第2章 线性表及其实现

一元多项式的表示

分析：多项式的关键数据:多项式项数n，各项系数ai 及指数 i

• 方法1:顺序存储结构直接表示

利用数组存储，数组下标表示指数i，然后数组数值表示系数ai

arr1.png

两个多项式相加: 两个数组对应分量相加

问题:如何表示多项式 x+3x^2000 ? 

需要创建2001个空间 ，内部会包含很多0 造成很多的空间浪费不合理

• 方法2:顺序存储结构表示非零项

  每个非零项 ai xi 涉及两个信息:系数 ai 和指数 i
  可以将一个多项式看成是一个 (ai,i) 二元组的集合。

  
  arr2.png

按指数大小有序存储!

相加过程:从头开始，比较两个多项式当前对应项的指数

P1: (9,12), (15,8), (3,2)

P2: (26,19), (-4,8), (-13,6), (82,0)

P3: (26,19) (9,12) (11,8) (-13,6)

实现了俩个多项式相加 空间也没有造成浪费 利用结构数组存储

• 方法3:链表结构存储非零项

list.png

“线性表(Linear List)”:由同类型数据元素构成有序序列的线性结构

广义表(Generalized List)

• 广义表是线性表的推广
• 对于线性表而言， n个元素都是基本的单元素;
• 广义表中，这些元素不仅可以是单元素也可以是另一个广义表。

多重链表:链表中的节点可能同时隶属于多个链

• 多重链表中结点的指针域会有多个，如前面例子包含了Next和 SubList两个指针域;
• 但包含两个指针域的链表并不一定是多重链表，比如在双向链表 不是多重链表。

什么是堆栈

具有一定操作约束的线性表 只在一端(栈顶，Top)做 插入、删除

后入先出:Last In First Out(LIFO)