2.3 線性表的鏈式存儲結構

線性表的另一種存儲形式是鏈式存儲結構，鏈式存儲結構中又有單（向）鏈表與雙（向）鏈表。

2.3.1 單鏈表及其基本運算

1.單鏈表

線性表的鏈式存儲結構簡稱鏈表，是用一組任意的存儲單元（這組存儲單元可以是連續的，也可以是不連續的）存儲線性表中的數據元素。因此，為了表示每個數據元素ai與其直接后繼數據元素ai+1之間的邏輯關系，對數據元素ai來說，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息（直接后繼的存儲位置）。由這兩部分信息組成一個“結點”，如圖2-4所示，表示線性表中一個數據元素ai。其中存儲數據元素信息的域稱為數據域，存儲直接后繼存儲位置的域稱為指針域。指針域中存儲的信息又稱為指針或鏈。

由分別表示a1,a2,…,an的n個結點依次相連構成的鏈表，稱為線性表的鏈式存儲表示，由于此類鏈表的每個結點中只包含一個指針域，故稱為單鏈表或線性鏈表，如圖2-5所示。

與順序表類似，在鏈式存儲結構中仍以第一個數據元素的存儲地址作為線性表的基地址，并用一個指針指向它，該指針通常稱為頭指針，線性表中所有數據元素都可以從頭指針出發找到。因為線性表的最后一個數據元素沒有后繼，因此最后一個結點中的“指針”為空指針（圖中用Λ表示）。

出于對操作上方便性的考慮，在第一個結點之前附加一個“頭結點”，令該結點中指針域的指針指向第一個表元素結點，并令頭指針指向頭結點，如圖2-6（a）所示。

值得注意的是，若線性表為空，在不帶頭結點的情況下，頭指針為空，但在帶頭結點的情況下，鏈表的頭指針不為空，而是其頭結點中指針域的指針為空，如圖2-6（b）所示。

由上可見，單鏈表可以由頭指針唯一確定，其存儲結構描述如下。

typedef struct Lnode    / * 結點類型定義 * /
{ ElementType data;
  struct Lnode *next;
}ListNode;
typedef ListNode *LinkList;/ * LinkList為指向ListNode的指針類型* /

若head是指向某一單鏈表的頭指針，則可用下列語句聲明：

LinkList head;

它指向表中第一個結點（對于帶頭結點的單鏈表，則指向單鏈表的頭結點），若head=NULL（對于帶頭結點的單鏈表為head->next=NULL），則表示單鏈表為一個空表，其長度為0。若不是空表，則可以通過頭指針訪問表中的任意結點，獲得相應結點數據域的值。對于帶頭結點的單鏈表head，p=head->next指向表中的第一個結點a1，即p->data表示a1，而p->next指向a2，p->next->data表示a2，依次類推。

2.單鏈表上基本運算的實現

（1）查找運算。在帶頭結點的單鏈表中查找（數據域的）值為x的結點，若找到，則返回指向該結點的指針，否則返回NULL。查找過程從單鏈表的頭指針指向的頭結點出發，順著鏈逐個將結點的值與給定值x作比較。

具體算法描述如下。

LinkList Locate( LinkList head,ElemType x)
/ * 在帶頭結點的單鏈表head中查找值為x的結點* /
{  p=head->next; / * 從表中第一個結點查找起 * /
   while (p!=NULL && p->data!=x)
      p=p->next;  / * 指針后移* /
   return p;
}/ * Locate * /

算法的平均時間復雜度為O(n)，n為單鏈表的結點數。

（2）單鏈表插入操作。在帶頭結點的單鏈表head中第i個數據元素之前插入一個數據元素x，需要首先在單鏈表中找到第i-1個結點（由pre指向該結點），然后申請一個新的結點（由p指向該結點），其數據域的值為x，并修改第i-1個結點的指針使其指向p，然后使p結點的指針域指向第i個結點。插入過程如圖2-7所示。具體算法描述如下。

void InsList(LinkList head,int i,ElemType x)
/*在帶頭結點的單鏈表head中第i個位置（前）插入值為x的新結點*/
{
    pre=head;k=0;
    while (pre!=NULL && k<i-1)
   /*查找第i-1個結點，并由pre指向該結點*/
   {  pre=pre->next;
      k=k+1;
   }
   if (k!=i-1 || pre==NULL)  /*沒有第i-1個結點*/
         printf("Error")；
      else
      {  p=(LinkList)malloc(sizeof(ListNode));
         p->data=x;
         p->next=pre->next;
         pre->next=p
    }
}/* InsList */

單鏈表中有n個結點時，則（前）插入操作的插入位置有n+1個，即1≤i≤n+1。當i=n+1時，則認為是在表尾插入一個結點。該算法的平均時間復雜度為O(n)。

（3）刪除。在帶頭結點的單鏈表head中刪除第i個結點，則首先要找到第i-1個結點并使pre指向第i-1個結點，而后刪除第i個結點并釋放結點空間。刪除過程如圖2-8所示。具體算法描述如下。

void DelList(LinkList head,int i)
/*在帶頭結點的單鏈表head中刪除第i個結點*/
{
    pre=head;k=0;
    while(pre->next!=NULL && k<i-1)
    {  pre=pre->next;
       k=k+1;
    }
    if(!(pre->next) && k<=i-1)    /* 沒有第i個結點*/
          printf("Error");
    else
    {  p=pre->next;
       pre->next=pre->next->next;  /*刪除結點p*/
       free(p); /*釋放結點所占空間*/
    }
} /* DelList */

單鏈表中有n個結點，則刪除操作的刪除位置有n個，即1≤i≤n。該算法的平均時間復雜度為O(n)。

以上3個基本運算均是在帶頭結點的單鏈表上實現的。下面僅以刪除操作為例，給出其在不帶頭結點的單鏈表上的實現。希望讀者能夠比較出單鏈表帶頭結點后算法的簡潔之處。

LinkList DelList(LinkList head,int i)
/*在不帶頭結點的單鏈表head中刪除第i個結點*/
{  if (head==NULL)
   {  printf(“Empty link”);
      return(NULL);
   }
   if (i==1)
   {  p=head;
      head=head->next;
      free(p);
      return(head);
   }
   pre=head;k=0;
   while(pre->next!=NULL && k<i-1)
   {  pre=pre->next;
      k=k+1;
   }
   if(!(p->next) && k<=i-1)   /* 沒有第i個結點*/
         printf(“Inexistent node”);
   else
   {  p=pre->next;
      pre->next=pre->next->next; /*刪除結點p*/
      free(p); /*釋放結點所占空間*/
   }
   return(head);
} /* DeleList */

【例2-2】輸入一批值作為單鏈表中結點數據域的值，寫一算法，建立相應的帶頭結點的單鏈表。

要建立一帶頭結點的單鏈表，可考慮使用如下兩種方法。一是首先建一帶頭結點的空單鏈表，然后逐一將元素插入到第一個結點之前；二是先建一不帶頭結點的單鏈表（每次將元素作為第一個結點插入），然后建立頭結點，并鏈接前面所建的單鏈表。實際上前一種方法在建立了頭結點之后，就是反復地調用插入算法。下面所用的是后一種方法。

LinkList Create()
/*建一帶頭結點的單鏈表*/
{  p=q=NULL;
   /*p指向新結點，用于存放輸入的數據；q指向構造過程中的單鏈表的鏈首*/
   scanf(&x);
   while (x!=FLAG)
   /* FLAG為一與x類型相同的特殊值（作為輸入數據的結束標志用）*/
   {
      p=(LinkList)malloc(sizeof(ListNode));
      p->data=x;
      p->next=q
      q=p;
      scanf(&x);
   }
   head=(LinkList)malloc(sizeof(ListNode))
   head->next=p;
   return (head);
}/* Create */

2.3.2 循環鏈表

循環單鏈表是單鏈表的另一種形式，其特點是表中最后一個結點的指針不再是空，而是指向頭結點（帶頭結點的單鏈表）或第一個結點（不帶頭結點的單鏈表），整個鏈表形成一個環，這樣從表中任意結點出發都可找到其他的結點。考慮到各種操作實現的方便性，循環單鏈表一般均指帶頭結點的循環單鏈表。如圖2-9（a）所示為帶頭結點的循環單鏈表的空表表示，如圖2.9（b）所示為帶頭結點的循環單鏈表的非空表表示。循環單鏈表的存儲結構描述（類型定義）與單鏈表的完全相同。

循環鏈表的基本操作的實現和單鏈表的基本一致，差別僅在于判別鏈表中最后一個結點的條件不再是“后繼是否為空”（p!=NULL或p->next!=NULL），而是“后繼是否為頭結點”（p!=head或p->next!=head）。

【例2-3】對如圖2-10（a）所示的兩個循環鏈表，寫一算法實現兩個鏈表的合并。合并后ra鏈表在前，rb鏈表在后，如圖2-10（b）所示。

要合并ra鏈表與rb鏈表，并使得rb鏈接在ra的尾部，也就是ra鏈表的尾結點的指針指向rb鏈表的第一個結點，rb鏈表的尾結點的指針指向ra鏈表的頭結點，需引入兩個指針pra與prb分別指向ra與rb的尾結點。合并算法描述如下。

void Merge(LinkList ra,LinkList rb)
/*將循環單鏈表ra、rb合并，合并后ra在前rb在后*/
{
    pra=ra->next;
    while (pra->next!=ra) /*移動pra使其指向ra表的尾結點*/
         pra=pra->next;
    prb=rb->next;
    while (prb->next!=rb) /*移動prb使其指向rb表的尾結點*/
         prb=prb-->next;
    prb->next=ra;
    pra->next=rb—>next;
    free(rb);
}/* Merge */

合并后的循環鏈表如圖2-10（b）所示。如果ra鏈表與rb鏈表中元素的個數分別是m與n，則算法的時間復雜度是O(m+n)。

2.3.3 雙向鏈表

在以上討論的單鏈表中，每個結點只有一個指向其后繼的指針域，因此，在這樣的結構上查找某一結點的后繼所需的時間復雜度是O(1)，而查找某一結點的前驅所需的時間復雜度是O(n)。為了克服單鏈表這種單向性的缺點，可利用雙向鏈表。

雙向鏈表中的每個結點都有兩個指針域，一個指向其后繼，另一個指向其前驅，雙向鏈表的結點結構如圖2-11所示，其相應的類型描述如下。

typedef struct DNode
{   ElemType data；
   struct DNode *prior，*next；
}DoubleNode,* DoubleList；

雙向鏈表與單鏈表類似，也有循環表，考慮到算法的方便性，一般使用帶頭結點的雙向循環鏈表。如圖2-12（a）所示是帶頭結點的空雙向循環鏈表，圖2.12（b）所示是帶頭結點非空雙向循環鏈表。

在雙向鏈表中，那些只涉及后繼指針的算法，如求表長度，獲取表中的第i個元素，元素定位（獲取某一元素的位置）等，與單鏈表中相應的算法相同。但對于插入和刪除操作，則涉及前驅和后繼兩個方向的指針變化，因此與單鏈表中的算法有所不同。

插入操作時（在第i個結點之前插入值為x的結點），首先定位第i個結點并由p指向它，如圖2-13（a）所示，然后修改指針，如圖2-13（b）所示。下面是插入算法。

void DlinkIns(DoubleList head,int i,ElemType x)
/*帶頭結點的雙向循環鏈表由head指向，在head中的第i個結點前插入值為x的新結點*/
{
    p=head->next;k=1;
    while (p!=head && k<i)
    /*查找第i個結點，并由p指向該結點*/
    {  p=p->next;
       k=k+1;
    }
    if(k!=i)  /*沒有第i個結點*/
         printf("Error")；
    else
    {
         s=(DoubleList)malloc(sizeof(DoubleNode));
         s->data=x;
         s->prior=p->prior;
         p->prior->next=s;
         s->next=p;
         p->prior=s;
    }
}/* DlinkIns */

雙向循環鏈表的刪除操作與插入操作類似，首先也是定位第i個結點并由p指向它，然后修改指針。定位第i個結點的過程與插入完全相同，如圖2-14（a）所示。指針的修改與插入時不同，只需修改兩個指針，如圖2-14（b）所示，最后釋放第i個結點的空間，相應的操作語句如下。

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