多项式相加

时间：2022-10-26 百科知识版权反馈

【摘要】：但当多项式中存在大量的零系数时,这种表示方式就会浪费大量的存储空间,例如:若采用顺序存储结构,则需要1 001个空间,而存储的有用数据只有三个,这无疑是一种浪费。采用链式存储结构表示多项式时,多项式中的每一个非零系数项构成链表中的一个结点,对于系数为零的项则无需存储。两个多项式中所有指数相同的项的对应系数相加,若和不为零,则构成“和多项式”中的一项；所有指数不相同的项均复制到“和多项式”中。

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所示。