2.3 線性表的鏈式存儲及其操作的實現

由于順序表的存儲特點是用物理上的相鄰關系實現邏輯上的相鄰關系，它要求用連續的存儲單元順序存儲線性表中各元素，因此，在對順序表插入、刪除時，需要通過移動數據元素來實現，影響了運行效率。本節介紹線性表的鏈式存儲結構，它不需要用地址連續的存儲單元來實現，因為它不要求邏輯上相鄰的兩個數據元素在物理上也相鄰。在鏈式存儲結構中，數據元素之間的邏輯關系是通過“鏈”來連接的，因此對線性表的插入、刪除不需要移動數據元素。

2.3.1 單鏈表

鏈表是通過一組任意的存儲單元來存儲線性表中的數據元素的，那么怎樣表示數據元素之間的線性關系呢？即如何來“鏈”接數據元素間的邏輯關系呢？為此在存儲數據元素時，對每個數據元素ai，除了存放數據元素的自身信息ai之外，還需要和ai一起存放其后繼數據元素ai+1所在的存儲單元的地址，這兩部分信息組成一個“結點”，結點的結構如圖2.6所示，每個數據元素都如此。存放數據元素自身信息的單元稱為數據域，存放其后繼元素地址的單元稱為指針域。因此n個元素的線性表通過每個結點的指針域拉成了一個“鏈子”，稱之為鏈表。如圖2.6所示，每個結點中只有一個指向后繼的指針，所示稱其為單鏈表。

鏈表是由結點構成的，結點定義如下：

typedef struct node
{ datatype data;                /*存放數據元素*/
           struct node *next;   /*存放下一個結點的地址*/
} LNode *LinkList；

定義頭指針變量：

LinkList H；

如圖2.7所示是線性表（a1, a2, a3, a4, a5, a6, a7, a8）對應的鏈式存儲結構示意圖。

當然，必須將第一個結點的地址160放到一個指針變量中，如H中，最后一個結點沒有后繼，其指針域必須置空（即NULL），表明此表到此結束，這樣就可以從第一個結點的地址開始“順藤摸瓜”，找到表中的每個結點。

作為線性表的一種存儲結構，人們關心的是結點間的邏輯結構，而并不關心每個結點的實際地址，所以通常的單鏈表用圖2.8的形式表示而不用圖2.7的形式表示，其中，符號∧表示空指針（下同）。

實際應用中通常用“頭指針”來標識一個單鏈表，如單鏈表L、單鏈表H等，是指某鏈表的第一個結點的地址放在指針變量L、H中，頭指針為“NULL”則表示一個空表。

需要進一步指出的是：上面定義的LNode是結點的類型，LinkList是指向LNode類型結點的指針類型。為了增強程序的可讀性，通常將標識一個鏈表的頭指針定義為LinkList類型的變量，如LinkList L。當L有定義時，值要么為NULL（表示一個空表），要么為第一個結點的地址，即鏈表的頭指針。將操作中用到指向某結點的指針變量說明為：LNode *類型，如

LNode *p；

則語句p=malloc(sizeof(LNode));完成了申請一塊 LNode 類型的存儲單元的操作，并將其地址賦值給指針變量p。如圖2.9所示，p所指的結點為*p，*p的類型為LNode型，所以該結點的數據域為(*p).data或p->data，指針域為(*p).next或p->next，而語句free(p);則表示釋放p所指的結點。

2.3.2 單鏈表基本操作的實現

1.建立單鏈表

（1）在鏈表的頭部插入結點建立單鏈表

鏈表與順序表不同，它是一種動態管理的存儲結構，鏈表中的每個結點占用的存儲空間不是預先分配的，而是運行時系統根據需求生成的，因此建立單鏈表要從空表開始，每讀入一個數據元素則申請一個結點，然后插在鏈表的頭部，如圖2.10展現了線性表（25, 45, 18, 76, 29）的鏈表的建立過程，因為是在鏈表的頭部插入，讀入數據的順序和線性表中的邏輯順序是相反的。

算法2.7 單鏈表的建立算法（頭部插入）。

LinkList Creat_LinkList1( )
     {  LinkList L=NULL；                   /*空表L為表頭*/
        LNode *s;
        int x;                              /*設數據元素的類型為int */
        scanf("%d", &x);
        while (x!=flag)                     /*設flag為數據元素輸入結束的標志*/
          { s=malloc(sizeof(LNode));        /*為插入元素申請空間*/
            s->data=x;                      /*將插入元素置入申請到的單元中*/
            s->next=L; L=s;
            scanf ("%d", &x);
           }
        return L;
}

（2）在單鏈表的尾部插入結點建立單鏈表

頭部插入建立單鏈表簡單，但讀入的數據元素的順序與生成的鏈表中元素的順序是相反的，若希望次序一致，則用尾部插入的方法。因為每次操作都是將新結點插入到鏈表的尾部，所以需加入一個指針 R 用來始終指向鏈表中的尾結點。如圖2.11展現了在鏈表尾部插入結點建立鏈表的過程。

算法思路：初始狀態時，頭指針H=NULL，尾指針R=NULL，按線性表中元素的順序依次讀入數據元素，不是結束標志時，申請結點，將新結點插入到R所指結點的后面，然后R指向新結點（但第一個結點有所不同，讀者注意下面算法中的有關部分）。

算法2.8 單鏈表的建立算法（尾部插入）。

LinkList Creat_LinkList2( )
   { LinkList L=NULL;
         LNode *s, *R=NULL;
         int x;                                   /* 設數據元素的類型為int */
         scanf("%d", &x);
         while (x!=flag)                          /* 設flag為數據元素輸入結束的標志 */
            { s=malloc(sizeof(LNode)); s->data=x; /*申請空間并將插入元素置入該單元*/
              if (L==NULL) L=s;                   /*第一個結點的處理*/
             else R->next=s;                      /*其他結點的處理*/
             R=s;                                 /*R指向新的尾結點*/
             scanf("%d", &x);
          }
        if ( R!=NULL) R->next=NULL;               /*對于非空表，最后結點的指針域放空指針*/
        return L;
}

（3）在帶頭結點單鏈表的表尾插入元素建立單鏈表

在上面的算法中，第一個結點的處理和其他結點是不同的，原因是第一個結點加入時鏈表為空，它沒有直接前趨結點，它的地址就是整個鏈表的指針，需要放在鏈表的頭指針變量中；而其他結點有直接前趨結點，其地址放入直接前趨結點的指針域。“第一個結點”的問題在很多操作中都會遇到，如在鏈表中插入結點時，將結點插在第一個位置和其他位置是不同的，在鏈表中刪除結點時，刪除第一個結點和其他結點的處理也是不同的。

為了方便操作，有時在鏈表的頭部加入一個“頭結點”，頭結點的類型與數據結點一致，標識鏈表的頭指針變量L中存放該結點的地址，這樣即使是空表，頭指針變量L也不為空了。頭結點的加入使得“第一個結點”的問題不再存在，也使得“空表”和“非空表”的處理一致。

頭結點的加入完全是為了操作的方便，它的數據域無定義，指針域中存放的是第一個數據結點的地址，當空表時該指針域為空。

圖2.12（a）和圖2.12（b）分別是帶頭結點的單鏈表空表和非空表的示意圖。

算法2.9 帶頭結點的單鏈表的建立算法。

LinkList Creat_LinkList3( )
    { LinkList L;
    LNode *R;
    int x;                                  /*設數據元素的類型為int */
    L=（LinkList）malloc(sizeof(Lnode));    /*申請頭結點空間 */
    L->next=NULL；                          /*初始化，置空表*/
    R=L；
    scanf("%d", &x);
    while (x!=flag)
        { R->next=malloc(sizeof(LNode));    /*為插入元素申請空間*/
          R->next->data=x ；                /*將插入元素置入該單元*/
          R=R->next;                        /*R指向新的尾結點*/
          scanf("%d", &x);
        }
      R->next=NULL；                        /*置表尾結點的next指針為空*/
      return L;
}

2.求表長

算法思路：設一個移動指針p和計數器j，初始化后，p所指結點后面若還有結點，p向后移動，計數器加1。

（1）設L是帶頭結點的單鏈表（線性表的長度不包括頭結點）。

算法2.10 求帶頭結點單鏈表的長度算法。

int Length_LinkList1(LinkList L)
   { LNode *p=L;                  /* p指向頭結點*/
     int j=0;
     while (p->next)
          { p=p->next; j++ }      /* p所指的是第j個結點*/
     return j;
}

（2）設L是不帶頭結點的單鏈表。

算法2.11 求不帶頭結點單鏈表的長度算法。

int Length_LinkList2 (LinkList L)
    { LNode *p=L;
      int j;
      if (p==NULL) return 0;      /*空表的情況*/
      j=1;                        /*在非空表的情況下，p所指的是第一個結點*/
      while (p->next )
            { p=p->next; j++ }
      return j;
}

從上面兩個算法中看到，不帶頭結點的單鏈表空表情況要單獨處理，而帶上頭結點之后則不用了。在以后的算法中不加說明則認為單鏈表是帶頭結點的。這兩個算法的時間復雜度均為O(n)。

3.查找操作

（1）按序號查找Get_LinkList(L, i)。

算法思路：從鏈表的第一個元素結點起，判斷當前結點是否是第i個，若是，則返回該結點的指針，否則繼續查找下一個結點，直到表結束為止。若沒有第i個結點，則返回空指針。

算法2.12 單鏈表按序號查找元素算法。

LNode *Get_LinkList(LinkList L, Int i);
                    /*在單鏈表L中查找第i個元素結點，找到返回其指針，否則返回空指針*/
    { LNode *p=L;
      int j=0;
      while (p->next !=NULL && j<i )
          { p=p->next;  j++; }
      if (j==i) return p;
       else return NULL;
}

（2）按值查找即定位 Locate_LinkList(L, x)。

算法思路：從鏈表的第一個元素結點起，判斷當前結點的值是否等于x，若是，則返回該結點的指針，否則繼續查找下一結點，直到表結束為止。若沒有找到值為x的結點，則返回空指針。

算法2.13 單鏈表的元素定位算法。

LNode *Locate_LinkList( LinkList L, datatype x)
                   /*在單鏈表L中查找值為x的結點，找到后返回其指針，否則返回空指針*/
    { LNode *p=L->next;
      while ( p!=NULL && p->data != x)
          p=p->next;
      return p;
    }

上述兩算法的時間復雜度均為O(n)。

4.插入操作

（1）后插結點：設p指向單鏈表中某結點，s指向待插入的值為X的新結點，將*s插入到*p的后面，插入示意圖如圖2.13所示。

操作如下：

① s->next=p->next;

② p->next=s;

注意：兩個指針的操作順序不能交換。

（2）前插結點：設p指向鏈表中某結點，s指向待插入的值為X的新結點，將*s插入到*p的前面，插入示意圖如圖2.14所示，與后插不同的是：首先要找到*p的前趨*q，然后完成在*q之后插入*s，設單鏈表頭指針為L，操作如下：

q=L;
① while (q->next!=p)
        q=q->next;    /*找*p的前趨*/
② s->next=q->next;
③ q->next=s;

后插操作的時間復雜度為O(1)，前插操作因為要找*p的前趨，時間復雜度為O(n)；其實人們關心的是數據元素之間的邏輯關系，所以仍然可以將*s插入到*p的后面，然后將p->data與s->data交換即可，這樣既滿足了邏輯關系，又能使得時間復雜度為O(1)。

（3）插入運算Insert_LinkList(L, i, x)。

算法思路：

① 找到第i-1個結點；若存在則繼續步驟②，否則結束；

② 申請、填裝新結點；

③ 將新結點插入，結束。

算法2.14 單鏈表的元素插入算法。

int Insert_LinkList( LinkList L, int i, datatype x)
                                         /*在單鏈表L的第i個位置上插入值為x的元素*/
{ LNode * p, *s;
  p=Get_LinkList(L, i-1);                     /*查找第i-1個結點*/
  if (p==NULL)
        { printf("參數i錯")； return 0； }    /*第i-1個點不存在，不能插入*/
   else {
         s=malloc(sizeof(LNode))；            /*申請、填裝結點*/
         s->data=x；
         s->next=p->next；                    /*新結點插入在第i-1個結點的后面*/
         p->next=s；
         return 1；
      }
  }

上述算法的時間復雜度為O(n)。

5.刪除操作

（1）刪除結點：設p指向單鏈表中某結點，刪除*p。其操作示意圖如圖2.15所示。通過示意圖可見，要實現對結點*p的刪除，首先要找到*p的前趨結點*q，然后完成指針的操作即可。刪除結點的操作由下列語句實現：

q->next=p->next;
free(p);

顯然，找*p前趨結點的時間復雜度為O(n)。

若要刪除*p的后繼結點（假設存在），則可以直接完成：

s=p->next;
p->next=s->next;
free(s);

該操作的時間復雜度為O(1) 。

（2）刪除運算：Del_LinkList(L, i)。

算法思路：

① 找到第i-1個結點；若存在則繼續步驟②，否則結束；

② 若存在第i個結點則繼續步驟③，否則結束；

③ 刪除第i個結點，結束。

算法2.15 單鏈表的元素刪除算法。

int Del_LinkList(LinkList L，int i)     /*刪除單鏈表L上的第i個數據結點*/
   { LinkList p, s;
     p=Get_LinkList(L, i-1);            /*查找第i-1個結點*/
     if (p==NULL)
         { printf("第i-1個結點不存在"); return -1; }
     else if (p->next==NULL)
              { printf("第i個結點不存在"); return 0; }
           else
              { s=p->next;              /*s指向第i個結點*/
                p->next=s->next;        /*從鏈表中刪除*/
                free(s);                /*釋放s */
                return 1;
              }
}

算法2.15的時間復雜度為O(n)。

通過上面的基本操作可知：

①在單鏈表上插入、刪除一個結點，必須知道其前趨結點；

②單鏈表不具有按序號隨機訪問的特點，只能從頭指針開始按結點順序進行。

2.3.3 循環鏈表

對于帶頭結點的單鏈表而言，最后一個結點的指針域是空指針，如果將該鏈表頭指針置入該指針域，則使得鏈表頭尾結點相連，就構成了單循環鏈表，如圖2.16所示。

在單循環鏈表上的操作基本與非循環鏈表相同，只是將原來判斷指針是否為NULL變為判斷指針是否為頭指針而已，沒有其他較大的變化。

對于單鏈表，只能從頭結點開始遍歷整個鏈表；而對于單循環鏈表，則可以從表中任意結點開始遍歷整個鏈表。不僅如此，有時對鏈表常做的操作是在表尾、表頭進行的，此時可以改變一下鏈表的標識方法，不用頭指針而用一個指向尾結點的指針R來標識，這樣在許多時候可以提高操作效率。

例如，對兩個單循環鏈表H1、H2的連接操作，是將H2的第一個數據結點接到H1的尾結點，如果用頭指針標識，則需要找到第一個鏈表的尾結點，其時間復雜度為O(n)，而鏈表若用尾指針R1、R2來標識，則時間復雜度為O(1)。操作如下：

p= R1->next;               /*保存R1的頭結點指針*/
R1->next=R2->next->next;   /*頭尾連接*/
free(R2->next);            /*釋放第二個表的頭結點*/
R2->next=p;                /*組成循環鏈表*/

這一過程如圖2.17所示。

2.3.4 雙向鏈表

單鏈表的結點中只有一個指向其后繼結點的指針域next，因此，若已知某結點的指針為p，其后繼結點的指針則為p->next，而找其前趨則只能從該鏈表的頭指針開始，順著各結點的next域進行，也就是說，找后繼的時間復雜度是O(1)，而找前趨的時間復雜度是O(n)，如果希望找前趨的時間復雜度達到O(1)，則只能付出空間的代價：每個結點再加一個指向前趨的指針域，結點的結構如圖2.18所示，用這種結點組成的鏈表稱為雙向鏈表。

雙向鏈表結點的定義如下：

typedef struct dLNode
             { datatype data;
               struct dLNode *prior, *next;
             } DLNode, *DLinkList;

和單鏈表類似，雙向鏈表通常也用頭指針標識，也可以帶頭結點或做成循環結構，圖2.19是帶頭結點的雙向循環鏈表示意圖，顯然，通過某結點的指針p即可以直接得到它的后繼結點的指針p->next，也可以直接得到它的前趨結點的指針p->prior。這樣，在有些操作中需要找前趨時，則不需要再用循環。從下面的插入刪除操作中可以看到這一點。

設p指向雙向循環鏈表中的某一結點，即p中存儲的是該結點的指針，則p->prior->next表示的是*p結點之前趨結點的后繼結點的指針，即與p相等；類似地，p->next->prior表示的是*p結點之后繼結點的前趨結點的指針，也與p相等，所以有以下等式：

p->prior->next=p=p->next->prior

雙向鏈表中結點的插入：設p指向雙向鏈表中某結點，s指向待插入的值為x的新結點，將*s插入到*p的前面，其插入過程如圖2.20所示。

操作如下：

① s->prior=p->prior;

② p->prior->next=s;

③ s->next=p;

④ p->prior=s;

指針操作的順序不是唯一的，但也不是任意的，操作①必須要放到操作④的前面完成，否則*p的前趨結點的指針就丟掉了。讀者把每條指針操作的含義搞清楚，就不難理解了。

雙向鏈表中結點的刪除：設p指向雙向鏈表中某結點，刪除*p。其刪除操作過程如圖2.21所示。

操作如下：

① p->prior->next=p->next;

② p->next->prior=p->prior;

free(p);

2.3.5 單鏈表的其他操作舉例

【例2.4】 已知單鏈表H，寫一算法將其元素倒置，即實現如圖2.22所示的操作，其中圖2.22（a）為倒置前的狀態，圖2.22（b）為倒置后的狀態。

算法思路：依次取原鏈表中的每個結點，將其作為第一個結點插入到新鏈表中去，指針p用來指向當前結點，p為空時結束。

算法2.16 單鏈表的倒置算法。

void reverse ( Linklist H )
    { LNode *p, *q;
      p=H->next;                  /*p指向第一個數據結點*/
      H ->next=NULL;              /*將原鏈表置為空表H*/
     while ( p )
         { q=p;  p=p->next;
          q ->next=H->next;       /*將當前結點插到頭結點的后面*/
          H ->next=q;
        }
}

該算法只是對鏈表順序掃描一遍即完成了倒置，所以時間復雜度為O(n)。

【例2.5】 已知單鏈表H，寫一算法，刪除鏈表中重復元素結點，即實現如圖2.23所示的操作。圖2.23（a）為刪除前的單鏈表，圖2.23（b）為刪除后的單鏈表。

算法思路：用指針p指向鏈表的第一個數據結點，用另一個指針q從p的后繼結點開始搜索到表尾，依次找出與p所指結點的值相同的結點并將其刪除；然后p指向下一個結點，繼續用q指針尋找與p所指結點值相同的結點并將其刪除；依此類推，直到p指向最后結點時算法結束。

算法2.17 剔除單鏈表中的重復元素算法。

void pur_LinkList (LinkList H)
    { LNode *p, *q, *r；
      p=H->next;                            /*p指向第一個結點*/
      if (p== NULL) return；
      while (p->next)
          { q=p;
      while (q ->next)                      /*從*p的后繼開始找重復結點*/
          { if (q ->next->data== p->data)
               { r=q ->next;                /*找到重復結點，用r指向，刪除*r */
                 q ->next=r ->next;
                 free( r );
               }
            else q=q ->next;
           }                                /*while(q->next)*/
          p=p->next;                        /*p指向下一個，繼續*/
           }                                /*while(p->next)*/
}

該算法的時間復雜度為O(n2)。

【例2.6】 設有兩個單鏈表A、B，其中元素遞增有序，編寫算法將A、B歸并成一個按元素值遞減（允許有相同值）有序的鏈表C，要求用A、B中的原結點形成，不能重新申請結點。

算法思路：利用A、B兩表有序的特點，依次進行比較，將當前值較小者摘下，插入到C表的頭部，得到的C表則為遞減有序的。

算法2.18 有序單鏈表的合并算法。

LinkList merge(LinkList A, LinkList B)      /*設A、B均為帶頭結點的單鏈表*/
        {  LinkList C;
        LNode *p，*q，*s；
        p=A->next； q=B->next；
        C=A;  C->next=NULL;                 /*C表的頭結點*/
        free ( B ) ;
        while (p&&q)
           { if (p->data<q->data)
              { s=p；p=p->next； }
           else
              { s=q；q=q->next； }          /*從原A、B表上摘下較小者*/
             s->next=C->next;               /*插入到C表的頭部*/
             C->next=s;
           }                                /*while */
         if ( p== NULL)  p=q；
         while (p)                          /* 將剩余的結點一個個摘下，插入到C表的頭部*/
           { s=p； p=p ->next；
             s->next=C->next;
             C->next=s;
           }
}

該算法的時間復雜度為O(m+n)。