下载掌阅APP，畅读海量书库
立即打开
一元多项式的相乘是线性表在日常生活中的一个典型应用，它的各种操作集中了线性表的各种基本操作。
一元多项式A n (x)可以写成降幂的形式：
A n (x)=a n x n +a n-1 x n-1 +…+a 1 x+a 0
若a n ≠0，则A n (x)被称为n阶多项式。一个n阶多项式由n+1个系数构成，它的系数可以用线性表(a n ,a n-1 ,…,a 1 ,a 0 )表示。
线性表的存储可以采用顺序存储结构，这样使多项式的一些操作变得更加简单。可以定义一个维数为n+1的数组a[n+1]，a[n]存放系数a n ，a[n-1]存放系数a n-1 ,…,a[0]存放系数a 0 。但是，实际情况是，多项式的阶数（最高的指数项）可能会很高，多项式的每个项的指数差别很大，这可能会浪费很多存储空间。例如，一个多项式：
P(x)=10x 2001 +x+1
若采用顺序存储，则存放系数需要2002个存储空间，但是存储的有用数据只有3个。若只存储非零系数项，则必须存储相应的指数信息。
一元多项式A n (x)=a n x n +a n-1 x n-1 +…+a 1 x+a 0 的系数和指数同时存放，可以表示成一个线性表，线性表的每一个数据元素由一个二元组构成。因此，多项式A n (x)可以表示成线性表((a n ,n),(a n-1 ,n-1),…,(a 1 ,1),(a 0 ,0))多项式P(x)可以表示成((10,2001),(1,1),(1,0))的形式。
多项式可以采用链式存储的方式表示，每一项可以表示成一个结点，结点的结构由3个域组成：存放系数的coef域，存放指数的expn域和指向下一个结点的next指针域，如图2-29所示。
图2-29 多项式的结点结构
结点结构类型描述如下：
例如，多项式S(x)=7x 6 +3x 4 -3x 2 +6可以表示成链表，如图2-30所示。
图2-30 一元多项式的链表表示
两个一元多项式相乘，需要将一个多项式的每一项的指数与另一个多项式的每一项的指数相加，并将其系数相乘。假设两个多项式A n (x)=a n x n +a n-1 x n-1 +…+a 1 x+a 0 和B m (x)=b m x m +b m-1 x m-1 +…+b 1 x+b 0 ，要将这两个多项式相乘，就是将多项式A n (x)中的每一项与B m (x)相乘，相乘的结果用线性表表示为((a n b m ,n+m),(a n-1 b m ,n+m-1),…,(a 1 ,1),(a 0 ,0))。
例如，两个多项式A(x)和B(x)相乘后得到C(x)。
A(x)=7x 4 +2x 2 +3x
B(x)=6x 3 +5x 2 +6x
C(x)=42x 7 +49x 6 +74x 5 +51x 4 +59x 3 +40x 2
以上多项式可以表示成链式存储结构，如图2-31所示。
图2-31 多项式的链表表示
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重新逆置。
程序运行结果如下。
思政元素： 在利用数据结构描述数据对象、设计算法时，要根据实际问题选择合适的存储结构来设计算法。例如，实现一元多项式的相加、相乘运算以及关于学生信息表的构造与操作，选择使用顺序存储还是链式存储呢？这就是我们需要考虑的问题。也就是在学习数据结构的过程中，不仅要学习算法思想、实现算法，还要养成正确认识事物、分析事物特点的能力，了解到凡事都具有两面性，在对立统一中不断发展变化，不能仅看到事物的一面而忽视了另一面。