一元多项式 ，在计算机中，可以用一个线性表来表示： P = (p0, p1, …，pn)。

但是对于形如 S(x) = 1 + 3x¹⁰⁰⁰⁰ – 2x²⁰⁰⁰⁰ 的多项式，上述表示方法就不合适 

一般情况下的一元稀疏多项式可写成 P_n(x) = p₁x^e1 + p₂x^e2 + ┄ + p_mx^em。其中，p_i 是指数为e_i 的项的非零系数，0≤ e₁ < e₂ < ┄ < e_m = n。可以下列线性表表示：

 

（（p₁, e₁）, (p₂, e₂), ┄, (p_m,e_m) ）

 

例如: P₉₉₉(x) = 7x³ - 2x¹² - 8x⁹⁹⁹ 可用线性表( (7, 3), (-2, 12), (-8, 999) ) 表示。

 

显然，实现稀疏的一元多项式，应该采用链式存储结构。可以利用在2.3.1中链表的存储结构，将ElemType类型定义成多项式的系数和指数就可以了。

 

typedef  struct           //一元多项式结点数据域的类型

{

    float coef;           //系数

    int  exp;            //指数

} ElemType;

typedef  struct node

{

    ElemType data;        //数据域 

    struct node *next;     //链指针域指向后继

 }*Link;

【算法】一元多项式相加

void addploy(Link Pa,Link Pb,Link,*Pc)       //A,B为带头结点的链表

{

*Pc=P=Pa;qa=Pa->next;qb=Pb->next;

while((qa&&qb)&&(!qa->next)&&(!qb->next))    //循环条件A,B链表都没结束

 {  a=qa->exp;b=qb->exp;

switch(compare(a,b))                //比较两个多项式中各个结点的幂的大小

{ case -1:                         //A链表中结点的指数小，链入结果中

P->next=qa; P=qa;

qa=qa->next; break;

      case 0:                          //A、B链表中结点的指数相等

              qa->coef + =qb->coef;     //将两个系数相加

              if (qa->coef==0)

                    {  u=qa; v=qb;       //系数相加为零

                    qa=qa->next;qb=qb->next;

free(u,v);}        //释放结点

else {  P->next=qa;P=qa;v=qb;

qa=qa->next;qb=qb->next;

                    free(v);}

             break;

      case 1:                         //B链表中结点的指数小，链入结果中

P->next=qb; P=qb;

qb=qb->next; break;

        }

     }

 free(Pb)                              //释放头结点

 }