2.6　多项式相加

对于符号多项式的各种操作,实际上都可以利用线性表来处理。比较典型的是关于一元多项式的处理。在数学上,一个一元多项式P_n（x）可按升幂的形式写成如下形式。

Pn（X）＝P₀＋P₁X＋P₂X²＋P₃X³＋…＋P_nXⁿ

p_iXi是多项式的第i项（0≤i≤n）。其中,a_i为系数,x为变量,i为指数。它有n＋1个系数唯一确定。因此,在计算机中可以用一个线性表P来表示。

P＝（P₀,P₁,P₂,…,P_n）

假设Q_m（x）是一个一元多项式,则它也可以用一个线性表Q来表示,即

Q＝（q₀,q₁,q₂,…,q_m）

若假设m＜n,则两个多项式相加的结果为R_n（x）＝P_n（x）＋Q_m（x）,也可以用线性表R来表示。

R＝（p₀＋q₀,p₁＋q₁,p₂＋q₂,…,p_m＋q_m,p_m＋₁,…,p_n）

对P、Q、R既可以采用顺序存储结构,也可以采用链式存储结构。使用顺序存储结构可以使多项式相加的算法十分简单,即p[0]存系数p₀,p[1]存系数p₁,…,p[n]存系数p_n,对应单元的内容相加即可。但当多项式中存在大量的零系数时,这种表示方式就会浪费大量的存储空间,例如:

R（x）＝1＋5x¹⁰⁰＋8x^{1 000}

若采用顺序存储结构,则需要1 001个空间,而存储的有用数据只有三个,这无疑是一种浪费。为了有效而合理地利用存储空间,则可以用链式存储结构来表示多项式。

采用链式存储结构表示多项式时,多项式中的每一个非零系数项构成链表中的一个结点,对于系数为零的项则无需存储。若只存储非零系数项,则必须存储相应的指数信息才行。

一般情况下,一元多项式（只表示非零系数项）可表示成如下形式。

P_n（x）＝p₁x^e1＋p₂x^e2＋…＋p_mx^em

其中,p_i是指数为e_i的项的系数且0≤e₁≤e₂≤…≤e_m＝n。若只存储非零系数,则多项式中每一项由指数项和系数项两项构成,可用线性表表示如下。

（（p₁,e₁）,（p₂,e₂）,…,（p_m,e_m））

采用上述的方法存储数据,在最坏的情况下,即n＋1个系数都不为零时,比只存储系数的方法多存储1倍的数据。但对于非零系数多的多项式则不宜采用这种方式。

多项式链表中的每一个非零项结点结构用C语言描述如下。

假设有多项式P（x）＝4＋2x－8x⁸＋9x¹⁴与Q（x）＝6x＋5x²＋7x⁸已经用单链表表示,其头结点分别为ph和qh,如图2－21所示。

图2－21　多项式的单链表存储结构

则两个多项式相加为R（x）＝4＋8x＋5x²＋15x⁸＋9x¹⁴。其运算规则为:假设指针p、q分别指向多项式P（x）和多项式Q（x）中当前进行比较的某个结点,则比较两个结点的数据域的指数项。两个多项式中所有指数相同的项的对应系数相加,若和不为零,则构成“和多项式”中的一项；所有指数不相同的项均复制到“和多项式”中。若以单链表作为存储结构,并且“和多项式”中的结点无需另外生成,则可看成是将多项式Q加到多项式P中,其具体过程如下。

（1）若p－＞exp＜q－＞exp,则结点p所指的结点应是“和多项式”中的一项,令指针p后移。

（2）若p－＞exp＝q－＞exp,则将两个结点中的系数相加。当和不为零时修改结点p的系数域,释放q结点；若和为零,则“和多项式”中无此项,从表A中删去p结点,同时释放p和q结点。

（3）若p－＞exp＞q－＞exp,则结点q所指的结点应是“和多项式”中的一项,将结点q插入到结点p之前,并且令指针q在原来的链表上后移。

上述过程反复进行,直到p或q的值为空为止。此时,若p（或q）不为空,则说明P（x）链表（或Q（x）链表）中还有未处理的结点,需要将它们复制到R（x）链表中。

按以上运算规则得到的“和多项式”链表如图2－22所示。

图2－22　和多项式链表

具体的算法如下。

本章小结

（1）线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表,用后者表示的线性表简称为链表。

（2）熟练掌握两类存储结构的描述方法,注意一维数组的下标从0开始,并掌握链表中指针p和结点＊p的对应关系,链表中的头结点、头指针和首元素结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实地掌握指针操作和内存动态分配的编程技术是学好本章的基础。

（3）熟练掌握线性表在顺序存储结构上实现基本操作（查找、插入和删除）的算法。

（4）熟练掌握在各种链表结构中实现线性表操作的基本方法,能在实际应用中选用适当的链表结构。

（5）能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。