1. 一元多项式的表示和相加
在数学上，一个一元多项式\(P_{n}(x)\)可升序写成：
\(P_{n}(x) = p_{0}+p_{1}x^1+p_{2}x^2+...++p_{n}x^n\)
它由n+1个系数唯一确定。因此，在计算机中，可用一个线性表P来表示：
\(P=(p_{0},p_{1},p_{2},...,p_{n})\)
每一项的指数i隐含在其系数\(p_{i}\)的序号里。
假设\(Q_{m}(x)\)是一元m次多项式，同样可用线性表Q来表示：
\(Q=(q_{0},q_{1},q_{2},...,q_{n})\)
不失一般性，设m < n，则两个多项式相加的结果可用线性表R表示：
\(R=(p_{0}+q_{0},p_{1}+q_{1},p_{2}+q_{2},...,p_{n}+q_{n})\)但是，只存储系数的方案对存在大量零系数的多项式并不适用。
\(S(x)=1+3x^{10000}+2x^{20000}\)
要用一个长度为20001的线性表来表示，表中仅有3个非零系数，会浪费大量存储空间。
若只存储非零系数项，则必须同时存储相应的指数。
一般情况下，一元n次多项式可写成：
\(P_{n}=p_1x^{e_1}+p_2x^{e_2}+...+p_mx^{e_m}\)
其中，\(p_i\)是指数为\(e_i\)的项的非零系数，且满足
\(0 \le e_1 < e_2<...<e_m=n\)
若用一个长度为m且每个元素有两个数据项（系数项和指数项）的线性表
\(((p_1,e_1),(p_2,e_2),...,(p_m,e_m))\)
便可唯一确定多项式\(P_n(x)\)。在最坏情况下，n+1(=m)个系数都不为零，则比只存储每项系数的方案要多存储一倍的数据，但是对于\(S(x)\)类多项式，这种存储表示将大大节省空间。
一元多项式可采用两种存储表示方法。在实际工程中使用哪一种？视多项式进行哪种运算而定。若只对多项式进行求值不改变多项式的系数和指数的运算，则采用顺序存储结构；否则，采用链式存储结构。本节讨论使用链式存储形式。
例如：
\(A_{17}(x)=7+3x+9x^8+5x^{17}\)
\(B_8(x)=8x+22x^{7}-8x^8\)
采用单链表存储效果如下：
将两个多项式相加为：
\(C_{17}(x)=7+11x+22x^7+5x^{17}\)
采用单链表存储效果如下：
2. 一元多项式的实现
（1）一元多项式抽象数据类型的动态链式表示
typedef struct //项的表示，多项式的项作为LinkList的数据元素
{
float coef; //系数
int expn; //指数
}term, ElemType;
//两个类型名：term用于本ADT，ElemType为LinkList的数据对象名
typedef struct Node
{
ElemType data;
struct Node * next;
}LNode, *LinkList, *Position;
typedef LinkList polynomial;（2）一元多项式的创建
void CreatPolyn(polynomial &P, int m)
//输入m项的系数和指数，建立表示一元多项式的有序链表P
{
polynomial h; ElemType e;
int i;
InitList(P);
h = P;
e.coef = 0.0;
e.expn = -1;
SetCurElem(h, e); //设置头结点的数据元素
for(i = 1; i <= m; ++i)
{
Position q; LinkList s;
scanf("%f %d",&e.coef,&e.expn);
if(!LocateElem(P, e, q, cmp)) //当前链表不存在该指数项
{
if(MakeNode(s, e))
InsFirst(q,s); //生成结点并插入链表
}
}
}//CreatPolyn
在函数CreatPolyn里面用到函数的说明：
int cmp(term a, term b)
//依a的指数值<、=或>b的指数值，分别返回-1、0或+1
Status LocateElem(polynomial L, term e, Position &q, int (*compare)(term,term))
//若升序链表L中存在与e满足判定函数compare()取值为0的元素，则q指示L中
//第一个值为e的结点的位置，并返回TRUE；否则q指示第一个与e满足判定函数
//compare()取值>0的元素的前驱的位置。并返回FALSE。（用于一元多项式）
Status MakeNode(LinkList &p, ElemType e)
//分配由p指向的值为e的结点，并返回OK；若分配失败。则返回ERROR.
Status InsFirst(LinkList q, LinkList s)
//将s指向的结点，插入到q指向的结点后面（3）一元多项式的相加
void AddPolyn(polynomial &Pa, polynomial &Pb)
//多项式的加法：Pa = Pa + Pb,利用两个多项式的结点构成“和多项式”。
{
LinkList ha = Pa; //ha和hb分别指向Pa和Pb的头指针
LinkList hb = Pb;
LinkList qa = Pa->next;
LinkList qb = Pb->next; //ha和hb分别指向pa和pb的前驱
while (qa && qb) //如果qa和qb均非空
{
float sum = 0.0;
term a = qa->data;
term b = qb->data;
switch (cmp(a,b))
{
case -1: //多项式PA中当前结点的指数值小
ha = qa;
qa = qa->next;
break;
case 0: //两者指数值相等
sum = a.coef + b.coef;
if(sum != 0.0)
{ //修改多项式PA中当前结点的系数值
qa->data.coef = sum;
ha = qa;
}else
{ //删除多项式PA中当前结点
DelFirst(ha, qa);
free(qa);
}
DelFirst(hb, qb);
free(qb);
qb = hb->next;
qa = ha->next;
break;
case 1:
DelFirst(hb, qb);
InsFirst(ha, qb);
qb = hb->next;
ha = ha->next;
break;
}//switch
}//while
if(!ListEmpty(Pb))
Append(Pa,qb);
DestroyList(hb);
}//AddPolyn在AddPolyn函数里面用到的函数说明：
Status DelFirst(LinkList h, LinkList q)
//h指向q的前驱，让h指向q的下一个结点
Status Append(LinkList &L, LinkList s)
//将指针s(s->data为第一个数据元素)所指(彼此以指针相链,以NULL结尾)的
//一串结点链接在线性链表L的最后一个结点之后
