1、一元多项式的运算

用顺序表存储多项式每次幂的系数，然后将将两个多项式对应位置的数组相加

代码实现：

输出结果：

2、稀疏多项式的运算

许许多多系数和指数（p,e）构成线性表A、B

算法步骤1：使用顺序表

1. 创建一个新数组c
2. 分别从头遍历比较a和b的1每一项

​ √ 指数相同，对应系数相加，若其和不为零，则在c中增加一个新项

​ √ 指数不相同，则将指数较小的项复制到c中

3. 一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可

问题：算法复杂度高、空间利用率低、分配不灵活，而且不知道数组c多大合适

====》使用链表

链表的结点有两个数据域，分别储存系数和指数。

算法步骤2：使用链表

创建链表算法步骤：

① 创建一个只有头结点得空链表

② 根据多项式的项的个数，循环n次执行以下操作：

· 生成一个新结点*s；(1)

· 输入多项式当前项的系数和指数赋给新结点*s的数据域；(2)

· 设置一前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱，pre初值指向头结点；(3)

· 指针q初始化，指向首元结点；(4)

· 循着链表向下逐个寻找链表中当前结点与输入项指数，找到第一个大于等于输入项指数的结点*q；(5)

· 将输入项结点*s插入到结点 *q之前；(6)

代码实现：

多项式相加算法步骤：

① 指针p1和p2初始化，分别指向Pa和Pb的首元结点。

② p3指向和多项式的当前结点，初值为Pa的头结点。

③ 当指针p1和p2均未达到相应表尾时，则循环比较p1和p2所指结点对应的指数值(p1->expn与p2->expn)，有以下三种情况：

（1）当p1->expn = p2->expn时，将两个结点中系数相加。

​ 1）若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点。

​ 2）若和为零，则删除p1和p2所指结点。

（2）当p1->expn < p2->expn时，将p1所指结点插入和多项式。

（3）当p1->expn > p2->expn时，将p2所指结点插入和多项式。

④ 将非空多项式的剩余段插入到p3所指结点之后。

⑤ 释放Pb的头结点。