2-1线性表的定义和特点
线性表(Linear List)：线性表是具有相同特性的数据元素的一个有限序列
(a1,a2,a3,...,ai-1,ai,ai+1,...an)
i:下标，元素的序号，表示元素在表中的位置
n:元素总个数，即表的长度 n=0时表称为空表
ai-1:ai的前缀
ai+1:ai的直接后继
a1:线性起点
an:线性终点
线性表是由n(n>=0)个元素（结点）组成的有限数列
E.x. 有26个英文祖母组成的英文表
(A,B,C,...,X,Y,Z) 数据元素都是字母，关系是线性的
2-2 案例引入
一元多项式的运算
Pn(X)=P0X0+P1X1+...+PnX^n
线性表P=(P0,P1,P2,...,Pn)每一项的指数i隐含在其系数Pi的序号中
例如:P(X)=10+5x-4x^2 +3x3+2x4
用数组表示:
指数(下标i) 0 1 2 3 4
系数Pi 10 5 -4 3 2
Rn(X)=Pn(X)+Qn(X)
线性表R=(p0+q0,p1+q1,...,pm+qm,...,pn)
稀疏多项式
S(X)=1+2X^10000+ 3x^300
数组表示：
下标(i) 0 1 2
系数a[i] 1 2 3
指数 0 10000 300
多项式相加
线性表A=((7,0),(3,1),(9,8),(17,5))
线性表B=((8,1),(22,7),(-9,8))
如何相加这两个多项式？
(1)建立一个数组C
(2)分别从头遍历比较a和b的每一项
1)若指数相同，对应系数相加，若其和不为零，则在C中增加一个新项
2)若指数不相同，则将指数较小的放入C中
(3)一个多项式已遍历完毕时，将另一个的剩余项依次复制到c中即可
顺序存储结构存在的问题
(1)存储空间分配不灵活
(2)运算的空间复杂度高
因此可以用链式存储结构
总结:
(1)线性表中元素可以是简单类型，也可以为复杂类型
(2)许多实际应用有很多类似性，不应该为每个应用编写程序
(3)从具体应用中抽出共性的逻辑关系和基本操作(抽象数据类型)，然后实现其存储结构和基本操作
