2.5.1 一元多项式的表示

一元多项式A_n（x）可以写成降幂的形式：

A_n（x）=a_nxn+a_n-1xn-1+…+a₁x+a₀

如果a_n≠0，则A_n（x）被称为n阶多项式。一个n阶多项式由n+1个系数构成。一个n阶多项式的系数可以用线性表（a_n,a_n-1,…,a₁,a₀）表示。

线性表的存储可以采用顺序存储结构，这样使多项式的一些操作变得更加简单。可以定义一个维数为n+1的数组a[n+1]，a[n]存放系数a_n，a[n-1]存放系数a_n-1，…，a[0]存放系数a₀。但是，实际情况是多项式的阶数（最高的指数项）可能会很高，多项式的每个项的指数会差别很大，这可能会浪费很多的存储空间。例如，一个多项式

P（x）=10x2001+x+1

若采用顺序存储，则存放系数需要2002个存储空间，但是存储的有用数据只有3个。若只存储非零系数项，还必须存储相应的指数信息。

一元多项式A_n（x）=a_nxn+a_n-1xn-1+…+a₁x+a₀的系数和指数同时存放，可以表示成一个线性表，线性表的每一个数据元素由一个二元组构成。因此，多项式A_n（x）可以表示成线性表：

（（a_n,n）,（a_n-1,n-1）,…,（a₁,1）,（a₀,0））

多项式P（x）可以表示成（（10,2001）,（1,1）,（1,0））的形式。

因此，多项式可以采用链式存储方式表示，每一项可以表示成一个结点，结点的结构由3个域组成：存放系数的coef域，存放指数的expn域和指向下一个结点的next指针域。如图2.37所示。

结点结构类型描述如下：

图2.37 多项式的结点结构

例如，多项式S（x）=7x6+3x4-3x2+6可以表示成链表，如图2.38所示。

图2.38 一元多项式的链表表示