2.5 線性表的應用舉例

本節通過對一元多項式加法求解問題的分析與設計，進一步熟悉線性表的存儲方式、運算實現技術等內容的應用。

【例2-10】已知兩個一元多項式a（x）和b（x），要求設計算法實現兩個一元多項式a（x）和b（x）的加法運算a（x）=a（x）+b（x）。

【問題分析】在數學中，符號多項式就是形如axe的項之和，其中a為系數，e為指數。換句話說，一個一元多項式可按升冪的形式寫為

它由n+1個系數唯一確定。因此，在計算機里，可用一個線性表A來表示：

每一項的指數隱含在其系數所在的位序號里。

假設Bm（x）是一個一元m次多項式，同樣可用線性表B來表示：

若m＜n，則Sn（x）=An（x）+Bm（x）也可以用線性表S來表示：

顯然，可以在計算機內部對A，B和S采用順序存儲結構，從而使多項式的加法運算變得簡單。但是在實際應用中，多項式的階數可能很高，且相鄰項之間的階數相差很大。例如P（x）=8+4x1002-3x20003，這樣的多項式若按照上述順序存儲方式，則需要用一長度為20004的線性表來表示，且表中僅有3項是非零元素，從而會造成大量的存儲空間浪費。為避免這種情況，我們自然會想到只存儲非零項，且在存儲非零項系數時同時存儲非零項的指數。在一般情況下，一元多項式可寫為

其中：pi是指數為ei的項的非零系數，滿足條件0≤e1＜e2＜…＜em=n。一元多項式可用以下線性表來表述：

雖然，對于一個非零項來說，其占用存儲空間量比只存儲系數要大，但對于P（x）類的多項式則大大地節省了存儲空間。但究竟是選擇順序存儲還是鏈式存儲呢？這就要看多項式要做何種運算而定。因為多項式的加法運算規則是：兩個多項式中所有指數相同的項對應的系數相加，若和不為零，則構成“和多項式”中的一項，而所有指數不相同的那些項均復制到“和多項式”中。由于求解結果中多項式的項數是無法預知的，且從提高空間利用率方面考慮，顯然應采用鏈式存儲結構。多項式的鏈式存儲結構中的每一個系數非零項對應一個結點，每個結點的結構如圖2-29所示。結點包含有三個域：其中coef數據域用來存放非零項的系數，expn數據域用來存放非零項的指數，而next指針域用來存放下一個非零項的結點地址。

多項式的鏈表結點類型定義：

        typedef struct PolyNode{   //項的表示
            float coef；          //系數
            int   expn；          //指數
            struct  PolyNode  *next；
        }PolyNode，*PolyNomial；

下面用帶頭結點的有序單鏈表來實現一元多項式的存儲。例如：對于兩個一元多項式a（x）=2+3x+5x3+2x4-7x9，b（x）=1-3x+4x2+7x3，它們的鏈式存儲結構如圖2-30所示。

兩個多項式相加的結果可用圖2-31來描述，其中有“×”標志的結點是相加后被刪除的結點。

多項式相加運算的實現方法類似于例2-8中對兩個有序單鏈表的合并方法。在運算過程中需引進三個工作指針：p，q和r。其中p，q分別指向兩個多項式鏈中待比較的結點，其初始分別指向兩個鏈表的首結點，r始終指向“和多項式”的當前尾結點。

【算法2-29】例2-10中一元多項式加法運算的設計算法

      Status PolyAdd（PolyNomial&La，PolyNomial Lb）
      //  求多項式加法La=La+Lb：利用兩個多項式的結點構成“和多項式”，并用La返回結果
      {  float sum；
          PolyNomial r=La；            //r用于指向新形成鏈表的尾結點r
          PolyNomial p=La-＞next；      //p指向La的第一個結點
          PolyNomial q=Lb-＞next；      //q指向La的第一個結點
          PolyNomial temp；
          while（p&&q）
          {  if（p-＞expn＜q-＞expn）  //p的指數小于q的指數
              { r-＞next=p；          //p加入和多項式的尾部
                r=p；                //r指向當前和多項式的尾結點
                p=p-＞next；          //p后移
              }
              else if（p-＞expn＞q-＞expn）//q的指數小于p的指數
              { r-＞next=q；          //q加入和多項式的尾部
                r=q；                //r指向當前和多項式的尾結點
                q=q-＞next；          //q后移
              }
              else                      //指數相等
              {  sum=p-＞coef+q-＞coef；
                  if（sum!=0）
                  {  p-＞coef=sum；    //和寫入p的系數域
                      r-＞next=p；     //p加入和多項式的尾部
                      r=p；            //r指向當前和多項式的尾結點
                      p=p-＞next；     //p后移
                      temp=q；         //q為待刪除的結點
                      q=q-＞next；     //q后移
                      free（temp）；      //刪除q

                    }
                    else                  //和為零，p與q都刪除，且實現p，q都后移
                    {  temp=p-＞next；
                        free（p）；
                        p=temp；
                        temp=q-＞next；
                        free（q）；
                        q=temp；
                    }
                }
            }//while
            r-＞next=（p!=NULL）? p：q；   //將La或Lb中剩余的結點鏈接到和多項式的尾部
            free（Lb）；                    //釋放Lb的頭結點
            return OK；
        }//算法2-29 結束

此算法的時間復雜度為O（ListLength（La）+ListLength（Lb））。

【綜合應用思考】分別采用順序存儲和鏈式存儲，完成學生成績管理系統的設計與實現。該系統應至少具有增、刪、查、改的功能。學生成績表的結構如表2-3所示。

【提示】由表2-3可知，表中的數據元素是由學號、姓名、性別、大學英語和高等數學等5個數據項所構成的，所以可將數據元素類型具體定義為

      typedef struct{
            int number；         //學號
            char name[10]；      //姓名
            char sex；           //性別（W/M）
            float english；      //大學英語
            float math；         //高等數學
      }ElemType；

成績表采用何種存儲結構，它的基本操作的實現方法就與前面討論過的對應存儲結構上基本操作的實現方法相同，只不過現在將前面的數據元素類型具體化為一個學生的成績記錄。