例：一元多项式的运算

$$
\begin{align}
P_n(x)&=p_0+p_1x+\cdots+p_nx^n
\
Q_m(x)&=q_0+q_1x+\cdots+q_mx^m
\end{align}
$$

通过线性表存储信息

$P_n(x)$ ：

下标	0	1	···	n
值	$p_0$	$p_1$	···	$p_n$

---

$Q_m(x)$ ：

下标	0	1	···	m
值	$q_0$	$q_1$	···	$q_m$

运算示例

$R_n(x)=P_n(x)+Q_m(x)$
$线性表R=(p_0+q_0,\ p_1+q_1,\ \cdots)$

其中下标 0 的值为 $x^0$ 的系数；下标 1 的值为 $x^1$ 的系数，依次类推……

稀疏多项式的运算

(a) $A(x)=7+3x+9x^4+5x^{14}$

下标i	0	1	2	3
系数a[i]	7	3	9	5
指数	0	1	4	14

(b) $B(x)=8x+11x^6-9x^9$

下标i	0	1	2
系数b[i]	8	11	-9
指数	1	6	9

$P_n(x)=p_1x^{e_1}+P_2x^{e_2}+\cdots+p_mx^{e_m}$
$线性表P=((p_1,e_1),(p_2,e_2),\cdots,(p_m,e_m))$

$线性表A=((7,0),(3,1),(9,4),(5,14))$
$线性表B=((8,1),(11,6),(-9,9))$

• 创建一个新数组C
• 分别从头遍历比较a和b的每一项
  • 指数相同，对应系数相加，若其和不为零，则在C中添加新项
  • 指数不相同，则将指数较小的项复制到C中
• 一个多项式已遍历完毕时，将另一个剩余项依次复制到C中即可

(c) $C(x)=A(x)+B(x)$

下标i	0	1	2	3	4	5
系数c[i]	7	11	9	11	-9	5
指数	0	1	4	6	9	14

C 声明多大合适呢？

• 顺序存储结构存在问题
  • 存储空间分配不灵活
  • 运算的空间复杂度高

总结

• 线性表中的数据元素的类型可以为简单类型，也可以为复杂类型。
• 许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用单独编写一个程序
• 从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作。