2.4　线性表的应用

一般情况下，一个n次多项式可表示为：

其中，ai是指数为ei项的非零系数，而ei（1≤i≤n）满足0≤e1＜e2＜…＜em＝n。在多项式相加时，至少有两个或两个以上的多项式同时并存，而且在实现运算的过程中所产生的中间多项式和结果多项式的项数和指数都是难以预测的。有时，多项式的次数可能很高且变化很大，若采用顺序结构必然会造成内存空间的大量浪费。因此，在计算机中可采用链表来表示多项式。

当把一个多项式表示成一个单链表时，可将其每一个非零项用一个结点来表示。每个结点包含两个数据域和一个指针域，即系数域、指数域和指针域，并分别用coef、exp和next表示，其形式如下：

例如，多项式A（x）＝3x14＋2x8＋1的链表形式为：

而多项式B（x）＝8x14－3x10＋10x6的链表形式为：

由A（x）加B（x）可得到多项式C（x）＝11x14－3x10＋2x8＋10x6＋1。表示C（x）的链表形式为：

于是，两个多项式相加的问题就变为由单链表ah和bh求单链表ch的问题，下面讨论解决这一问题的算法。

多项式的链式存储结构可描述如下：

多项式相加运算的规则是：两个多项式中系数相同的项对应系数相加，若和不为零，则构成“和多项式”中的一项，所有指数不同的项均复制到“和多项式”中。

1.方法1

对于表示多项式A（x）和B（x）的单链ah和bh，使用指针pa和pb分别沿着两个链表向表尾移动，以指示当前被检测的结点。当pa≠NULL且pb≠NULL时，可能出现下列3种情况之一。

（1）pa－exp＞pb－exp。这说明pa所指的结点的指数大于pb所指的结点的指数。由于单链表的结点是以指数值的递减次序排列的，因此，pa所指结点中的系数值和指数值应写入一个新结点，然后将这个新结点插入到单链表ch的表尾结点之后，成为C（x）中新的表尾结点。同时pa移向下一个结点，继续扫描A（x）中后面的结点。

（2）pa－exp＝pb－exp。这说明pa和pb所指结点的指数相等。这时，应将它们的系数相加，若系数相加的结果为零，则不产生一个新的结点；否则应产生一个新结点，按照（1）的类似做法插在C（x）的尾结点之后，此时，pa和pb同时移向它们各自的下一个结点。

（3）pa－exp＜pb－exp。这和（1）的情况完全类似，只不过复制的是pb所指的结点，然后pb移向下一个结点。

重复上述过程，直至pa或pb的值为“NULL”（有时pa和pb的值会同时为NULL，但这不会影响算法）。若pa≠NULL，则说明单链表ah中还有结点未处理，这时需要将它们复制到ch上；若pb≠NULL，则表示单链表bh中还有结点未处理，同样需要将它们复制到ch上。

在逐步产生C（x）的单链表的过程中，我们总是把新产生的结点加在ch的表尾结点之后。为了避免每次都要从C（x）的第一个结点开始扫描，可令指针变量pc总是指着C（x）的表尾结点，这样就能很方便地把新结点插在pc所指的结点之后。插入新结点到ch中的子过程如下，它供后面多项式相加算法调用。

算法2.9 结点插入算法

下面给出两个多项式相加的算法。

算法2.10 两个多项式相加的算法

上述算法的主要运行时间花费在指数比较和系数相加上。例如，若设多项式A（x）有n项、B（x）有m项，则运行该算法的时间为O（m＋n）。

2.方法2

运算过程中利用原来多项式的空间，这种方法不能复算，但不必另外申请空间。即“和多项式”链表中的结点无须另外生成，只要从两个多项式的链表中摘取即可，其运算规则如下。

算法2.11 两个多项式相加的算法改进

求集合“并”和“交”的运算可以用链表实现。假设由键盘输入集合元素，先建立表示集合的链表，然后通过链表的操作实现集合的运算。例如，已知两个整数集合A和B，它们的元素按递增有序的方式分别存放在两个单链表ha和hb中，如何编写一个函数求这两个集合的并集C呢？可将表示集合C的链表另辟空间，且同样是以递增有序的顺序存放，具体算法如下。

算法2.12 求两个集合的并集