3.3 線性表的存儲結構及實現

3.3.1 順序表

1.順序表的存儲結構定義

線性表的順序存儲結構稱為順序表（sequentiallist），其基本思想是用一段地址連續的存儲單元依次存儲線性表的數據元素，如圖3-5所示。由于線性表中每個數據元素的類型相同，設順序表的每個元素占用c個存儲單元，則第i個元素的存儲地址為：

圖3-5 順序表中元素ai的存儲地址

LOC（ai）=LOC（a1）+（i-1）c

容易看出，順序表中數據元素的存儲地址是其序號的線性函數，只要確定了存儲順序表的起始地址（即基地址），計算任意一個元素的存儲地址的時間就是相等的，具有這一特點的存儲結構稱為隨機存取（randomaccess）結構。

通常用一維數組來實現順序表，也就是把線性表中相鄰的元素存儲在數組中相鄰的位置，從而導致了數據元素的序號和存放它的數組下標之間的一一對應關系，如圖3-6所示。需要強調的是，C語言中數組的下標是從0開始的，而線性表中元素的序號是從1開始的，也就是說，線性表中第i個元素存儲在數組中下標為i-1的位置①。

圖3-6 數組的長度和線性表的長度具有不同含義

數組需要分配固定長度的數組空間，因此，必須確定存放線性表的數組空間的長度。因為在線性表中可以進行插入操作，所以，數組的長度應大于當前線性表的長度。用MaxSize表示數組的長度，用length表示線性表的長度，如圖3-6所示。

下面給出順序表的存儲結構定義：

        constintMaxSize=10；              //假設順序表最多存放10個元素
        typedefintDataType；               //DataType為線性表的數據類型
        typedefstruct
        {
            DataTypedata[MaxSize]；        //存放數據元素的數組
            intlength；                   //線性表的長度
        }SeqList；

2.順序表的實現

在順序表中，由于元素的序號與數組中存儲該元素的下標之間具有一一對應關系，所以，容易實現順序表的基本操作。下面討論基本操作的算法。

（1）初始化順序表

初始化順序表只需簡單地將順序表的長度length初始化為0，算法如下：

            voidInitList（SeqList&L）
            {
            L.length=0；
            }

（2）建立順序表

建立一個長度為n的順序表需要將給定的數據元素傳入順序表中，并將傳入的元素個數作為順序表的長度。設給定的數據元素存放在數組 a[n]中，建立順序表的操作示意圖如圖3-7所示。算法如下：

圖3-7 建立順序表的操作示意圖

            voidCreat（SeqList&L，DataTypea[]，intn）
            {
              if（n＞MaxSize）{printf（＂參數非法＂）；exit（-1）；}
              for（i=0；i＜n；i++）
                L.data[i]=a[i]；
              L.length=n；
            }

（3）求順序表的長度

在順序表的存儲結構定義中用結構體成員length保存了線性表的長度，因此，求線性表的長度只需返回length的值，算法如下：

            intLength（SeqList&L）
            {
              returnL.length；
            }

（4）按位查找

順序表中第i個元素存儲在數組中下標為i-1的位置，所以，容易實現按位查找。顯然，按位查找算法的時間復雜度為O（1）。

            DataTypeGet（SeqList&L，inti）
            {
              if（i＜1&&i＞L.length）{printf（＂查找位置非法＂）；exit（-1）；}
              elsereturnL.data[i-1]；
            }

（5）按值查找

在順序表中實現按值查找操作，需要對順序表中的元素依次進行比較，如果查找成功，返回元素的序號（注意不是下標）；如果查找不成功，返回查找失敗的標志“0”。

            intLocate（SeqList&L，DataTypex）
            {
              for（i=0；i＜L.length；i++）
                if（L.data[i]==x）returni+1；     //下標為i的元素等于x，返回序號i+1
              return0；                           //退出循環，說明查找失敗
            }

按值查找算法的問題規模是表長n，基本語句是for循環中元素比較的語句。順序查找從第一個元素開始，依次比較每一個元素，直到找到x為止。如果順序表的第一個元素恰好就是x，算法只要比較一次就行了，這是最好情況；如果順序表的最后一個元素是x，算法就要比較n個元素，這是最壞情況；平均情況下，假設數據等概率分布，則平均比較表長的一半。所以，按值查找算法的平均時間性能是O（n）。

（6）插入操作

插入操作是在表的第i（1≤i≤n+1）個位置插入一個新元素 x，使長度為 n的線性表（a1，…，ai-1，ai，…，an）變成長度為n+1的線性表（a1，…，ai-1，x，ai，…，an），插入后，元素ai-1和ai之間的邏輯關系發生了變化并且存儲位置要反映這個變化。圖3-8給出了順序表在進行插入操作的前后，數據元素在存儲空間中位置的變化。

圖3-8 將元素15插入位置3，順序表前后狀態的對比

注意元素移動的方向，必須從最后一個元素開始移動，直至將第i個元素后移為止，然后將新元素插入位置i處。如果表滿了，則引發上溢錯誤；如果元素的插入位置不合理，則引發位置錯誤。算法如下：

            voidInsert（SeqList&L，inti，DataTypex）
            {
              if（L.length＞=MaxSize）{printf（＂上溢＂）；exit（-1）；}
              if（i＜1‖i＞length+1）{printf（＂位置＂）；exit（-1）；}
              for（j=L.length；j＞=i；j--）            //j表示元素序號
                L.data[j]=L.data[j-1]；
              L.data[i-1]=x；
              L.length++；
            }

該算法的問題規模是表的長度n，基本語句是for循環中元素后移的語句。當i=n+1時（即在表尾插入），元素后移語句將不執行，這是最好情況，時間復雜度為O（1）；當i=1時（即在表頭插入），元素后移語句將執行n次，需移動表中所有元素，這是最壞情況，時間復雜度為O（n）；由于插入可能在表中任意位置上進行，因此需分析算法的平均時間復雜度。令Ein（n）表示元素移動次數的平均值，pi表示在表中第i個位置上插入元素的概率，不失一般性，假設p1=p2=…=pn+1=1/（n+1），由于在第i個（1≤i≤n+1）位置上插入一個元素后移語句的執行次數為n-i+1，故

也就是說，在順序表上實現插入操作，等概率情況下，平均要移動表中一半的元素，算法的平均時間復雜度為O（n）。

（7）刪除操作

刪除操作是將表的第i（1≤i≤n）個元素刪除，使長度為n的線性表（a1，…，ai-1，ai，ai+1，…，an）變成長度為n-1的線性表（a1，…，ai-1，ai+1，…，an），刪除后元素ai-1和ai+1之間的邏輯關系發生了變化并且存儲位置也要反映這個變化。圖3-9給出了順序表在刪除操作的前后，數據元素在存儲空間中位置的變化。

圖3-9 將位置3處的元素刪除，順序表前后狀態的對比

注意元素移動的方向，必須從第i+1個元素（下標為i）開始移動，直至將最后一個元素前移為止，并且在移動元素之前要取出被刪元素。如果表為空，則引發下溢錯誤；如果元素的刪除位置不合理，則引發位置錯誤。算法如下：

            DataTypeDelete（SeqList&L，inti）
            {
              if（L.length==0）{printf（＂下溢＂）；exit（-1）；}
              if（i＜1‖i＞L.length）{printf（＂位置＂）；exit（-1）；}
              x=L.data[i-1]；                    //取出位置i的元素
              for（j=i；j＜L.length；j++）       //j表示元素所在數組下標
                L.data[j-1]=L.data[j]；
              L.length--；
              returnx；
            }

設順序表的表長是n，顯然，刪除第i個（1≤i≤n）元素需要移動n-i個元素，令Ede（n）表示元素移動次數的平均值，pi表示刪除第i個元素的概率，等概率情況下，pi=1/n，則

也就是說，在順序表上實現刪除操作，等概率情況下，平均要移動表中一半的元素，算法的平均時間復雜度為O（n）。

（8）判空操作

順序表的判空操作只需判斷長度length是否為0，算法如下：

            intEmpty（SeqList&L）
            {
              if（L.length==0）return1；          //順序表為空返回1
              elsereturn0；
            }

（9）遍歷操作

在順序表中，遍歷操作即是按下標依次輸出各元素，算法如下：

            voidPrintList（SeqList&L）
            {
                for（i=0；i＜L.length；i++）
                  printf（L.data[i]）；            //依次輸出線性表的元素值
            }

3.3.2 單鏈表

1.單鏈表的存儲結構定義

單鏈表①（singlylinkedlist）是用一組任意的存儲單元存放線性表的元素，這組存儲單元可以連續也可以不連續，甚至可以零散分布在內存中的任意位置。為了能正確表示元素之間的邏輯關系，每個存儲單元在存儲數據元素的同時，還必須存儲其后繼元素所在的地址信息，如圖3-10所示，這個地址信息稱為指針（pointer），這兩部分組成了數據元素的存儲映像，稱為結點（node），結點結構如圖3-11所示。單鏈表正是通過每個結點的指針域將線性表的數據元素按其邏輯次序鏈接在一起的，由于每個結點只有一個指針域，故稱為單鏈表。

圖3-10 線性表（a1，a2，a3）的單鏈表存儲

圖3-11 單鏈表的結點結構

用圖3-10的方法表示一個單鏈表非常不方便，而且在使用單鏈表時，關心的只是數據元素以及數據元素之間的邏輯關系，而不是每個數據元素在存儲器中的實際位置。通常將圖3-10所示的單鏈表畫成圖3-12的形式。

圖3-12 線性表（a1，a2，a3）的單鏈表存儲

如圖3-12所示，單鏈表中每個結點的存儲地址存放在其前驅結點的next域中，而第一個元素無前驅，所以設頭指針（headpointer）指向第一個元素所在結點（稱為開始結點），整個單鏈表的存取必須從頭指針開始進行，因而頭指針具有標識一個單鏈表的作用；由于最后一個元素無后繼，故最后一個元素所在結點（稱為終端結點）的指針域為空，即NULL（圖中用“∧”表示），也稱尾標志（tailmark）。

從單鏈表的存儲示意圖可以看到，除了開始結點外，其余每個結點的存儲地址都存放在其前驅結點的next域中，而開始結點是由頭指針指示的。這個特例需要在單鏈表實現時特殊處理，增加了程序的復雜性和出現bug①的機會。因此，通常在單鏈表的開始結點之前附設一個類型相同的結點，稱為頭結點②（headnode），如圖3-13所示。加上頭結點之后，無論單鏈表是否為空，頭指針始終指向頭結點，因此空表和非空表的處理也統一了。

圖3-13 帶頭結點的單鏈表

下面給出單鏈表的存儲結構定義：

            typedefintDataType；                 //DataType為線性表的數據類型
            typedefstructNode
            {
              DataTypedata；
              Node*next；
            }Node，*first；                     //first為指向單鏈表的頭指針

2.單鏈表的實現

單鏈表的基本思想就是用指針表示結點之間的邏輯關系，首先要正確區分指針變量、指針、指針所指結點和結點的值這四個密切相關的不同概念。

設p是一個指針變量，則p的值是一個指針。有時為了敘述方便，將“指針變量”簡稱為“指針”。例如，將“頭指針變量”簡稱為“頭指針”。

設指針p指向某個Node類型的結點，則該結點用*p來表示，*p為結點變量。有時為了敘述方便，將“指針p所指結點”簡稱為“結點p”。

在單鏈表中，結點p由兩個域組成：存放數據元素的部分和存放后繼結點地址的指針部分，分別用（*p）.data和（*p）.next來標識，為了使用方便，C語言為指向結構體的指針提供了運算符“-＞”，即用p-＞data和p-＞next分別表示結點p的數據域和指針域，如圖3-14所示，設指針p指向結點ai，則p-＞next指向結點ai+1。

圖3-14 指針和結點之間的關系

單鏈表由頭指針唯一指定，整個單鏈表的操作必須從頭指針開始。通常設置一個工作指針p，當指針p指向某結點時執行相應的處理，然后將指針p修改為指向其后繼結點，直到p為NULL為止。下面討論單鏈表基本操作的算法。

（1）初始化單鏈表

初始化單鏈表也就是生成只有頭結點的空鏈表，算法如下：

            Node*InitList（Node*first）
            {
              first=（Node*）malloc（sizeof（Node））；          //生成頭結點
              first-＞next=NULL；                                //頭結點的指針域置空
              returnfirst；
            }

（2）遍歷操作

所謂遍歷單鏈表是指按序號依次訪問單鏈表中的所有結點且僅訪問一次。可以設置一個工作指針p依次指向各結點，當指針p指向某結點時輸出該結點的數據域。遍歷單鏈表的操作示意圖如圖3-15所示，算法用偽代碼描述如下 ：

圖3-15 遍歷單鏈表的操作示意圖

遍歷單鏈表需要將單鏈表掃描一遍，因此時間復雜度為O（n）。遍歷單鏈表的算法用C語言描述如下：

            voidPrintList（Node*first）
            {
              p=first-＞next；                 //工作指針p初始化
              while（p！=NULL）
              {
                printf（p-＞data）；
                p=p-＞next；                  //工作指針p后移，注意不能寫作p++
              }
            }

需要強調的是，工作指針p后移不能寫作p++，因為單鏈表的存儲單元可能不連續，因此p++不能保證工作指針p指向下一個結點，如圖3-16所示。

圖3-16 p++與p-＞next的執行結果

（3）求線性表的長度

由于單鏈表的存儲結構定義中沒有存儲線性表的長度，因此，不能直接獲得線性表的長度。考慮采用“數數”的方法來求其長度，即從第一個結點開始數，一直數到表尾。可以設置一個工作指針p依次指向各結點，當指針p指向某結點時求出其序號，然后將p修改為指向其后繼結點并且將序號加1，則最后一個結點的序號即為表中結點個數（即線性表的長度）。求單鏈表長度的操作示意圖如圖3-17所示。

圖3-17 求線性表長度的操作示意圖

求線性表長度的算法用C語言描述如下：

            intLength（Node*first）
            {
              p=first-＞next；count=0；              //工作指針p和累加器count初始化
              while（p！=NULL）
              {
                p=p-＞next；
                count++；
              }
              returncount；                         //注意count的初始化和返回值之間的關系
            }

（4）按位查找

在單鏈表中，即使知道被訪問結點的序號i，也不能像順序表那樣直接按序號訪問，只能從頭指針出發順next域逐個結點往下搜索。當工作指針p指向某結點時判斷是否為第i個結點，若是，則查找成功；否則，將工作指針p后移。對每個結點依次執行上述操作，直到p為NULL時查找失敗。算法如下：

            DataTypeGet（Node*first，inti）
            {
              p=first-＞next；count=1；                         //工作指針p和累加器count初始化
              while（p！=NULL&&count＜i）
              {
                p=p-＞next；                                    //工作指針p后移
                count++；
              }
              if（p==NULL）{printf（＂位置＂）；exit（-1）；}   //查找失敗
              elsereturnp-＞data；
            }

查找算法的基本語句是工作指針p后移，該語句執行的次數與被查結點在表中的位置有關。在查找成功的情況下，若查找位置為i（1≤i≤n），則需要執行 i-1次，等概率情況下，平均時間性能為O（n）。因此，單鏈表是順序存取（SequentialAccess）結構。

（5）按值查找

在單鏈表中實現按值查找操作，需要對單鏈表中的元素依次進行比較，如果查找成功，則返回元素的序號；如果查找不成功，返回0表示查找失敗。算法如下：

            intLocate（Node*first，DataTypex）
            {
              p=first-＞next；count=1；                //工作指針p和累加器count初始化
              while（p！=NULL）
              {
                if（p-＞data==x）returncount；         //查找成功，結束函數并返回序號
                p=p-＞next；
                count++；
              }
              return0；                               //退出循環表明查找失敗
            }

按值查找的基本語句是將結點p的數據域與待查值進行比較，具體的比較次數與待查值結點在單鏈表中的位置有關。在等概率情況下，平均時間性能為O（n）。

（6）插入操作

單鏈表的插入操作是將值為x的新結點插入到單鏈表的第i個位置，即插入到ai-1與ai之間。因此，必須先掃描單鏈表，找到ai-1的存儲地址p，然后生成一個數據域為x的新結點s，將結點s的next域指向結點ai，將結點p的next域指向新結點s（注意指針的鏈接順序），從而實現三個結點ai-1、x和ai之間邏輯關系的變化，插入過程如圖3-18所示。注意分析在表頭、表中間、表尾插入這三種情況，由于單鏈表帶頭結點，這三種情況的操作語句一致，不用特殊處理。算法用偽代碼描述如下 ：

圖3-18 在單鏈表中插入結點時指針的變化情況（① s-＞next=p-＞next；② p-＞next=s；）

插入算法的時間主要耗費在查找正確的插入位置上，故時間復雜度為O（n）。單鏈表插入算法用C語言描述如下：

            voidInsert（Node*first，inti，DataTypex）
            {
              p=first；count=0；                              //工作指針p應指向頭結點
              while（p！=NULL&&count＜i-1）                   //查找第i-1個結點
              {
                p=p-＞next；                                  //工作指針p后移
                count++；
              }
              if（p==NULL）{printf（＂位置＂）；exit（-1）；} //沒有找到第i-1個結點
              else{
                s=（Node*）malloc（sizeof（Node））；
                s-＞data=x；                                  //申請一個結點s，其數據域為x
                s-＞next=p-＞next；p-＞next=s；               //將結點s插入到結點p之后
              }
            }

在不帶頭結點的單鏈表中插入一個結點，在表頭的操作和在表中間以及表尾的操作語句是不同的，則在表頭的插入情況需要單獨處理，如圖3-19所示，算法如下：

圖3-19 在不帶頭結點的單鏈表中插入結點時指針的變化情況

（? s-＞next=first；? first=s；① s-＞next=p-＞next；② p-＞next=s；）

            voidInsert（Node*first，inti，DataTypex）
            {
                if（i==1）
                {
                    s=（Node*）malloc（sizeof（Node））；s-＞data=x；
                    s-＞next=first；first=s；               //將結點s插入到頭指針之后
                    return；                                //插入操作完畢，結束函數
                }
                p=first；count=0；                          //工作指針p初始化
                while（p！=NULL&&count＜i-1）
                {
                    p=p-＞next；                            //工作指針p后移
                    count++；
                }
                if（p==NULL）{printf（＂位置＂）；exit（-1）；}
                else
                {
                    s=（Node*）malloc（sizeof（Node））；s-＞data=x；
                    s-＞next=p-＞next；                    //將結點s插入到結點p之后
                    p-＞next=s；
                }
            }

可見，在不帶頭結點的單鏈表中實現插入操作，算法不僅冗長，而且需要考慮在表頭操作的特殊情況，容易出現錯誤。所以，在單鏈表中，除非特別說明不能帶頭結點，否則，為了運算方便，都要加上頭結點。

（7）建立單鏈表

設給定的數據元素存放在數組a[n]中，建立單鏈表就是生成存儲這n個數據元素的單鏈表。有兩種建立方法：頭插法和尾插法。

頭插法的基本思想是每次將新申請的結點插在頭結點的后面，執行過程如圖3-20所示，算法如下：

圖3-20 頭插法建立單鏈表的操作示意圖（① s-＞next=first-＞next；② first-＞next=s；）

            Node*Creat（Node*first，DataTypea[]，intn）
            {
                first=（Node*）malloc（sizeof（Node））；
                first-＞next=NULL；                          //初始化頭結點
                for（i=0；i＜n；i++）
                {
                    s=（Node*）malloc（sizeof（Node））；
                    s-＞data=a[i]；                          //為每個數組元素建立一個結點
                    s-＞next=first-＞next；first-＞next=s；  //將結點s插入到頭結點之后
                }
                returnfirst；
            }

尾插法的基本思想是每次將新申請的結點插在終端結點的后面，執行過程如圖3-21所示，算法如下：

            Node*Creat（Node*first，DataTypea[]，intn）
            {
                first=（Node*）malloc（sizeof（Node））；          //生成頭結點
                r=first；                                          //尾指針初始化
                for（i=0；i＜n；i++）
                {
                    s=（Node*）malloc（sizeof（Node））；
                    s-＞data=a[i]；                                //為每個數組元素建立一個結點
                    r-＞next=s；r=s；                              //將結點s插入到終端結點之后
                }
                r-＞next=NULL；                                    //單鏈表建立完畢，將終端結點的指針域置空
                returnfirst；
            }

（8）刪除操作

刪除操作是將單鏈表的第i個結點刪去。因為在單鏈表中結點ai的存儲地址在其前驅結點ai-1的指針域中，所以必須首先找到ai-1的存儲地址p，然后令p的next域指向ai的后繼結點，即把結點ai從鏈上摘下，最后釋放結點ai的存儲空間。需要注意表尾的特殊情況，此時雖然被刪結點不存在，但其前驅結點卻存在。因此僅當被刪結點的前驅結點p存在且p不是終端結點時，才能確定被刪結點存在，如圖3-22所示。算法用偽代碼描述如下 ：

圖3-22 在單鏈表中刪除結點時指針的變化情況

刪除算法的時間主要耗費在查找正確的刪除位置上，故時間復雜度亦為O（n）。單鏈表刪除算法用C語言描述如下：

            DataTypeDelete（Node*first，inti）
            {
                p=first；count=0；                 //注意工作指針p要指向頭結點
                while（p！=NULL&&count＜i-1）      //查找第i-1個結點
                {
                    p=p-＞next；
                    count++；
                }
                if（p==NULL|p-＞next==NULL）       //結點p不存在或p的后繼結點不存在
                {
                    printf（＂位置＂）；exit（-1）；
                }
                else
                {
                    q=p-＞next；x=q-＞data；      //暫存被刪結點
                    p-＞next=q-＞next；           //摘鏈
                    free（q）；
                    returnx；
                }
            }

3.3.3 雙鏈表

1.雙鏈表的存儲結構定義

如果希望快速確定單鏈表中任一結點的前驅結點，可以在單鏈表的每個結點中再設置一個指向其前驅結點的指針域，這樣就形成了雙鏈表（doublylinkedlist）。和單鏈表類似，雙鏈表一般也是由頭指針唯一確定的，增加頭結點也能使雙鏈表的某些操作變得方便。雙鏈表的存儲示意圖如圖3-23所示。

圖3-23 雙鏈表存儲示意圖

在雙鏈表中，每個存儲單元在存儲數據元素的同時，還存儲了其前驅元素和后繼元素所在的地址信息，這三部分組成了數據元素的存儲映像。雙鏈表的結點結構如圖3-24所示，其中，data為數據域，存放數據元素；prior為前驅指針域，存放該結點的前驅結點的地址；next為后繼指針域，存放該結點的后繼結點的地址。下面給出雙鏈表的存儲結構定義：

圖3-24 雙鏈表的結點結構

            typedefintDataType；            //DataType為線性表的數據類型
            typedefstructDulNode

            {
                  DataTypedata；
                  structDulNode*prior，*next；
            }DulNode，*first；             //first為雙鏈表的頭指針

2.雙鏈表的實現

在雙鏈表中求表長、按位查找、按值查找、遍歷等操作的實現與單鏈表基本相同。下面討論插入和刪除操作。

（1）插入操作

在結點p的后面插入一個新結點s，需要修改四個指針：

① s-＞prior=p；

② s-＞next=p-＞next；

③ p-＞next-＞prior=s；

④ p-＞next=s；

注意指針修改的相對順序，如圖3-25所示，在修改第②和③步的指針時，要用到p-＞next以找到結點p的后繼結點，所以第④步指針的修改要在第②和③步的指針修改完成后才能進行。算法如下：

圖3-25 雙鏈表插入操作示意圖

            voidInsert（DulNode*first，inti，DataTypex）
            {
                p=first；count=0；               //工作指針p應指向頭結點
                while（p！=NULL&&count＜i-1）    //查找第i-1個結點
                {
                    p=p-＞next；                 //工作指針p后移
                    count++；
                }
                if（p==NULL）                    //沒有找到第i-1個結點
                {
                    printf（＂位置＂）；exit（-1）；
                }
                else
                {
                    s=（DulNode*）malloc（sizeof（DulNode））；
                    s-＞data=x；                 //申請一個結點s，其數據域為x
                    s-＞prior=p；                //將結點s插入到結點p之后
                    s-＞next=p-＞next；
                    p-＞next-＞prior=s；
                    p-＞next=s；
                }
            }

（2）刪除操作

設指針p指向待刪除結點，如圖3-26所示，刪除操作可通過下述兩條語句完成：

圖3-26 雙鏈表刪除操作示意圖

①（p-＞prior）-＞next=p-＞next；

②（p-＞next）-＞prior=p-＞prior；

這兩個語句的順序可以顛倒。另外，雖然執行上述語句后結點p的兩個指針域仍指向其前驅結點和后繼結點，但在雙鏈表中已經找不到結點p，而且，執行刪除操作后，還要將結點p所占的存儲空間釋放。雙鏈表刪除算法如下：

            DataTypeDelete（Node*first，inti）
            {
                p=first；count=0；               //工作指針初始化
                while（p！=NULL&&count＜i）      //查找第i個結點
                {
                    p=p-＞next；
                    count++；
                }
                if（p==NULL）                    //結點p不存在
                {
                    printf（＂位置＂）；exit（-1）；
                }
                else
                {
                    q=p-＞next；x=q-＞data；     //暫存被刪結點
                    （p-＞prior）-＞next=p-＞next；//摘鏈
                    （p-＞next）-＞prior=p-＞prior；
                    free（q）；
                    returnx；
                }
            }

3.3.4 循環鏈表

在單鏈表中，如果將終端結點的指針域由空指針改為指向頭結點，就使整個單鏈表形成一個環，這種頭尾相接的單鏈表稱為循環單鏈表（circularsinglylinkedlist），如圖3-27所示。

圖3-27 循環單鏈表存儲示意圖

在用頭指針指示的循環單鏈表中，找到開始結點的時間是O（1），然而要找到終端結點，則需從頭指針開始遍歷整個鏈表，其時間是O（n）。在很多實際問題中，操作是在表的首或尾兩端進行的，此時頭指針指示的循環單鏈表就顯得不夠方便。如果改用指向終端結點的尾指針（rearpointer）來指示循環單鏈表，如圖3-28所示，則查找開始結點和終端結點都很方便，它們的存儲地址分別是（rear-＞next）-＞next和rear，顯然，時間都是O（1）。因此，實際應用中多采用尾指針指示的循環單鏈表。

圖3-28 帶尾指針的循環單鏈表

在雙鏈表中，如果將終端結點的后繼指針域由空指針改為指向頭結點，將頭結點的前驅指針域由空指針改為指向終端結點，就使整個雙鏈表形成一個頭尾相接的循環雙鏈表（circulardoublelinkedlist），如圖3-29所示。在由頭指針指示的循環雙鏈表中，查找開始結點和終端結點都很方便，它們的存儲地址分別是first-＞next和first-＞prior，顯然，時間開銷都是O（1）。

圖3-29 循環雙鏈表存儲示意圖

循環鏈表沒有增加任何存儲量，僅對鏈表的鏈接方式稍做改變，因此，基本操作的實現與鏈表類似，不同之處僅在于循環條件不同。從循環鏈表中任一結點出發，可掃描到其他結點，從而增加了鏈表操作的靈活性。但這種方法的危險在于循環鏈表中沒有明顯的尾端，可能會使循環鏈表的處理操作進入死循環，所以，需要格外注意循環條件。通常判斷用作循環變量的工作指針是否等于某一指定指針（如頭指針或尾指針），以判定工作指針是否掃描了整個循環鏈表。例如，在循環單鏈表的遍歷算法中，用循環條件p！=first判斷工作指針p是否掃描了整個鏈表，算法如下：

            voidPrintList（Node*first）
            {
                p=first-＞next；              //工作指針p初始化
                while（p！=first）            //注意循環條件
                {
                    printf（p-＞data）；
                    p=p-＞next；              //工作指針p后移
                }
            }

3.3.5 靜態鏈表

1.靜態鏈表的存儲結構定義

靜態鏈表（staticlinkedlist）用數組來表示單鏈表，用數組元素的下標來模擬單鏈表的指針。靜態鏈表的存儲示意圖如圖3-30所示，其中，avail是空閑鏈表（所有空閑數組單元組成的單鏈表）頭指針，first是靜態鏈表頭指針。為了運算方便，通常靜態鏈表也帶頭結點。

圖3-30 靜態鏈表存儲示意圖

靜態鏈表的每個數組元素由兩個域構成：data域存放數據元素，next域存放該元素的后繼元素所在的數組下標。由于它是利用數組定義的，屬于靜態存儲分配，因此叫做靜態鏈表。靜態鏈表的存儲結構定義如下：

            constintMaxSize=10；                //最多10個數組單元
            typedefintDataType；                //DataType是線性表的數據類型
            typedefstruct
            {
                  DataTypedata；
                  intnext；                     //指針域（也稱游標），注意不是指針
            }SNode，SList[MaxSize]；

2.靜態鏈表的實現

在靜態鏈表中求表長、按位查找、按值查找、遍歷等操作的實現與單鏈表基本相同，下面討論插入和刪除操作。

（1）插入操作

在靜態鏈表中進行插入操作時，首先從空閑鏈的最前端摘下一個結點，將該結點插入靜態鏈表中，如圖3-31所示。假設新結點插在結點p的后面，則修改指針的操作為：

圖3-31 靜態鏈表插入操作示意圖

            s=avail；                      //不用申請新結點，利用空閑鏈的第一個結點
            avail=SList[avail].next；      //空閑鏈的頭指針后移
            SList[s].data=x；              //將x填入下標為s的結點
            SList[s].next=SList[p].next；  //將下標為s的結點插入到下標為p的結點后面
            SList[p].next=s；

（2）刪除操作

進行刪除操作時，將被刪除結點從靜態鏈表中摘下，再插入空閑鏈的最前端，如圖3-31所示。假設要刪除結點p的后繼結點，則修改指針的操作為：

            q=SList[p].next；              //暫存被刪結點的下標
            SList[p].next=SList[q].next；  //摘鏈
            SList[q].next=avail；          //將結點q插在空閑鏈avail的最前端
            avail=q；                      //空閑鏈頭指針avail指向結點q

圖3-32 靜態鏈表刪除操作示意圖

靜態鏈表雖然是用數組來存儲線性表的，但在執行插入和刪除操作時，只需修改游標，無須移動表中的元素，從而改進了在順序表中插入和刪除操作需要移動大量元素的缺點，但它沒有解決連續存儲分配帶來的表長難以確定的問題。

3.3.6 順序表和鏈表的比較

前面給出了線性表的兩種截然不同的存儲結構——順序存儲結構和鏈接存儲結構，哪一種更好呢？如果實際問題需要采用線性表來解決，應該選擇哪一種存儲結構呢？通常情況下，需要比較不同存儲結構的時間性能和空間性能。

1.時間性能比較

所謂時間性能是指基于某種存儲結構的基本操作（即算法）的時間復雜度。

像取出線性表中第i個元素這樣的按位置隨機訪問的操作，使用順序表更快一些，時間性能為O（1）；相比之下，鏈表中按位置訪問只能從表頭開始依次向后掃描，直到找到那個特定的位置，所需要的平均時間為O（n）。

在鏈表中進行插入和刪除操作不需要移動元素，在給出指向鏈表中某個合適位置的指針后，插入和刪除操作所需的時間僅為O（1）；在順序表中進行插入和刪除操作需移動表長一半的元素，平均時間為O（n），當線性表中元素個數較多時，特別是當每個元素占用的存儲空間較多時，移動元素的時間開銷很大。對于許多應用，插入和刪除是最主要的操作，因此它們的時間效率是舉足輕重的，僅就這個原因而言，鏈表比順序表更好。

作為一般規律，若線性表需頻繁查找卻很少進行插入和刪除操作，或其操作和“數據元素在線性表中的位置”密切相關時，宜采用順序表作為存儲結構；若線性表需頻繁進行插入和刪除操作，則宜采用鏈表作為存儲結構。

2.空間性能比較

所謂空間性能是指某種存儲結構所占用的存儲空間的大小。首先定義結點的存儲密度（storagedensity）。

順序表中每個結點（即數組元素）只存放數據元素，其存儲密度為1；而鏈表的每個結點除了存放數據元素，還要存儲指示元素之間邏輯關系的指針。如果數據域占據的空間較小，則指針的結構性開銷將占用整個結點的大部分，因而從結點的存儲密度上講，順序表的存儲空間利用率較高。

由于順序表需要預分配一定長度的存儲空間，如果事先不知道線性表的大致長度，則有可能對存儲空間預分配得過大，致使存儲空間得不到充分利用，造成浪費；若估計得過小，又將發生上溢而造成存儲空間的再分配；單鏈表不需要為其預分配空間，只要有內存空間可以分配，鏈表中的元素個數就沒有限制。

作為一般規律，當線性表中元素個數變化較大或者未知時，最好使用鏈表實現；如果事先知道線性表的大致長度，使用順序表的空間效率會更高。

總之，線性表的順序存儲和鏈接存儲各有其優缺點，應該根據實際問題的需要，并對各方面的優缺點加以綜合平衡，才能最終選定比較適宜的存儲結構。