2.4 順序表與鏈表的比較

順序表和鏈表是線性表在計算機中的兩種基本實現形式，其中鏈表除上述討論的幾種形式之外，還可能會有更多的變化形式。但無論是已經討論過的，還是其他未涉及的方法中，沒有一種方法可稱得上是絕對最好的。因它們都有各自的特點和優、缺點，具體如表2-2所示。

在實際中，需要根據具體的應用來決定線性表應選擇采用何種存儲結構。當線性表的長度或存儲規模難以估計時，不宜采用順序表。另外，當線性表經常需要實現插入操作和刪除操作時，也不宜采用順序表。而當需要經常對線性表進行按位訪問，且讀操作比插入與刪除操作的頻率更多時，則不宜采用鏈表。

與順序表相比較，鏈表比較靈活，它既不要求在一塊連續的存儲空間中存儲線性表的所有數據元素，也不要求按其邏輯順序來分配存儲單元，可根據需要進行空間的動態分配，即不需要預先分配“足夠應用”的連續的存儲空間。因此，當線性表的長度變化較大或長度難以估計時，宜用鏈表；但在線性表的長度基本可預計且變化較小的情況下，宜用順序表，因順序表的存儲密度較鏈表的高。

在順序表中按序號訪問第i個數據元素的時間復雜度為O（1），而在鏈表中做同樣的操作時的時間復雜度為O（n）。所以若要經常對線性表按序號訪問數據元素時，順序表要優先于鏈表。但在順序表上進行插入操作和刪除操作時，需要平均移動近一半的數據元素，而在鏈表上做插入操作和刪除操作，不需要移動任何數據元素，雖然在鏈表上需要先查找到插入或刪除數據元素的位置，但查找主要是比較操作，所以從這個角度考慮，鏈表要優先于順序表。

總之，鏈表比較靈活，插入操作和刪除操作的效率較高，但鏈表的存儲密度較低，適合實現動態的線性表；順序表實現比較簡單，因為任何高級程序語言中都有數組類型，并且空間利用率也較高，可高效地進行隨機存取，但順序表不易擴充，插入操作和刪除操作的效率較低，適合實現相對“穩定”的靜態線性表。兩種存儲結構各有所長，各種實現方法也不是一成不變的。在實際應用時，必須以這些基本方法和思想為基礎，抓住兩者各自的特點并結合具體情況，加以創造性地靈活應用和改造，用最合適的方法來解決問題。

【例2-9】Josephus問題：Josephus問題建立在歷史學家Joseph ben Matthias（稱為“Josephus”）的一個報告的基礎上，該報告講述了他和40個士兵在公元67年被羅馬軍包圍期間簽訂的一人自殺協定。Josephus建議每個人殺死他的鄰居，他很聰明地使自己成為這些人中的最后一個，因此獲得生還。請編程完成對該問題使用8人士兵時的情況進行模擬。

【分析】本題涉及的主要知識點是在循環單鏈表上實現建立、查找、插入、刪除等基本操作。首先考慮應該采用的存儲結構。根據題目中對Josephus問題的描述，程序要處理的對象可以看成是由8個士兵組成的線性表；又由于每個人要殺死他的鄰居，則要保證每個人都要有鄰居，為此宜采用循環的存儲結構。殺死鄰居的操作可以看作是對線性表中數據元素進行刪除操作，而且此操作是解決此問題的關鍵操作，所以宜采用鏈式存儲而不宜用順序存儲。現假定本題中采用單循環鏈表L來解決問題。為處理問題方便，先給出了實現插入Insert（&L，i，x）、刪除Delete（&L，i）、求長度Length（L）、讀取指定元素Get（L，i）和輸出Display（L）等的操作算法，在此前提下再來解決Josephus問題就比較簡單。先利用插入操作創建一個帶頭結點的循環單鏈表，鏈表中依次存放著各士兵信息，在此以字母A，B，…，H代替。然后，再從單循環鏈表的某個指定的結點開始，依次去刪除其相鄰的結點，直到鏈表中只剩下一個結點為止。圖2-27是該問題從第1個士兵開始對8個士兵的情況模擬。

【程序參考代碼】

        #include＜stdio.h＞
        #include＜malloc.h＞
        #define ERROR 0
        #define OK 1
        typedef char ElemType；                //自定義數據元素類型為字符型
        typedef bool Status；                  //自定義函數類型為布爾型
        typedef struct LNode
        {   ElemType data；
            struct LNode *next；
        }LNode，*LinkList；
        Status Init（LinkList&L）              //初始化操作算法
        //創建一個帶頭結點的空循環單鏈表L
        {  L=（LinkList）malloc（sizeof（LNode））； //為頭結點分配空間，并使L指針指向它
            if（!L）                         //空間分配失敗
              return ERROR；
            L-＞next=L；
            return OK；
        }//Init

    int Length（LinkList L）               //求長度的操作算法
    //返回帶頭結點的循環單鏈表中數據的個數
    {  int length=0；
        LinkList p=L-＞next；             //p指針指向鏈表中第一個元素結點
        while（p!=L）
        {length++；                     //長度加 1
          p=p-＞next；                  //p指針后移
        }
        return length；
    }//Length
    Status Get（LinkList L，int i，ElemType&e）//取第i個元素的操作算法
    //讀取帶頭結點的循環單鏈表L中的第i個數據元素，并用e返回其值
    {  LinkList p=L-＞next；             //p指針指示鏈表中的第一個元素結點
        int j=1；                       //j指示p指針所指向的結點在表中的位序號
        while（p!=L&&j＜i）
        {   p=p-＞next；
           ++j；
        }
        if（p=L‖j＞i）                 //i不合法
            return ERROR；
        e=p-＞data；
        return OK；
    }//Get
    Status Insert（LinkList&L，int i，ElemType e）//插入操作算法
    //在循環單鏈表L的第i個數據元素之前插入值為e的數據元素
    {  LinkList p=L，s；                 //p指針指示鏈表中的頭結點
        int j=0；                       //j指示p指針所指向的結點在表中的位序號
        while（（p!=L||j==0）&&j＜i-1）//確定第i個元素的前驅結點，并用p指針指示它
        {    p=p-＞next；
             ++j；
        }
        if（j!=i-1）                  //i不合法
          return ERROR；
        s=（LinkList）malloc（sizeof（LNode））；//產生新的結點
        s-＞data=e；
        s-＞next=p-＞next；              //修改鏈，讓新結點插入第i-1個元素結點p的后面
        p-＞next=s；
        return OK；
    }//Insert
    Status Delete（LinkList&L，int i，ElemType&e）//刪除操作算法
    //刪除帶頭結點的循環單鏈表L中的第i個數據元素，并用e返回其值
    {  LinkList p=L，q；                 //p指針指示鏈表中的頭結點
        int j=0；                       //j指示p指針所指向的結點在表中的位序號

        while（（p-＞next!=L||j==0）&&j＜i-1）
        { p=p-＞next；
         ++j；
        }
        if（p-＞next=L‖j＞i-1）         //i不合法
          return ERROR；
        q=p-＞next；                    //q指向待刪結點
        p-＞next=q-＞next；              //修改鏈讓待刪結點從鏈中脫離出來
        e=q-＞data；                    //用e保存待刪結點的數據元素值
        free（q）；                        //釋放待刪結點空間
        return OK；
    }//Delete
    Status Josephus（LinkList L，int i）      //Josephus問題模擬求解算法
    //參數i是開始自殺的士兵在表中的位置
    {    char s1，s2；
          int h；
          while（（h=Length（L））＞ 1）
          {
            i=i%（h+1）；               //求出該士兵在鏈表的位序號
            if（i==0）                  //跳過 0 號，因位序號是從 1 開始編號的
              i++；
            Get（L，i，s1）；                 //讀取到鏈表中位序號為i的士兵信息
            i=++i%（h+1）；             //求出相鄰士兵在鏈表中的位序號
            if（i==0）                  //跳過 0 號
              i++；
            Delete（L，i，s2）；               //殺死相鄰的士兵
            printf（"%c殺死%c\n"，s1，s2）；
          }
          printf（"最后存活的士兵是%C\n"，L-＞next-＞data）；
          return OK；
    }//Josephus
    void Display（LinkList L）             //輸出操作算法
    //輸出帶頭結點的循環單鏈表L中各數據元素值
    {  LinkList p=L-＞next；
        while（p!=L）
        { printf（"%4c"，p-＞data）；
          p=p-＞next；
        }
        printf（"\n"）；
    }//Display
    int main（　）                          //測試程序的主函數
    {   LinkList L；
         int num，i；

            char s；
            Init（L）；                        //創建一個帶頭結點的空循環單鏈表
            printf（"請輸入士兵的人數num："）；
            scanf（"%d"，&num）；
            getchar（　）；                      //跳過回車
            printf（"按順序輸入%d個士兵信息（＇A＇-＇H＇）："，num）；
            for（i=1；i ＜=num；i++）       //輸入num個士兵，并將士兵結點插入循環鏈表
            {  scanf（"%c"，&s）；
                Insert（L，i，s）；
            }
           printf（"%d個士兵是："，num）；
           Display（L）；                     //輸出士兵在鏈表中的信息
           printf（"輸入開始自殺的士兵在表中的位置（1-num）："）；
           scanf（"%d"，&i）；
           Josephus（L，i）；                  //Josephus問題模擬求解
        }//main

【運行結果】運行結果如圖2-28所示。