2.4 典型例題

一元多項(xiàng)式的操作已經(jīng)成為表處理的典型用例。在數(shù)學(xué)上，一元多項(xiàng)式可按升冪的形式寫成：

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

式中，pi是xi項(xiàng)的系數(shù)，則一個(gè)最高冪次為n的多項(xiàng)式可由n+1個(gè)系數(shù)唯一確定，因此，在計(jì)算機(jī)里，它可以用一個(gè)線性表P來表示：

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

假設(shè)Qm(x)是一個(gè)一元多項(xiàng)式，同樣可以用線性表Q表示：

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

若設(shè)m<n，則兩個(gè)多項(xiàng)式相加的結(jié)果Rn(x)= Pn(x)+Qm(x)，用線性表R表示：

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

顯然，表示多項(xiàng)式的線性表可以用順序存儲結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)。

1.一元多項(xiàng)式的存儲表示

（1）一元多項(xiàng)式的順序存儲表示。一元多項(xiàng)式Pn(x)的順序存儲表示有兩種方法。

一種方法是：只存儲多項(xiàng)式的各項(xiàng)系數(shù)（不管系數(shù)是否為零，全部按冪次的順序存儲），每個(gè)系數(shù)對應(yīng)的指數(shù)隱含在存儲系數(shù)的下標(biāo)里。如上所述，p[0]存系數(shù)p0，對應(yīng)x0的系數(shù)，p[1]存系數(shù)p1，對應(yīng)x1的系數(shù)，…，p[n]存系數(shù)pn，對應(yīng)xn的系數(shù)。至此，一元多項(xiàng)式的相加運(yùn)算就非常簡單，只需要將下標(biāo)相同的單元內(nèi)容相加即可。

然而，在通常的應(yīng)用中，多項(xiàng)式的冪次可能很高而且變化較大，同時(shí)非零項(xiàng)又往往很少。例如S(x)=1+5x1000+3x20000，若采用以上方法存儲，則需要20001個(gè)存儲空間，而實(shí)際有用的數(shù)據(jù)只有3個(gè)，無疑是一種浪費(fèi)。

另一種方法是：采取只存儲非零項(xiàng)的方法，此時(shí)每個(gè)存儲單元需要存儲：非零項(xiàng)系數(shù)和非零項(xiàng)指數(shù)。即對一元多項(xiàng)式Pn(x)，可寫成：

其中，pi是指數(shù)為ei的項(xiàng)的非零系數(shù)，且滿足

0≤e1<e2<…<em=n

則只需要存儲如下線性表：

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

便可唯一確定多項(xiàng)式Pn(x)。即使在最壞情況下，n+1個(gè)系數(shù)都不為零，也只比前一種方法多存儲一倍的數(shù)據(jù)，但是，對于通常情況如S(x)類的多項(xiàng)式，這種方法將大大節(jié)省存儲空間。

（2）一元多項(xiàng)式的鏈?zhǔn)酱鎯Ρ硎?。在鏈?zhǔn)酱鎯χ?，對一元多?xiàng)式只存儲非零項(xiàng)，則作為鏈?zhǔn)酱鎯Y(jié)構(gòu)的基本單元結(jié)點(diǎn)由三部分構(gòu)成：系數(shù)、指數(shù)及指向下一結(jié)點(diǎn)的指針。

表示一元多項(xiàng)式的單鏈表定義如下：

struct Polynode
     { int coef ;      /*系數(shù)*/
       int eap ;       /*指數(shù)*/
       Polynode  *next ;
     } PolyNode, *PolyList ;

根據(jù)以上數(shù)據(jù)類型定義，可以設(shè)計(jì)一元多項(xiàng)式的鏈表建立算法。

假設(shè)通過鍵盤輸入一組多項(xiàng)式的系數(shù)和指數(shù)，用表尾插入法建立一元多項(xiàng)式鏈表，以輸入系數(shù)0為輸入結(jié)束標(biāo)志，并規(guī)定輸入多項(xiàng)式數(shù)據(jù)時(shí)，總是按指數(shù)從小到大的順序輸入。

算法2.19 一元多項(xiàng)式鏈表的建立算法。

PolyList polycreate ( )
     {  PolyNode *head, *rear, *s ;
        int c, e ;
        head=(PolyList) malloc (sizeof ( PolyNode ));    /*建立頭結(jié)點(diǎn)*/
        rear=head;                       /*rear始終指向表尾，便于在表尾插入新結(jié)點(diǎn)*/
        scanf ( "%d, %d", &c, &e ) ;     /*輸入多項(xiàng)式的系數(shù)和指數(shù)*/
        while ( c != 0 )                 /*若c=0，則表示多項(xiàng)式輸入結(jié)束*/
            { s=(PloyList ) malloc (sizeof ( PolyNode )) ;  /*申請新的結(jié)點(diǎn)空間*/
              s ->coef=c ;   s ->exp=e ;
              rear ->next=s ;            /*在當(dāng)前表尾插入*/
              rear=s ;
              scanf ( "%d, %d", &c, &e ) ;
           }
      rear ->next=NULL ;     /*將表的最后一個(gè)結(jié)點(diǎn)的next指針置空，以示表結(jié)束*/
        return ( head ) ;
     }

根據(jù)以上一元多項(xiàng)式的鏈?zhǔn)酱鎯Y(jié)構(gòu)的定義，以及多項(xiàng)式鏈表的構(gòu)造算法，則兩個(gè)多項(xiàng)式A(x)= 5+4x2+7x5+8x12和B(x)= 3x+2x2-7x5的單鏈表表示如圖2.24所示。

2.一元多項(xiàng)式的相加運(yùn)算

根據(jù)一元多項(xiàng)式相加的運(yùn)算規(guī)則：

（1）對于兩個(gè)一元多項(xiàng)式中所有指數(shù)相同的項(xiàng)，對應(yīng)系數(shù)相加，若和不為零，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)；

（2）對于兩個(gè)一元多項(xiàng)式中指數(shù)不相同的項(xiàng)，則分別復(fù)抄到“和多項(xiàng)式”中去。

假設(shè)以單鏈表A和B分別表示兩個(gè)一元多項(xiàng)式，則它們的和實(shí)質(zhì)上就是兩個(gè)鏈表的合并操作，而合并的具體要求必須滿足以上多項(xiàng)式運(yùn)算的兩條規(guī)則。圖2.25所示為圖2.24中兩個(gè)多項(xiàng)式相加的結(jié)果，其中孤立的結(jié)點(diǎn)為相加過程中被釋放的結(jié)點(diǎn)。

顯然，相加后原來的兩個(gè)多項(xiàng)式鏈表已不復(fù)存在，而“和多項(xiàng)式”中的結(jié)點(diǎn)也無須另外申請空間。當(dāng)然，假如需要保存原來的兩個(gè)多項(xiàng)式鏈表，則相加運(yùn)算就必須另外為“和多項(xiàng)式”申請結(jié)點(diǎn)空間，實(shí)現(xiàn)的過程大致相同。

算法2.20 一元多項(xiàng)式相加的算法（原多項(xiàng)式指數(shù)從低到高，和的指數(shù)由高到低）。

void AddPolyn ( PolyList polya, PolyList polyb )
     /*將兩個(gè)多項(xiàng)式相加，然后將和多項(xiàng)式存放到多項(xiàng)式polya中，并釋放多余結(jié)點(diǎn)*/
     { PolyList *p , *q , *tail , *s ;
       int sum;
       p=polya->next ;   q=polyb->next ;     /*令p, q分別指向兩個(gè)鏈表的第一個(gè)結(jié)點(diǎn)*/
       tail=polya ;                          /*tail指向和多項(xiàng)式鏈表的尾結(jié)點(diǎn)*/
       while ( p!=NULL && q!=NULL )
          { if ( p->exp<q->exp )             /*p所指當(dāng)前結(jié)點(diǎn)的指數(shù)小，將該結(jié)點(diǎn)插入和多項(xiàng)式*/
               { tail->next=p ;  tail=p ;  p=p->next ; }
            else if ( p->exp > q ->exp )     /* q所指當(dāng)前結(jié)點(diǎn)的指數(shù)小，將之插入和多項(xiàng)式*/
                   { tail->next=q ;  tail=q ;  q=q ->next ; }
                 else                        /*p與q所指結(jié)點(diǎn)的指數(shù)相同，則系數(shù)相加*/
                    { sum=p->coef+q ->coef ;
                       if ( sum !=0 )        /*和不為0，則將系數(shù)修改，并插入和多項(xiàng)式鏈表*/
                         { p ->coef=sum ;
                           tail->next=p ;  tail=p ;  p=p->next ;
                           s=q ;  q=q->next ;  free ( s ) ;    /*釋放多余空間*/
                    }
                  else   /*和為0，則刪除p與q所指當(dāng)前結(jié)點(diǎn)，并將p、q指針下移*/
                    { s=p ;  p=p->next ;  free( s ) ;
                      s=q ;  q=q->next ;  free ( s ) ;
                        }
                }
        }
}