2.5.2 一元多项式的相乘

两个一元多项式的相乘，需要将一个多项式的每一项的指数与另一个多项式的每一项的指数相加，并将其系数相乘。假设两个多项式A_n（x）=a_nxn+a_n-1xn-1+…+a₁x+a₀和B_m（x）=b_mxm+b_m-1xm-1+…+b₁x+b₀，要将这两个多项式相乘，就是将多项式A_n（x）中的每一项与B_m（x）相乘，相乘的结果用线性表表示为（（a_n*b_m,n+m）,（a_n-1*b_m,n+m-1）,…,（a₁,1）,（a₀,0））。

例如，两个多项式A（x）和B（x）的相乘后得到C（x）。

A（x）=7x4+2x2+3x

B（x）=6x3+5x2+6x

C（x）=42x7+49x6+74x5+51x4+59x3+40x2

以上多项式可以表示成链表，如图2.39所示。

其中，A、B和C分别是多项式A（x）、B（x）和C（x）对应链表的头指针，A（x）和B（x）两个多项式相乘，首先计算出A（x）和B（x）的最高指数和，即4+3=7，则A（x）和B（x）的乘积C（x）的指数范围在0～7之间。然后将A（x）按照指数降幂排列，将B（x）按照指数升序排列，分别设两个指针pa和pb，pa用来指向链表A，pb用来指向链表B，从第一个结点开始计算两个链表的expn域的和，并将其与k比较（k为指数和的范围，从7到0递减），使链表的和呈递减排列。如果和小于k，则pb=pb->next；如果和等于k，则计算二项式的系数的乘积，并将其赋值给新生成的结点；如果和大于k，则pa=pa->next。这样得到多项式A（x）和B（x）的乘积C（x）。最后将链表B重新逆置。

1.一元多项式的创建

2.两个一元多项式的相乘

3.测试程序

程序运行结果如图2.40所示。