2.4 典型例题

一元多项式的操作已经成为表处理的典型用例。在数学上，一元多项式可按升幂的形式写成：

Pn(x)=p0+p1 x1+p2 x2+…+pn xn

式中，pi是xi项的系数，则一个最高幂次为n的多项式可由n+1个系数唯一确定，因此，在计算机里，它可以用一个线性表P来表示：

P=（p0, p1, p2, …, pn）

假设Qm(x)是一个一元多项式，同样可以用线性表Q表示：

Q=（q0, q1, q2, …, qm）

若设m<n，则两个多项式相加的结果Rn(x)= Pn(x)+Qm(x)，用线性表R表示：

R=（p0 +q0, p1+q1, p2+q2, …, pm+qm, pn+1, …, pn）

显然，表示多项式的线性表可以用顺序存储结构，也可以用链式存储结构。

1.一元多项式的存储表示

（1）一元多项式的顺序存储表示。一元多项式Pn(x)的顺序存储表示有两种方法。

一种方法是：只存储多项式的各项系数（不管系数是否为零，全部按幂次的顺序存储），每个系数对应的指数隐含在存储系数的下标里。如上所述，p[0]存系数p0，对应x0的系数，p[1]存系数p1，对应x1的系数，…，p[n]存系数pn，对应xn的系数。至此，一元多项式的相加运算就非常简单，只需要将下标相同的单元内容相加即可。

然而，在通常的应用中，多项式的幂次可能很高而且变化较大，同时非零项又往往很少。例如S(x)=1+5x1000+3x20000，若采用以上方法存储，则需要20001个存储空间，而实际有用的数据只有3个，无疑是一种浪费。

另一种方法是：采取只存储非零项的方法，此时每个存储单元需要存储：非零项系数和非零项指数。即对一元多项式Pn(x)，可写成：

其中，pi是指数为ei的项的非零系数，且满足

0≤e1<e2<…<em=n

则只需要存储如下线性表：

((p1, e1)，(p2, e2), …, (pm, em))

便可唯一确定多项式Pn(x)。即使在最坏情况下，n+1个系数都不为零，也只比前一种方法多存储一倍的数据，但是，对于通常情况如S(x)类的多项式，这种方法将大大节省存储空间。

（2）一元多项式的链式存储表示。在链式存储中，对一元多项式只存储非零项，则作为链式存储结构的基本单元结点由三部分构成：系数、指数及指向下一结点的指针。

表示一元多项式的单链表定义如下：

struct Polynode
     { int coef ;      /*系数*/
       int eap ;       /*指数*/
       Polynode  *next ;
     } PolyNode, *PolyList ;

根据以上数据类型定义，可以设计一元多项式的链表建立算法。

假设通过键盘输入一组多项式的系数和指数，用表尾插入法建立一元多项式链表，以输入系数0为输入结束标志，并规定输入多项式数据时，总是按指数从小到大的顺序输入。

算法2.19 一元多项式链表的建立算法。

PolyList polycreate ( )
     {  PolyNode *head, *rear, *s ;
        int c, e ;
        head=(PolyList) malloc (sizeof ( PolyNode ));    /*建立头结点*/
        rear=head;                       /*rear始终指向表尾，便于在表尾插入新结点*/
        scanf ( "%d, %d", &c, &e ) ;     /*输入多项式的系数和指数*/
        while ( c != 0 )                 /*若c=0，则表示多项式输入结束*/
            { s=(PloyList ) malloc (sizeof ( PolyNode )) ;  /*申请新的结点空间*/
              s ->coef=c ;   s ->exp=e ;
              rear ->next=s ;            /*在当前表尾插入*/
              rear=s ;
              scanf ( "%d, %d", &c, &e ) ;
           }
      rear ->next=NULL ;     /*将表的最后一个结点的next指针置空，以示表结束*/
        return ( head ) ;
     }

根据以上一元多项式的链式存储结构的定义，以及多项式链表的构造算法，则两个多项式A(x)= 5+4x2+7x5+8x12和B(x)= 3x+2x2-7x5的单链表表示如图2.24所示。

2.一元多项式的相加运算

根据一元多项式相加的运算规则：

（1）对于两个一元多项式中所有指数相同的项，对应系数相加，若和不为零，则构成“和多项式”中的一项；

（2）对于两个一元多项式中指数不相同的项，则分别复抄到“和多项式”中去。

假设以单链表A和B分别表示两个一元多项式，则它们的和实质上就是两个链表的合并操作，而合并的具体要求必须满足以上多项式运算的两条规则。图2.25所示为图2.24中两个多项式相加的结果，其中孤立的结点为相加过程中被释放的结点。

显然，相加后原来的两个多项式链表已不复存在，而“和多项式”中的结点也无须另外申请空间。当然，假如需要保存原来的两个多项式链表，则相加运算就必须另外为“和多项式”申请结点空间，实现的过程大致相同。

算法2.20 一元多项式相加的算法（原多项式指数从低到高，和的指数由高到低）。

void AddPolyn ( PolyList polya, PolyList polyb )
     /*将两个多项式相加，然后将和多项式存放到多项式polya中，并释放多余结点*/
     { PolyList *p , *q , *tail , *s ;
       int sum;
       p=polya->next ;   q=polyb->next ;     /*令p, q分别指向两个链表的第一个结点*/
       tail=polya ;                          /*tail指向和多项式链表的尾结点*/
       while ( p!=NULL && q!=NULL )
          { if ( p->exp<q->exp )             /*p所指当前结点的指数小，将该结点插入和多项式*/
               { tail->next=p ;  tail=p ;  p=p->next ; }
            else if ( p->exp > q ->exp )     /* q所指当前结点的指数小，将之插入和多项式*/
                   { tail->next=q ;  tail=q ;  q=q ->next ; }
                 else                        /*p与q所指结点的指数相同，则系数相加*/
                    { sum=p->coef+q ->coef ;
                       if ( sum !=0 )        /*和不为0，则将系数修改，并插入和多项式链表*/
                         { p ->coef=sum ;
                           tail->next=p ;  tail=p ;  p=p->next ;
                           s=q ;  q=q->next ;  free ( s ) ;    /*释放多余空间*/
                    }
                  else   /*和为0，则删除p与q所指当前结点，并将p、q指针下移*/
                    { s=p ;  p=p->next ;  free( s ) ;
                      s=q ;  q=q->next ;  free ( s ) ;
                        }
                }
        }
}