3.4 應用實例

3.4.1 約瑟夫環(huán)問題

本章的引言部分給出了約瑟夫環(huán)問題及其數(shù)據(jù)模型，下面考慮算法設計與程序實現(xiàn)。

【算法】 由于約瑟夫環(huán)問題本身具有循環(huán)性質，考慮采用循環(huán)單鏈表。約瑟夫環(huán)問題的基本思想是設置一個計數(shù)器count和工作指針p，當計數(shù)器累加到m時刪除結點p。為了統(tǒng)一對表中任意結點的操作，循環(huán)單鏈表不帶頭結點；為了便于刪除操作，設兩個工作指針為pre和p，pre指向結點p的前驅結點；為了使計數(shù)器從1開始計數(shù)，采用尾指針指示的循環(huán)單鏈表，將pre初始化為指向終端結點，將p初始化為指向開始結點，如圖3-33所示。

圖3-33 約瑟夫環(huán)的初始狀態(tài)

用函數(shù)Joseph求解約瑟夫環(huán)問題，算法用偽代碼描述如下 ：

【程序】 主函數(shù)首先輸入約瑟夫環(huán)的長度n和密碼m，然后調用函數(shù)Creat建立由尾指針rear指示的循環(huán)單鏈表，最后調用函數(shù)Joseph打印出環(huán)的順序。程序如下：

            #include＜stdio.h＞                         //使用庫函數(shù)printf和scanf
            #include＜malloc.h＞                        //使用malloc等庫函數(shù)實現(xiàn)動態(tài)存儲分配
            typedefstructNode                           //定義單鏈表的結點Node
            {
                  intdata；
                  structNode*next；
            }Node；
            Node*Creat（intn）；                        //函數(shù)聲明，構造尾指針指示的約瑟夫環(huán)
            voidJoseph（Node*rear，intm）；             //函數(shù)聲明，打印出環(huán)的順序
                                                        //以下是主函數(shù)
            intmain（）
            {
                  intn，m；
                  Node*rear=NULL；                      //定義尾指針rear并初始化為空
                  printf（＂請輸入約瑟夫環(huán)的長度：＂）；//輸出提示信息
                  scanf（＂%d＂，&n）；
                  printf（＂請輸入密碼：＂）；          //輸出提示信息
                  scanf（＂%d＂，&m）；
                  rear=Creat（n）；                     //函數(shù)調用，返回的尾指針賦給rear
                  Joseph（rear，m）；                   //函數(shù)調用，實參rear是尾指針
                  return0；                             //將0返回操作系統(tǒng)，表明程序正常結束
            }

                                                        //以下是其他函數(shù)定義
            Node*Creat（intn）                          //函數(shù)定義，返回值是循環(huán)單鏈表的尾指針
            {
                  Node*rear=NULL，*s；                  //定義尾指針rear并初始化為空
                  inti；
                  rear=（Node*）malloc（sizeof（Node））;//申請結點，rear指向該結點
                  rear-＞data=1；                        //結點rear的數(shù)據(jù)域為1
                  rear-＞next=rear；                     //建立長度為1的循環(huán)單鏈表
                  for（i=2；i＜=n；i++）                 //依次插入數(shù)據(jù)域為2，3，…，n的結點
                  {
                      s=（Node*）malloc（sizeof（Node））;//申請結點，s指向該結點
                      s-＞data=i；                        //結點s的數(shù)據(jù)域為i
                      s-＞next=rear-＞next；              //將結點s插入尾結點rear的后面
                      rear-＞next=s；
                      rear=s；                            //指針rear指向當前的尾結點
                  }
                  returnrear；                            //結束函數(shù)的執(zhí)行，并將尾指針rear返回到調用處
            }
            voidJoseph（Node*rear，intm）
            {                   //函數(shù)定義，形參rear為循環(huán)單鏈表的尾指針，形參m為密碼
                  Node*pre=rear，*p=rear-＞next，*q；     //初始化工作指針p和pre
                  intcount=1；                            //初始化計數(shù)器count
                  printf（＂出環(huán)的順序是：＂）；
                  while（p-＞next！=p）                   //循環(huán)，直到循環(huán)鏈表中只剩一個結點
                  {
                      if（count＜m）                      //計數(shù)器未累加到密碼值
                      {
                  pre=p；p=p-＞next；                     //將工作指針pre和p分別后移
                  count++；                               //計數(shù)器加1
                      }
                      else                                //計數(shù)器已經累加到密碼值
                      {
                  printf（＂%-3d＂，p-＞data）；          //寬度3位左對齊打印出環(huán)的編號
                  q=p；                                   //指針q暫存即將刪除的結點
                  pre-＞next=p-＞next；                   //將結點p摘鏈
                  p=pre-＞next；                          //工作指針p后移，但pre不動
                  free（q）；                             //釋放指針q指向的存儲單元
                  count=1；                               //計數(shù)器從1開始重新計數(shù)
                      }
                  }
                  printf（＂%-3d\n＂，p-＞data）；        //寬度3位左對齊輸出最后一個結點的編號
                  free（p）；                             //釋放最后一個結點
                  return；                                //結束函數(shù)Joseph的執(zhí)行
            }

3.4.2 一元多項式求和

【問題】 設A（x）=a0+a1x+a2x2+…+anxn，B（x）=b0+b1x+b2x2+…+bmxm，并且多項式的指數(shù)可能很高且變化很大，例如：A（x）=7+12x3-2x8+5x12，B（x）=4x+6x3+2x8+5x20+7x28，求兩個一元多項式的和，即求A（x）+B（x）。

【想法】 由于一元多項式A（x）=a0+a1x+a2x2+…+anxn由n+1個系數(shù)唯一確定，因此，可以用一個線性表（a0，a1，a2，…，an）來表示，每一項的指數(shù)i隱含在其系數(shù)ai的序號里。如果多項式的指數(shù)可能很高且變化很大，則一元多項式對應的線性表中就會存在很多零元素。一個較好的存儲方法是只存儲非零項，但是需要在存儲非零系數(shù)的同時存儲相應的指數(shù)。這樣，一元多項式的每一個非零項可由系數(shù)和指數(shù)唯一表示。例如，一元多項式A（x）=7+12x3-2x8+5x12就可以用線性表（（7，0），（12，3），（-2，8），（5，12））來表示。

由數(shù)學知識，一元多項式求和實質上是合并同類項的過程，也就是將兩個一元多項式對應的線性表進行合并的過程。例如，A（x）=7+12x3-2x8+5x12和B（x）=4x+6x3+2x8+5x20+7x28的求和，即是將線性表（（7，0），（12，3），（-2，8），（5，12））和（（4，1），（6，3），（2，8），（5，20），（7，28））進行合并，結果為（（7，0），（4，1），（18，3），（5，12），（5，20），（7，28））。

【算法】 如何存儲多項式對應的線性表呢？對于指數(shù)相差很多的兩個一元多項式，相加會改變多項式的系數(shù)和指數(shù)。若相加的某兩項的指數(shù)不等，則兩項應分別加在結果中，將引起線性表的插入；若某兩項的指數(shù)相等，則系數(shù)相加，若相加結果為零，將引起線性表的刪除。由于在線性表的合并過程中需要頻繁地執(zhí)行插入和刪除操作，因此考慮采用單鏈表存儲。

在表示一元多項式的單鏈表中，每一個非零項對應單鏈表中的一個結點，且單鏈表應按指數(shù)遞增有序排列。結點結構如圖3-34所示。其中

圖3-34 一元多項式鏈表的結點結構

coef：系數(shù)域，存放非零項的系數(shù)；

exp：指數(shù)域，存放非零項的指數(shù)；

next：指針域，存放指向下一結點的指針。

下面分析多項式求和的執(zhí)行過程。設單鏈表A和B分別存儲兩個多項式，求和結果存儲在單鏈表A中，設兩個工作指針p和q分別指向兩個單鏈表的開始結點。兩個多項式求和實質上是對結點p的指數(shù)域和結點q的指數(shù)域進行比較，有下列三種情況：

（1）若p-＞exp小于q-＞exp，則結點p應為結果鏈表中的一個結點，將指針p后移，如圖3-35所示。

圖3-35 第一種情況示意圖

（2）若p-＞exp大于q-＞exp，則結點q應為結果中的一個結點，將q插入到第一個單鏈表中結點p之前，并將指針q指向單鏈表B中的下一個結點，如圖3-36所示。為此，在單鏈表A中應該設置兩個工作指針pre和p，使得pre指向p的前驅結點。

圖3-36 第二種情況示意圖

（3）若p-＞exp等于q-＞exp，則p與q所指為同類項，將q的系數(shù)加到p的系數(shù)上。若相加結果不為0，則將指針p后移，并刪除結點q，為此，在單鏈表B中應該設置兩個工作指針qre和q，使得qre指向q的前驅結點，如圖3-37（a）所示；若相加結果為0，則表明結果中無此項，刪除結點p和結點q，并將指針p和指針q分別后移，如圖3-37（b）所示。

圖3-37 第三種情況示意圖

綜合上述三種情況，一元多項式相加算法用偽代碼描述如下 ：

【程序】 主函數(shù)首先接收從鍵盤輸入的一元多項式各項的系數(shù)和指數(shù)，分別建立多項式A（x）和B（x），然后調用函數(shù)AddPolynomial實現(xiàn)兩個一元多項式相加，最后調用函數(shù)Print打印相加結果。程序如下：

            #include＜stdio.h＞                       //使用庫函數(shù)printf和scanf
            #include＜malloc.h＞                      //使用malloc等庫函數(shù)實現(xiàn)動態(tài)存儲分配
            typedefstructNode                         //定義單鏈表結點
            {
                  intcoef，exp；                      //coef表示系數(shù)，exp表示指數(shù)
                  structNode*next；
            }Node；
            Node*AddPolynomial（Node*A，Node*B）；    //函數(shù)聲明，多項式相加
            Node*Creat（）；                          //函數(shù)聲明，建立單鏈表表示一元多項式
            voidPrint（Node*first）；                 //函數(shù)聲明，打印一元多項式
                                                      //空行，以下為主函數(shù)
            intmain（）
            {
                  Node*A=NULL，*B=NULL；
                  A=Creat（）；Print（A）；           //輸入多項式A（x）建立單鏈表，頭指針為A
                  B=Creat（）；Print（B）；           //輸入多項式B（x）建立單鏈表，頭指針為B
                  A=AddPolynomial（A，B）；           //相加結果為頭指針A指示的單鏈表
                  printf（＂結果是：＂）；
                  Print（A）；                        //輸出單鏈表A，即相加結果
                  return0；                           //將0返回操作系統(tǒng)，表明程序正常結束
            }
                                                      //以下是其他函數(shù)定義
            Node*Creat（）                            //建立單鏈表，返回頭指針
            {
                  Node*first=NULL，*r=NULL，*s=NULL；
                  intcoef，exp；
                  first=（Node*）malloc（sizeof（Node））;//申請頭結點
                  r=first；                               //尾插法建立單鏈表
                  printf（＂請輸入系數(shù)和指數(shù)：＂）；
                  scanf（＂%d%d＂，&coef，&exp）；        //輸入第一項的系數(shù)和指數(shù)
                  while（coef！=0）                       //循環(huán)結束的條件是輸入系數(shù)為0
                  {
                      s=（Node*）malloc（sizeof（Node））；
                      s-＞coef=coef；s-＞exp=exp；
                      r-＞next=s；r=s；                   //將結點s插入單鏈表的尾部
                      printf（＂請輸入系數(shù)和指數(shù)：＂）；
                      scanf（＂%d%d＂，&coef，&exp）；
                  }
                  r-＞next=NULL；                         //置單鏈表的尾標志
                  returnfirst；                           //結束函數(shù)的執(zhí)行并返回頭指針

            }
            Node*AddPolynomial（Node*A，Node*B）
            {                                             //多項式相加，頭指針分別為A和B
                  Node*pre=A，*p=pre-＞next；             //工作指針pre和p初始化
                  Node*qre=B，*q=qre-＞next；             //工作指針qre和q初始化
                  Node*v=NULL；
                  while（p！=NULL&&q！=NULL）
                  {
                      if（p-＞exp＜q-＞exp）              //第1種情況
                      {
                  pre=p；p=p-＞next；
                      }
                      elseif（p-＞exp＞q-＞exp）         //第2種情況
                  {
                            v=q-＞next；
                            pre-＞next=q；               //將結點q插入到結點p之前
                            q-＞next=p；
                            q=v；
                  }
                  else                                   //第3種情況
                  {
                            p-＞coef=p-＞coef+q-＞coef； //系數(shù)相加
                            if（p-＞coef==0）            //系數(shù)為0
                            {
                                pre-＞next=p-＞next；    //則刪除結點p
                                free（p）；
                                p=pre-＞next；
                            }
                            else                         //系數(shù)不為0
                            {
                                pre=p；p=p-＞next；
                            }
                            qre-＞next=q-＞next；       //第3種情況都要刪除結點q
                            free（q）；
                            q=qre-＞next；
                  }
                  }
                  if（q！=NULL）pre-＞next=q；          //將結點q鏈接在第一個單鏈表的后面
                  free（B）；                           //釋放第二個單鏈表的頭結點所占的內存
                  returnA；
            }
            voidPrint（Node*first）
            {
                  Node*p=first-＞next；

                  if（p！=NULL）                        //輸出第一項
                      printf（＂%dx%d＂，p-＞coef，p-＞exp）；
                  p=p-＞next；
                  while（p！=NULL）
                  {
                      if（p-＞coef＞0）                 //輸出系數(shù)的正號或負號
                  printf（＂+%dx%d＂，p-＞coef，p-＞exp）；
                      else
                  printf（＂%dx%d＂，p-＞coef，p-＞exp）；
                      p=p-＞next；
                  }
                  printf（＂\n＂）；
            }