2-1线性表的定义和特点

线性表(Linear List)：线性表是具有相同特性的数据元素的一个有限序列 $(a_1,a_2,a_3,...,a_{i-1},a_i,a_{i+1},..a_n)$ i:下标，元素的序号，表示元素在表中的位置 n:元素总个数，即表的长度 n=0时表称为空表 $a_{i-1}$:ai的前缀 $a_{i+1}$:ai的直接后继 a1:线性起点 an:线性终点

线性表是由n(n>=0)个元素（结点）组成的有限数列E.x. 有26个英文祖母组成的英文表 (A,B,C,...,X,Y,Z) 数据元素都是字母，关系是线性的

2-2案例引入

一元多项式的运算 $P_n(X) = p_0x^0+p_1x^1 + p_2x^2+...+p_mx^m$ 线性表P=(P0,P1,P2,...,Pn)每一项的指数i隐含在其系数Pi的序号中 例如:$P(X)=10+5x-4x^2+3x^3+2x^4$ 用数组表示: 指数(下标i)  0 1 2 3 4 系数Pi    10 5 -4 3 2

$R_n(X)=P_n(X)+Q_m(X)$ 线性表$R=(p_0+q_0,p_1+q_1,p_m+q_m,...,p_n)$

稀疏多项式

$S=1+x^{100000}+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)从具体应用中抽出共性的逻辑关系和基本操作(抽象数据类型)，然后实现其存储结构和基本操作