线性表及其应用(算法)

　　算法描述

　　多项式用单链表在计算机内的表示与运算

　　（1）多项式链表的生成：设：多项式Pn(x)=anx^n+an-1x^n-1+……+a1x+a0(n次多项式共用n+1项)，在计算机内部采用链表表示这个多项式时，多项式中的每一个非零系数的项构成链表中的一个接点（而对于非零的项就不用表示）BNX。多项式中的非零系数所构成的项如下所示。

　　多项式非零系数项的结点结构

　　其中，数据域有两项：EXP(i)表示该项的指数值，COEF(i)表示该项的系数BNX。指针域NEXT(i)表示指向下一个非零系数项目的结点地址。

　　生成过程：按升幂顺序一数偶形式依次输入多项式非零项的指数EXPk和系数COEFk（k=1,2,3……m）,最后一输入指数0为结束BNX。对于每一次的输入，申请一个结点，填入的指数值与系数值后，将该结点链接到链表的末尾。

　　（2）单链表多项式加法基本思路：

　　设置指针(p和p)来扫描整个多项式BNX。算法思路是：不产生新的结点而利用原有的结点空间，设有指针变量p和q分别指向两个多项式Am(x)和Bn(x)单链表的第一个结点，依次比较两个指针所指结点的系数项。如果系数相等系数相加，和不为零修改*P的系数项并删除*q，和为零删除*P和*q；如果系数不相等，p->exp<q->exp时，*P为和多项式的一项，p->exp>q->exp时，把*P插在*q之前（*q为多项式的一项）；所有操作之后都要相应地移动指针，直到最后一个链空指针NULL，把另一个链剩下的结果点插在*P之后，扫描结束。

　　运算过程表达式如下：

　　设有多项式分别为Am(x)和Bn(x)BNX，且：

　　Am(x)= amx^m+am-1x^m-1+……+a1x+a0

　　Bn(x)= bnx^n+bn-1x^n-1+……+b1x+b0

　　其中：ai0(i=1,2,3…,m),bj0（j=1,2,3……n）

　　现在要求BNX他们的多项式之和表达式C(x),即求：

　　C(x)= Am(x)+ Bn(x)

　　（3）单链表多项式乘法基本思路：

　　在乘法运算实现之前，设置一个结果链表的头结点来预先指向结果链表，并且用一个双重循环来控制两的单链表的各项乘积，引入一个变量指针*Pa来扫描各项乘积结果，在*Pa未为NULL之前，为每次的乘积结果申请一个空间来存放，然后，对于各项的指数与指数、系数与系数分别相乘，各项乘积完毕后就把系数相同的项合并，系数之和非零，建立新的结点存储结果项，释放第一次乘积运算的各项结点，*Pa扫描结束,最后返回头结点，程序运算完毕BNX。

　　D(x)= Am(x)* Bn(x)

　　本人来自厦门白马网站>>>