寫(xiě)在前面：本文僅供個(gè)人學(xué)習(xí)使用。《大話數(shù)據(jù)結(jié)構(gòu)》通俗易懂，適合整體做筆記輸出，構(gòu)建體系。并且文中很多圖片來(lái)源于該書(shū)。

文章目錄

• • 3.2 線性表的定義
  • 3.3 線性表的抽象數(shù)據(jù)類型
  • 3.4 線性表的順序存儲(chǔ)結(jié)構(gòu)
  • • 3.4.1 順序存儲(chǔ)定義
    • 3.4.2 順序存儲(chǔ)方式
    • 3.4.3 數(shù)組長(zhǎng)度與線性表長(zhǎng)度的區(qū)別
    • 3.4.4 地址計(jì)算方法
  • 3.5 順序存儲(chǔ)結(jié)構(gòu)的插入與刪除
  • • 3.5.1 獲得元素操作
    • 3.5.2 插入操作
    • 3.5.3 刪除操作
    • 3.5.4 線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)
  • 3.6 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
  • • 3.6.1 順序存儲(chǔ)結(jié)構(gòu)不足的解決辦法
    • 3.6.2 線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義
    • 3.6.3 頭指針和頭結(jié)點(diǎn)的異同
    • 3.6.4 線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)代碼描述
  • 3.7 單鏈表的讀取
  • 3.8 單鏈表的插入與刪除
  • • 3.8.1 單鏈表的插入
    • 3.8.2 單鏈表的刪除
  • 3.9 單鏈表的整表創(chuàng)建
  • 3.10 單鏈表的整表刪除
  • 3.11 單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)
  • 3.12 靜態(tài)鏈表
  • • 3.12.1 靜態(tài)鏈表的插入操作
    • 3.12.2 靜態(tài)鏈表的刪除操作
    • 3.12.3 靜態(tài)鏈表優(yōu)缺點(diǎn)
  • 3.13 循環(huán)鏈表
  • 3.14 雙向鏈表
  • 3.15 總結(jié)

線性表：零個(gè)或者多個(gè)數(shù)據(jù)元素的有限序列。

3.2 線性表的定義

舉個(gè)例子，一個(gè)班級(jí)的小朋友，一個(gè)跟著一個(gè)排隊(duì)，有一個(gè)打頭，一個(gè)結(jié)尾，當(dāng)中的小朋友都知道他前面一個(gè)是誰(shuí)，他后面一個(gè)是誰(shuí)，這樣如同有一根線把他們串聯(lián)起來(lái)，就可以稱之為線性表。

線性表的定義

線性表(List):零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列。

這里強(qiáng)調(diào)幾個(gè)關(guān)鍵的地方。

首先它是一個(gè)序列。也就是說(shuō)，元素之間是有順序的，若元素存在多個(gè)，則第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼，其他每個(gè)元素都有且只有一個(gè)前驅(qū)和后繼。如果一個(gè)小朋友去拉兩個(gè)小朋友后面的衣服，那就不可以排成一隊(duì)了；同樣，如果一個(gè)小朋友后面的衣服，被兩個(gè)甚至多個(gè)小朋友拉扯，這其實(shí)是在打架，而不是有序隊(duì)列。

然后，線性表強(qiáng)調(diào)是有限的，小朋友班級(jí)人數(shù)是有限的，元素個(gè)數(shù)當(dāng)然是有限的。事實(shí)上，在計(jì)算機(jī)中處理的對(duì)象都是有限的，那種無(wú)限的數(shù)列，只存在于數(shù)學(xué)的概念中。

如果用數(shù)學(xué)的語(yǔ)言來(lái)定義線性表。可如下

若將線性表記為$(a_1,...,a_{i?1},a_i,...,a_n)$,則表中$a_{i?1}$領(lǐng)先于$a_i$，$a_i$領(lǐng)先于$a_{i+1}$，稱$a_{i?1}$是$a_i$的直接前驅(qū)元素，$a_{i+1}$是$a_i$的直接后繼元素。當(dāng)i=1,2,…,n-1時(shí)，$a_i$有且僅有一個(gè)直接后繼，當(dāng)i=2,3,…,n時(shí)，$a_i$有且僅有一個(gè)直接前驅(qū)。

所以線性表元素的個(gè)數(shù)n(n≥0)定義為線性表的長(zhǎng)度，當(dāng)n=0時(shí)，稱為空表。

在非空表中的每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，如$a_1$是第一個(gè)數(shù)據(jù)元素，$a_n$是最后一個(gè)數(shù)據(jù)元素，$a_i$是第i個(gè)數(shù)據(jù)元素，稱i為數(shù)據(jù)元素$a_i$在線性表中的位序。

在較復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。

3.3 線性表的抽象數(shù)據(jù)類型

現(xiàn)在來(lái)看一下，線性表應(yīng)該具有一些什么樣的操作呢？

還是回到剛才幼兒園小朋友的例子，老師為了讓小朋友有秩序地出入，所以就考慮給他們排一個(gè)隊(duì)，并且是長(zhǎng)期使用的順序，這個(gè)考慮和安排的過(guò)程其實(shí)就是一個(gè)線性表的創(chuàng)建和初始化過(guò)程。

一開(kāi)始沒(méi)經(jīng)驗(yàn)，把小朋友排好隊(duì)之后，發(fā)現(xiàn)有的高有的矮，隊(duì)伍很難看，于是讓小朋友解散重排–這是一個(gè)把線性表重置為空表的操作。

排好了隊(duì)，我們隨時(shí)可以叫出隊(duì)伍某一位置的小朋友名字及他的具體情況。這種可以根據(jù)位序得到數(shù)據(jù)元素也是一種很重要的線性表操作。

還有什么呢，有時(shí)我們想知道,某個(gè)小朋友，比如麥兜是否是班里的小朋友，老師會(huì)告訴我說(shuō)，不是，麥兜在春田花花幼兒園里，不在我們幼兒園。這種查找某個(gè)元素是否存在的操作很常用。

而后有家長(zhǎng)問(wèn)老師，班里現(xiàn)在到底有多少個(gè)小朋友呀，這種獲得線性表長(zhǎng)度的問(wèn)題也很普遍。

顯然，對(duì)于一個(gè)幼兒園來(lái)說(shuō)，加入一個(gè)新的小朋友到隊(duì)列中，或因某個(gè)小朋友生病，需要移除某個(gè)位置，都是很正常的情況。對(duì)于一個(gè)線性表來(lái)說(shuō)，插入數(shù)據(jù)和刪除數(shù)據(jù)都是必須的操作。

所以，線性表的抽象數(shù)據(jù)類型如下：

ADT 線性表(List)Data線性表的數(shù)據(jù)對(duì)象集合為{a1,a2,...,an}，每個(gè)元素的數(shù)據(jù)類型均為DataType。其中，除第一個(gè)元素a1之外，每一個(gè)元素有且只有一個(gè)直接前驅(qū)元素，除了最后一個(gè)元素an外，每一個(gè)元素有且只有一個(gè)直接后繼元素。數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系。 OperationInitList(*L) :初始化操作，建立一個(gè)空的線性表LListEmpty(L) :若線性表為空，返回true，否則返回falseClearList(*L) :將線性表清空GetElem(L,i,e) :將線性表L中的第i個(gè)位置元素值返回給eLocateElem(L,e) :在線性表L中查找與給定值e相等的元素，如果查找成功，返回該元素在表中的序號(hào)表示成功；否則返回0表示失敗。ListInsert(*L,i,e):在線性表L中的第i個(gè)位置插入新元素eListDelete(*L,i,*e):刪除線性表L中第i個(gè)位置元素，并用e返回其值。ListLength(L):返回線性表L的元素個(gè)數(shù)。 endADT

對(duì)于不同的應(yīng)用，線性表的基本操作是不同的，上述操作是最基本的，對(duì)于實(shí)際問(wèn)題中涉及的關(guān)于線性表的更復(fù)雜操作，完全可以用這些基本操作的組合來(lái)實(shí)現(xiàn)。

比如，要實(shí)現(xiàn)兩個(gè)線性表集合A和B的并集操作。即要使得集合A=A∪B。說(shuō)白了，就是把存在集合B中但并不存在A中的數(shù)據(jù)元素插入到A中即可。

仔細(xì)分析一下這個(gè)操作，發(fā)現(xiàn)我們只要循環(huán)集合B中的每個(gè)元素，判斷當(dāng)前元素是否在A中，若不存在，則插入到A中即可。思路是比較容易想到的。

我們假設(shè)La表示集合A，Lb表示集合B，則實(shí)現(xiàn)的代碼如下

void union(List *La,list Lb){int La_len,Lb_len,i;ElemType e;La_len=ListLength(La); //線性表的長(zhǎng)度Lb_len=ListLength(Lb);for(int i=1;i<=Lb_len;i++){GetElem(Lb,i,e); //取出Lb中第i個(gè)數(shù)據(jù)放入到eif(!LocateElem(La,e,equal)) //La中不存在和e相同數(shù)據(jù)元素ListInsert(La,++La_len,e); //插入} }

這里，我們對(duì)于union操作，用到了前面線性表基本操作ListLength,GetElem,LocateElem,ListInsert等，可見(jiàn)，對(duì)于復(fù)雜的個(gè)性化的操作，其實(shí)就是基本操作組合起來(lái)實(shí)現(xiàn)的。

3.4 線性表的順序存儲(chǔ)結(jié)構(gòu)

3.4.1 順序存儲(chǔ)定義

線性表的兩種物理結(jié)構(gòu)其中之一—順序存儲(chǔ)結(jié)構(gòu)

線性表的順序存儲(chǔ)結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。

可以看成去圖書(shū)館占位，連續(xù)占幾個(gè)位置。

3.4.2 順序存儲(chǔ)方式

線性表的順序存儲(chǔ)結(jié)構(gòu)，說(shuō)白了，就是在內(nèi)存中找了塊地兒，通過(guò)占位的方式，把一定內(nèi)存空間給占了，然后把相同類型的數(shù)據(jù)元素依次存放在這塊空地中。既然線性表中的每個(gè)數(shù)據(jù)元素的類型都相同，所以可以用C語(yǔ)言的一維數(shù)組來(lái)實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)，即把第一個(gè)數(shù)據(jù)元素存到數(shù)組下標(biāo)為0的位置中，接著把線性表相鄰的元素存儲(chǔ)在數(shù)組中相鄰的位置。

為了建立一個(gè)線性表，要在內(nèi)存中找一塊地，于是這塊地的第一個(gè)位置就非常關(guān)鍵，它是存儲(chǔ)空間的起始位置。

線性表中，我們估算這個(gè)線性表的最大存儲(chǔ)容量，建立一個(gè)數(shù)組，數(shù)組的長(zhǎng)度就是這個(gè)最大存儲(chǔ)容量。 我們有了起始位置，也有了最大容量，于是我們就可以在里面增加數(shù)據(jù)了。隨著數(shù)據(jù)的插入，我們線性表的長(zhǎng)度開(kāi)始變大，不過(guò)線性表的當(dāng)前長(zhǎng)度不能超過(guò)存儲(chǔ)容量，即數(shù)組的長(zhǎng)度。

來(lái)看線性表的順序存儲(chǔ)的結(jié)構(gòu)代碼

#define MAXSIZE 30 // 存儲(chǔ)空間初始分配量 typedef int ElemType;// 數(shù)據(jù)元素類型typedef struct{ElemType data[MAXSIZE]; //數(shù)組存儲(chǔ)數(shù)據(jù)元素，最大值為MAXSIZEint length;//線性表當(dāng)前的長(zhǎng)度 }SqList;

這里，我們發(fā)現(xiàn)描述順序存儲(chǔ)結(jié)構(gòu)需要三個(gè)屬性：

• 存儲(chǔ)空間的起始位置：數(shù)組data，它的存儲(chǔ)位置就是存儲(chǔ)空間的存儲(chǔ)位置
• 線性表的最大存儲(chǔ)容量：數(shù)組長(zhǎng)度MaxSize
• 線性表的當(dāng)前長(zhǎng)度：length

3.4.3 數(shù)組長(zhǎng)度與線性表長(zhǎng)度的區(qū)別

注意哦，這里有兩個(gè)概念“數(shù)組的長(zhǎng)度”和“線性表的長(zhǎng)度”需要區(qū)分一下。

數(shù)組的長(zhǎng)度時(shí)存放線性表的存儲(chǔ)空間的長(zhǎng)度，存儲(chǔ)分配后這個(gè)量一般是不變的。但是可以采用編程手段實(shí)現(xiàn)動(dòng)態(tài)分配數(shù)組，不過(guò)這會(huì)帶來(lái)性能上的損耗。

線性表的長(zhǎng)度是線性表中數(shù)據(jù)元素的個(gè)數(shù)，隨著線性表插入和刪除操作的進(jìn)行，這個(gè)量是變化的。

在任意時(shí)刻，線性表的長(zhǎng)度應(yīng)該小于等于數(shù)組的長(zhǎng)度。

3.4.4 地址計(jì)算方法

c語(yǔ)言中從下標(biāo)0開(kāi)始，線性表的第i個(gè)元素存在數(shù)組下標(biāo)為i-1的位置。

其實(shí)，內(nèi)存中的地址，就和圖書(shū)館或電影院里的座位一樣，都是有編號(hào)的。存儲(chǔ)器中的每個(gè)存儲(chǔ)單元都有自己的編號(hào)，這個(gè)編號(hào)稱為地址。由于每個(gè)數(shù)據(jù)元素，不管它是整型、實(shí)型還是字符型，它都需要占用一定的連續(xù)存儲(chǔ)空間。假設(shè)占用的是c個(gè)連續(xù)單元，那么線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置滿足下列關(guān)系（LOC表示獲得存儲(chǔ)位置的函數(shù)）：

$LOC(a_{i+1})=LOC(a_i)+c$

所以對(duì)于第i個(gè)數(shù)據(jù)元素$a_i$的存儲(chǔ)位置可以由$a_1$推算得出：

$LOC(a_i)=LOC(a_1)+(i?1)\times c$

通過(guò)這個(gè)公式，可以隨時(shí)算出線性表中任意位置的地址，不管它是第一個(gè)還是最后一個(gè)，都是相同的時(shí)間。那么我們對(duì)每個(gè)線性表位置的存入或者取出數(shù)據(jù)，對(duì)于計(jì)算機(jī)而言都是相等的時(shí)間，也就是一個(gè)常數(shù)，所以它的存取時(shí)間性能是O(1)。我們通常把具有這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)稱為隨機(jī)存取結(jié)構(gòu)。

3.5 順序存儲(chǔ)結(jié)構(gòu)的插入與刪除

3.5.1 獲得元素操作

實(shí)現(xiàn)GetElem操作，剛才提到過(guò)，順序存儲(chǔ)結(jié)構(gòu)獲取元素操作時(shí)間復(fù)雜度為：O(1)

#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0typedef int Status; // Status 是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 // 初始條件：順序表L已存在，1≤L≤ListLength(L) //操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值Status GetElem(SqList L,int i, ElemType *e){ //e這里用引用if(L.length==0 || i<1 || i>L.length)return ERROR;*e=L.data[i-1];return OK; }

注意這里返回值類型Status是一個(gè)類型，返回OK代表1，ERROR代表0.

3.5.2 插入操作

我們現(xiàn)在來(lái)考慮，如果我們要實(shí)現(xiàn)ListInsert(*L,i,e)，即在線性表L中的第i個(gè)位置插入新元素e，應(yīng)該如何操作？

舉例：排隊(duì)時(shí)有人插隊(duì)在你前面，你和后面的人只能順序往后退。

插入算法的思路：

• 如果插入位置不合理，拋出異常；
• 如果線性表長(zhǎng)度≥數(shù)組長(zhǎng)度，則拋出異常或動(dòng)態(tài)增加容量；
• 從最后一個(gè)元素開(kāi)始向前遍歷到第i個(gè)位置，分別將它們都向后移動(dòng)一個(gè)位置；
• 將要插入元素填入位置i處；
• 表長(zhǎng)增加1.

實(shí)現(xiàn)的代碼如下:

Status ListInsert(SqList *L,int i,ElemType e){int k;//線性表滿了：if(L->length==MAXSIZE) //線性表已滿return ERROR;//下面都是在線性表沒(méi)滿的情況下：if(i<1 || i> L->length+1) //當(dāng)i不在范圍內(nèi)時(shí)return ERROR;if(i<=L->length){//若插入數(shù)據(jù)位置不在表尾for( k=L->length-1;k>=i-1;k--)L->data[k+1]=L->data[k];//一位位后移}L->data[i-1]=e; //將新元素插入L->length++;return OK; }

3.5.3 刪除操作

線性表的順序存儲(chǔ)結(jié)構(gòu)刪除元素：刪除該位置，該位置后面的元素依次前移。

刪除算法的思路

• 如果刪除位置不合理，拋出異常；
• 取出刪除元素
• 從刪除元素位置開(kāi)始遍歷到最后一個(gè)元素位置，分別將它們都向前移動(dòng)一個(gè)位置；
• 表長(zhǎng)減1 。

實(shí)現(xiàn)代碼如下：

//操作結(jié)果：刪除L的第i個(gè)元素，并用e返回其值，L的長(zhǎng)度減1 Status ListDelete(SqList *L,int i,ElemType *e){int k;if(L->length==0) //如果線性表為空return ERROR;if(i<1 || i>L->length) //刪除位置不正確return ERROR;*e=L->data[i-1];if(i<L->length){ //i表示線性表中第i個(gè)元素，對(duì)應(yīng)到data數(shù)組中下標(biāo)是i-1for(k=i;k<L->length;k++)L->data[k-1]=L->data[k]; //將刪除位置后繼元素前移}L->length--;return OK; }

下面我們來(lái)分析一下，插入和刪除的時(shí)間復(fù)雜度。

先來(lái)看最好的情況，如果元素要插入到最后一個(gè)位置，或者刪除最后一個(gè)元素，此時(shí)時(shí)間復(fù)雜度為O(1),因?yàn)椴恍枰苿?dòng)元素，就如同來(lái)了一個(gè)新人要正常排隊(duì)，當(dāng)然是排在最后，如果此時(shí)他又不想排了，那么他一個(gè)人離開(kāi)就好，不影響任何人。

最壞的情況呢？ 如果元素要插入到第一個(gè)位置或者刪除第一個(gè)元素，此時(shí)時(shí)間復(fù)雜度是多少呢？那就意味著要移動(dòng)所有的元素向后或者向前，所以這個(gè)時(shí)間復(fù)雜度是O(n).

至于平均的情況，由于元素插入到第i個(gè)位置，或刪除第i個(gè)元素，需要移動(dòng)n-i個(gè)元素。根據(jù)概率原理，每個(gè)位置插入或刪除元素的可能性是相同的，也就說(shuō)位置靠前，移動(dòng)元素多，位置靠后，移動(dòng)元素少。最終平均移動(dòng)次數(shù)和最中間的那個(gè)元素的移動(dòng)次數(shù)相等，為$\frac{n?1}{2}$，所以平均時(shí)間復(fù)雜度為O(n)。

這說(shuō)明什么？ 線性表的順序存儲(chǔ)結(jié)構(gòu)，在存、讀數(shù)據(jù)時(shí)，不管是哪個(gè)位置，時(shí)間復(fù)雜度都是O(1);而插入或刪除時(shí)，時(shí)間復(fù)雜度都是O(n)。就說(shuō)明，它比較適合元素個(gè)數(shù)不太變化，而更多是存取數(shù)據(jù)的應(yīng)用。當(dāng)然，它的優(yōu)缺點(diǎn)還不只這些……

3.5.4 線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)缺點(diǎn)

無(wú)須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間	插入和刪除操作需要移動(dòng)大量元素
可以快速地存取表中任意位置的元素	當(dāng)線性表長(zhǎng)度變化較大時(shí)，難以確定存儲(chǔ)空間的容量
	造成存儲(chǔ)空間的“碎片”

3.6 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

3.6.1 順序存儲(chǔ)結(jié)構(gòu)不足的解決辦法

前面我們提到的線性表的順序存儲(chǔ)結(jié)構(gòu)，它是有缺點(diǎn)的，最大的缺點(diǎn)就是插入和刪除時(shí)需要移動(dòng)大量元素，這顯然需要消耗時(shí)間。能不能想解決辦法？

要解決這個(gè)問(wèn)題，我們就得考慮一下導(dǎo)致這個(gè)問(wèn)題的原因。

為什么當(dāng)插入和刪除時(shí)，就要移動(dòng)大量元素，仔細(xì)分析后，發(fā)現(xiàn)原因就在于相鄰兩元素的存儲(chǔ)位置也具有鄰居關(guān)系。它們的編號(hào)是1,2,…,n，它們?cè)趦?nèi)存中的位置也是挨著的，中間沒(méi)有空隙，當(dāng)然就無(wú)法快速介入，而刪除后，當(dāng)中就會(huì)留出空隙，自然需要彌補(bǔ)。問(wèn)題就出在這里。

A同學(xué)思路：讓當(dāng)中每個(gè)元素之間都留有一個(gè)空位置，這樣要插入時(shí)，就不至于移動(dòng)。可一個(gè)空位置如何解決插入多個(gè)數(shù)據(jù)的問(wèn)題呢？所以這個(gè)想法顯然不行。

B同學(xué)思路：那就讓當(dāng)中每個(gè)元素之間都留有足夠多的位置，根據(jù)實(shí)際情況制定空隙大小，比如10個(gè)，這樣插入時(shí)，就不需要移動(dòng)了。萬(wàn)一10個(gè)空位用完了，再考慮移動(dòng)使得每個(gè)位置之間都有10個(gè)空位置。如果刪除，就直接刪除，把位置留空即可。這樣似乎暫時(shí)解決了插入和刪除的移動(dòng)數(shù)據(jù)問(wèn)題。可這對(duì)于超過(guò)10個(gè)同位置數(shù)據(jù)的插入，效率上還是存在問(wèn)題。對(duì)于數(shù)據(jù)的遍歷，也會(huì)因?yàn)榭瘴恢锰喽斐膳袛鄷r(shí)間上的浪費(fèi)。而且顯然這里空間復(fù)雜度還增加了，因?yàn)槊總€(gè)元素之間都有若干個(gè)空位置。

C同學(xué)思路：我們反正也是要讓相鄰元素間留有足夠余地，那干脆所有的元素都不考慮相鄰位置了，哪有空位就到哪里，而只是讓每個(gè)元素知道它下一個(gè)元素位置在哪里，這樣，我們就可以在第一個(gè)元素時(shí)，就知道第二個(gè)元素的位置（內(nèi)存地址），而找到它；在第二個(gè)元素時(shí)，再找到第三個(gè)元素的位置。這樣所有的元素我們就都可以通過(guò)遍歷而找到。

好！太棒了，這個(gè)想法非常好！C同學(xué)，你可惜生晚了幾十年，不然，你的想法對(duì)于數(shù)據(jù)結(jié)構(gòu)來(lái)講就是劃時(shí)代的意義。我們要的就是這個(gè)思路。

注：這里完全照搬《大話數(shù)據(jù)結(jié)構(gòu)》中的措辭。

3.6.2 線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。這就意味著，這些數(shù)據(jù)元素可以存在內(nèi)存未被占用的任意位置。如圖3-6-1所示。

以前在順序結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素只需要存數(shù)據(jù)元素信息就可以了。現(xiàn)在鏈?zhǔn)浇Y(jié)構(gòu)中，除了要存數(shù)據(jù)元素信息外，還要存儲(chǔ)它的后繼元素的存儲(chǔ)地址。

因此，為了表示每個(gè)數(shù)據(jù)元素$a_i$與其直接后繼元素$a_{i+1}$之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素$a_i$來(lái)說(shuō)，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置）。我們把存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，把存儲(chǔ)直接后繼位置的域稱為指針域。指針域中存儲(chǔ)的信息稱為指針或鏈。這兩部分信息組成數(shù)據(jù)元素$a_i$的存儲(chǔ)映像，稱為結(jié)點(diǎn)（Node）。

n個(gè)結(jié)點(diǎn)($a_i$的存儲(chǔ)映像)鏈接成一個(gè)鏈表，即為線性表($a_1,a_2,...,a_n$)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)榇随湵淼拿總€(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，所以叫作單鏈表。

單鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的數(shù)據(jù)元素按其邏輯順序鏈接在一起，如下圖所示。

對(duì)于線性表來(lái)說(shuō)，總得有個(gè)頭有個(gè)尾，鏈表也不例外。我們把鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置叫作頭指針，那么整個(gè)鏈表的存取就必須是從頭指針開(kāi)始進(jìn)行了。之后的每一個(gè)結(jié)點(diǎn)，其實(shí)就是上一個(gè)后繼指針指向的位置。

最后一個(gè)結(jié)點(diǎn)，當(dāng)然就意味著直接后繼不存在了，所以我們規(guī)定，線性鏈表的最后一個(gè)結(jié)點(diǎn)指針為“空”（通常用NULL或“^”符號(hào)表示），如下圖所示。

有時(shí)，我們?yōu)榱烁臃奖銓?duì)鏈表進(jìn)行操作，會(huì)在單鏈表的第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)如線性表的長(zhǎng)度等附加信息，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針。如下圖所示

3.6.3 頭指針和頭結(jié)點(diǎn)的異同

頭指針頭結(jié)點(diǎn)

頭指針是指鏈表指向第一個(gè)結(jié)點(diǎn)的指針，若鏈表有頭結(jié)點(diǎn)，則是指向頭結(jié)點(diǎn)的指針	頭結(jié)點(diǎn)是為了操作的統(tǒng)一和方便而設(shè)立的，放在第一元素的結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無(wú)意義（也可存放鏈表的長(zhǎng)度）
頭指針具有標(biāo)識(shí)作用，所以常用頭指針冠以鏈表的名字	有了頭結(jié)點(diǎn)，對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)，其操作與其他結(jié)點(diǎn)的操作就統(tǒng)一了
無(wú)論鏈表是否為空，頭指針均不為空。頭指針是鏈表的必要元素	頭結(jié)點(diǎn)不一定是鏈表必須元素

3.6.4 線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)代碼描述

若線性表為空表，則頭結(jié)點(diǎn)的指針域?yàn)椤翱铡?#xff0c;如圖所示

這里我們大概用圖示表達(dá)了內(nèi)存中單鏈表的存儲(chǔ)狀態(tài)。我們關(guān)心的是它在內(nèi)存中的實(shí)際位置嗎？不是的，這只是它所表示的線性表中的數(shù)據(jù)元素及數(shù)據(jù)元素之間的邏輯關(guān)系。我們我們改用更方便的存儲(chǔ)示意圖來(lái)表示單鏈表。如下圖所示

若帶頭結(jié)點(diǎn)的單鏈表，如下圖

空鏈表如圖所示

單鏈表中，我們?cè)贑語(yǔ)言中可用結(jié)構(gòu)指針來(lái)描述

//線性表的單鏈表存儲(chǔ)結(jié)構(gòu) typedef struct Node{ElemType data;struct Node *next; }Node;typedef struct Node *LinkList;//定義結(jié)構(gòu)指針Linklist

從這個(gè)結(jié)構(gòu)定義中，我們也就知道，結(jié)點(diǎn)由存放數(shù)據(jù)元素的數(shù)據(jù)域和存放后繼結(jié)點(diǎn)地址的指針域組成。

假設(shè)p是指向線性表第i個(gè)元素的指針，則該結(jié)點(diǎn)ai的數(shù)據(jù)域我們可以用p->data來(lái)表示,p->data的值是一個(gè)數(shù)據(jù)元素，結(jié)點(diǎn)ai的指針域可以用p->next來(lái)表示，p->next的值是一個(gè)指針。p->next指向誰(shuí)呢？當(dāng)然是指向第i+1個(gè)元素，即指向$a_{i+1}$的指針。也就是說(shuō)，如果$p?>data=a_i,那么p?>next?>data=a_{i+1}$.

3.7 單鏈表的讀取

在線性表的順序存儲(chǔ)結(jié)構(gòu)中，我們要計(jì)算任意一個(gè)元素的存儲(chǔ)位置是很容易的。但在單鏈表中，由于第i個(gè)元素到底在哪沒(méi)法一開(kāi)始就知道，必須得從頭開(kāi)始找。因此，對(duì)于單鏈表實(shí)現(xiàn)獲取第i個(gè)元素的數(shù)據(jù)的操作GetElem上，相對(duì)要麻煩一些。

獲取鏈表第i個(gè)數(shù)據(jù)的算法思路：

聲明一個(gè)結(jié)點(diǎn)p指向鏈表第一個(gè)結(jié)點(diǎn)，初始化j從1開(kāi)始；

當(dāng)j<i時(shí)，就遍歷鏈表，讓p的指針往后移動(dòng)，不斷指向下一結(jié)點(diǎn)，j累加1；

若到鏈表末尾p為空，則說(shuō)明第i個(gè)元素不存在；

否則查找成功，返回結(jié)點(diǎn)p的數(shù)據(jù)。

實(shí)現(xiàn)代碼：

Status GetElem(LinkList L,int i,ElemType *e){int j;LinkList p;//聲明一個(gè)結(jié)點(diǎn)pp=L->next; //讓p指向鏈表L的第一個(gè)結(jié)點(diǎn)j=1; //j為計(jì)數(shù)器while(p && j <i){ //p不為空 或者計(jì)數(shù)器j沒(méi)有等于i時(shí)，循環(huán)繼續(xù)p=p->next;++j; }if( !p || j>i){ //p為空或者 j＞i 則沒(méi)有該元素return ERROR; }*e=p->data; //取出第i個(gè)元素的數(shù)據(jù) return OK;}

說(shuō)白了，就是從頭開(kāi)始找，直到第i個(gè)元素為止。由于這個(gè)算法的時(shí)間復(fù)雜度取決于i的位置，當(dāng)i=1時(shí)，不需要遍歷；當(dāng)i=n時(shí)需要遍歷n-1次，因此最壞情況的為O(n).

3.8 單鏈表的插入與刪除

3.8.1 單鏈表的插入

將結(jié)點(diǎn)s(里面的數(shù)據(jù)是e)插入到結(jié)點(diǎn)p和結(jié)點(diǎn)p->next之間

s->next=p->next; p->next=s;

考慮一下，這兩句的順序可不可以交換？

如果先p->next=s;再s->next=p->next;會(huì)怎么樣？

這樣是錯(cuò)誤的。p->next=s;s的地址覆蓋掉p->next，那么s->next=p->next就是 s->next=s，這樣真正擁有$a_{i+1}$數(shù)據(jù)元素的結(jié)點(diǎn)就沒(méi)了上級(jí)。也就是掉了鏈子。

對(duì)于單鏈表的表頭和表尾的特殊情況，操作是相同的。

單鏈表第i個(gè)數(shù)據(jù)插入結(jié)點(diǎn)的算法思路：

聲明一個(gè)結(jié)點(diǎn)p指向鏈表第一個(gè)結(jié)點(diǎn)，初始化j從1開(kāi)始；

當(dāng)j<i時(shí)，就遍歷鏈表，讓p的指針向后移動(dòng)，不斷指向下一個(gè)結(jié)點(diǎn)，j++；

若到鏈表末尾p為空，則說(shuō)明第i個(gè)元素不存在；

否則查找成功，在系統(tǒng)中生成一個(gè)空結(jié)點(diǎn)s；

將數(shù)據(jù)元素e賦值給s->data；

單鏈表的插入標(biāo)準(zhǔn)語(yǔ)句是 s->next=p->next;p->next=s;

返回成功

實(shí)現(xiàn)代碼

Status ListInsert(LinkList *L,int i,ElemType e){int j;LinkList p,s;p=*L;j=1;while(p&& j<i){ // 尋找第i個(gè)結(jié)點(diǎn),退出條件是p為空或者 j==ip=p->next;++j;}if(!p || j>i){return ERROR; //不存在第i個(gè)元素}s=(LinkList)malloc(sizeof(Node)); //生成新結(jié)點(diǎn)s->data=e;//賦值s->next=p->next; //插入結(jié)點(diǎn)sp->next=s;return OK;}

在這段代碼中，我們用到了C語(yǔ)言的malloc函數(shù)，它的作用是生成一個(gè)新的結(jié)點(diǎn)，其類型與Node一樣，其實(shí)質(zhì)就是在內(nèi)存中找了一小塊空地，準(zhǔn)備用來(lái)存放e數(shù)據(jù)s結(jié)點(diǎn)。

3.8.2 單鏈表的刪除

設(shè)存儲(chǔ)元素ai的結(jié)點(diǎn)為q，現(xiàn)在要實(shí)現(xiàn)將結(jié)點(diǎn)q刪除單鏈表的操作，其實(shí)就是將它的前驅(qū)結(jié)點(diǎn)的指針繞過(guò)q，指向它的后繼結(jié)點(diǎn)即可。如圖3-8-5所示。

我們要做的其實(shí)就是一步：p->next=p->next->next; 用q來(lái)代替p->next 就是

q=p->next; p->next=q->next;

單鏈表第i個(gè)數(shù)據(jù)刪除結(jié)點(diǎn)的算法思路：

聲明一個(gè)結(jié)點(diǎn)p指向鏈表的第一個(gè)結(jié)點(diǎn)，初始化j從1開(kāi)始；

當(dāng)j<i時(shí)，就遍歷鏈表，讓p的指針向后移動(dòng)，不斷指向下一個(gè)結(jié)點(diǎn)，j++；

若到鏈表末尾p為空，則說(shuō)明第i個(gè)元素不存在；

否則查找成功，將欲刪除的結(jié)點(diǎn)p->next 賦值為q；

單鏈表的刪除標(biāo)準(zhǔn)語(yǔ)句：p->next=q->next;

將q結(jié)點(diǎn)中的數(shù)據(jù)賦值為e，作為返回；

釋放q結(jié)點(diǎn)；

返回成功。

代碼實(shí)現(xiàn)：

Status ListDelete(LinkList *L,int i,ElemType *e){int j;LinkList p,q;//結(jié)點(diǎn)p和qp=*L;//指向第一個(gè)結(jié)點(diǎn)j=1;while(p->next && j<i){ //遍歷尋找第i個(gè)元素（即p->next）p=p->next;++j;}if(!(p->next)||j>i){ //第i個(gè)元素不存在return ERROR; }q=p->next;p->next=q->next;*e=q->data; //將q結(jié)點(diǎn)中的數(shù)據(jù)給efree(q); //系統(tǒng)回收該結(jié)點(diǎn)，釋放內(nèi)存return OK; }

這段代碼中，我們用到了C語(yǔ)言標(biāo)準(zhǔn)函數(shù)free，它的作用是讓系統(tǒng)回收一個(gè)Node結(jié)點(diǎn)，釋放內(nèi)存。

分析一下單鏈表的插入和刪除操作，其實(shí)它們由兩部分組成：第一部分就是遍歷查找第i個(gè)元素；第二部分就是插入和刪除元素。

從整個(gè)算法來(lái)說(shuō)，我們?nèi)菀淄茢喑?#xff1a;它們的時(shí)間復(fù)雜度都是O(n)。如果不知道第i個(gè)元素的指針位置，單鏈表數(shù)據(jù)結(jié)構(gòu)在插入和刪除操作上，與線性表的順序存儲(chǔ)結(jié)構(gòu)相比沒(méi)有太大優(yōu)勢(shì)。但如果，我們希望從第i個(gè)位置開(kāi)始，插入10個(gè)元素，對(duì)于順序存儲(chǔ)結(jié)構(gòu)意味著，每一個(gè)插入都需要移動(dòng)n-i個(gè)元素，每次都是O(n)。而單鏈表，我們只需要在第一次時(shí)，找到第i個(gè)位置的指針，此時(shí)為O(n)，接下來(lái)只是簡(jiǎn)單地通過(guò)賦值移動(dòng)指針而已，時(shí)間復(fù)雜度都是O(1)。顯然，對(duì)于插入或刪除數(shù)據(jù)頻繁的情形，單鏈表的效率優(yōu)勢(shì)就很明顯了。

3.9 單鏈表的整表創(chuàng)建

回顧一下，順序存儲(chǔ)結(jié)構(gòu)的創(chuàng)建，其實(shí)就是數(shù)組的初始化過(guò)程，即聲明一個(gè)類型和大小確定的數(shù)組并賦值的過(guò)程。而單鏈表和順序存儲(chǔ)結(jié)構(gòu)不一樣，它不像順序存儲(chǔ)結(jié)構(gòu)那樣集中，它可以很分散，是一種動(dòng)態(tài)結(jié)構(gòu)。對(duì)于每個(gè)鏈表來(lái)說(shuō)，它所占用的空間的大小和位置是不需要提前分配的，可以根據(jù)系統(tǒng)的情況和實(shí)際的需求及時(shí)生成。

所以創(chuàng)建單鏈表的過(guò)程就是一個(gè)動(dòng)態(tài)生成鏈表的過(guò)程，即從“空表”的初始狀態(tài)起，依次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表。

單鏈表整表創(chuàng)建的算法思路：

聲明一個(gè)結(jié)點(diǎn)p和計(jì)數(shù)器變量i；

初始化一空鏈表L；

讓L的頭結(jié)點(diǎn)的指針指向NULL，即建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表；

循環(huán)：生成一新結(jié)點(diǎn)賦值給p；隨機(jī)生成一數(shù)字賦值給p的數(shù)據(jù)域p->data;將p插入到頭結(jié)點(diǎn)與前一新結(jié)點(diǎn)之間。

實(shí)現(xiàn)代碼（頭插法）：

void CreateListHead( LinkList *L,int n){LinkList p;int i;srand(time(0)); //初始化隨機(jī)數(shù)種子*L=(LinkList)malloc(sizeof(Node)); (*L)->next=NULL;//建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=0;i<n;i++){p=(LinkList)malloc(sizeof(Node)); //生成新結(jié)點(diǎn)p->data=rand()%100+1;//隨機(jī)生成100以內(nèi)的數(shù)字p->next=(*L)->next;(*L)->next=p;//插入到表頭}}

這段代碼里，我們其實(shí)用的是插隊(duì)的辦法，就是始終讓新結(jié)點(diǎn)在第一的位置，因此稱為頭插法。如圖所示

可事實(shí)上，我們還是可以不這樣干，為什么不把新結(jié)點(diǎn)都放到最后呢？這才是排隊(duì)時(shí)的正常思維啊，所謂的先來(lái)后到。我們把每次新結(jié)點(diǎn)都插入到終端結(jié)點(diǎn)的后面，這種算法稱為尾插法。

實(shí)現(xiàn)代碼（尾插法）：

void CreateListTail(LinkList *L,int n){LinkList p,r;int i;srand(time(0));*L=(LinkList)malloc(sizeof(Node)); //L是整個(gè)單鏈表r=*L;//r為指向尾部的結(jié)點(diǎn)for(i=0;i<n;i++){p=(Node *)malloc(sizeof(Node)); //生成新結(jié)點(diǎn)p->data=rand()%100+1;r->next=p;r=p;//將當(dāng)前的新結(jié)點(diǎn)定義為尾部終端結(jié)點(diǎn)}r->next=NULL; //表示當(dāng)前鏈表結(jié)束}

注意L和r的關(guān)系，L是指整個(gè)單鏈表，而r是指向尾結(jié)點(diǎn)的變量，變量r會(huì)隨著循環(huán)不斷變化，而L則是隨著循環(huán)增長(zhǎng)為一個(gè)多結(jié)點(diǎn)的鏈表。

3.10 單鏈表的整表刪除

當(dāng)我們不打算使用這個(gè)單鏈表時(shí)，我們需要把它銷毀，其實(shí)也就是在內(nèi)存中將它釋放掉，以便于留出空間給其他程序或軟件使用。

單鏈表整表刪除的算法思路如下：

聲明一結(jié)點(diǎn)p和q；

將第一個(gè)結(jié)點(diǎn)賦值給p；

循環(huán)：將下一結(jié)點(diǎn)賦值給q；釋放p；將q賦值給p。

實(shí)現(xiàn)代碼

Status ClearList(LinkList *L){//默認(rèn)鏈表帶有頭結(jié)點(diǎn)LinkList p,q;//申明兩個(gè)結(jié)構(gòu)體變量，即結(jié)點(diǎn)p=(*L)->next; //p指向第一個(gè)結(jié)點(diǎn)while(p){// 沒(méi)到表尾q=p->next;free(p);p=q;}(*L)->next=NULL; //頭結(jié)點(diǎn)指針域?yàn)榭?/span>return OK;}

這段代碼里，常見(jiàn)的錯(cuò)誤就是有同學(xué)會(huì)覺(jué)得q變量沒(méi)有必要存在。在循環(huán)體中直接寫(xiě)free§;p=p->next;不就行了嗎？可這樣會(huì)帶來(lái)什么問(wèn)題？

要知道p是一個(gè)結(jié)點(diǎn)，它除了有數(shù)據(jù)域，還有指針域。在做free (p )時(shí)，其實(shí)是對(duì)它整個(gè)結(jié)點(diǎn)進(jìn)行刪除和內(nèi)存釋放的工作。直接刪除就不知道和它關(guān)聯(lián)的后繼是誰(shuí)了，而變量q的作用，使得下一個(gè)結(jié)點(diǎn)是誰(shuí)得到記錄，以便等當(dāng)前結(jié)點(diǎn)釋放后，把下一個(gè)結(jié)點(diǎn)拿過(guò)來(lái)補(bǔ)充。

3.11 單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)

簡(jiǎn)單地對(duì)單鏈表結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)做對(duì)比：

存儲(chǔ)分配方式時(shí)間性能空間性能

順序存儲(chǔ)結(jié)構(gòu)用一段連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素	查找性能：順序存儲(chǔ)結(jié)構(gòu)O(1);單鏈表O(n)	順序存儲(chǔ)結(jié)構(gòu)需要預(yù)分配存儲(chǔ)空間，分大了浪費(fèi)；分小了易發(fā)生上溢
單鏈表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用一組任意的存儲(chǔ)單元存放線性表的元素	插入和刪除性能：順序存儲(chǔ)結(jié)構(gòu)需要平均移動(dòng)表長(zhǎng)一半的元素，時(shí)間為O(n);單鏈表在找出某位置的指針后，插入和刪除時(shí)間僅為O(1)	單鏈表不需要分配存儲(chǔ)空間，只要有就可以分配，元素個(gè)數(shù)不受限制

通過(guò)上面的對(duì)比，我們可以得到一些經(jīng)驗(yàn)性的結(jié)論：

• 若線性表需要頻繁查找，很少進(jìn)行插入和刪除操作時(shí)，宜采用順序存儲(chǔ)結(jié)構(gòu)。若需要頻繁插入和刪除時(shí)，宜采用單鏈表結(jié)構(gòu)。比如說(shuō)，游戲開(kāi)發(fā)中，對(duì)于用戶注冊(cè)的個(gè)人信息，除了注冊(cè)時(shí)插入數(shù)據(jù)外，絕大多數(shù)情況都是讀取，所以應(yīng)該考慮用順序存儲(chǔ)結(jié)構(gòu)。而游戲中玩家的武器或者裝備列表，隨著玩家的游戲過(guò)程，可能會(huì)隨時(shí)增加或刪除，此時(shí)再用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)就不太適合了，單鏈表結(jié)構(gòu)就可以大展身手。當(dāng)然，這只是簡(jiǎn)單類比，現(xiàn)實(shí)中軟件開(kāi)發(fā)還需要考慮更多的問(wèn)題。
• 當(dāng)線性表中的元素個(gè)數(shù)變化較大或者根本不知道有多大時(shí)，最好用單鏈表結(jié)構(gòu)，這樣可以不需要考慮存儲(chǔ)空間的大小問(wèn)題。而如果事先知道線性表的大致長(zhǎng)度，比如一年12個(gè)月，這種采用順序存儲(chǔ)結(jié)構(gòu)效率會(huì)高很多。

總之，線性表的順序存儲(chǔ)結(jié)構(gòu)和單鏈表結(jié)構(gòu)各有優(yōu)缺點(diǎn)，不能簡(jiǎn)單說(shuō)哪個(gè)好，哪個(gè)不好。

3.12 靜態(tài)鏈表

C語(yǔ)言具有指針功能，使得它可以容易地操作內(nèi)存中的地址和數(shù)據(jù)，而對(duì)于一些語(yǔ)言，由于沒(méi)有指針，鏈表結(jié)構(gòu)是如何實(shí)現(xiàn)的呢？

有人就想出用數(shù)組代替指針，來(lái)描述單鏈表。

首先我們讓數(shù)組的元素都是由兩個(gè)數(shù)據(jù)域組成，data和cur。也就是說(shuō)，數(shù)組的每個(gè)下標(biāo)都對(duì)應(yīng)一個(gè)data和一個(gè)cur。數(shù)據(jù)域data，用來(lái)存放數(shù)據(jù)元素，也就是通常我們要處理的數(shù)據(jù)；而游標(biāo)cur相當(dāng)于單鏈表中的next指針，存放該元素的后繼在數(shù)組中的下標(biāo)。

我們把這種用數(shù)組描述的鏈表叫做靜態(tài)鏈表。

為了便于插入數(shù)據(jù)，通常會(huì)把數(shù)組建的大一些，以便有一些空閑空間可以使得插入時(shí)不會(huì)溢出。

#define MAZSIZE 1000 typedef struct{ElemType data;int cur; //游標(biāo)，為0時(shí)表示無(wú)指向 }Component,StaticLinkList[MAXSIZE];

另外我們把數(shù)組的第一個(gè)和最后一個(gè)元素作為特殊元素處理，不存放數(shù)據(jù)。通常把未被使用的數(shù)組元素組成的數(shù)組稱為備用鏈表。而數(shù)組的第一個(gè)元素，即下標(biāo)為0的元素的cur就存放備用鏈表的第一個(gè)結(jié)點(diǎn)的下標(biāo)；而數(shù)組的最后一個(gè)元素的cur則存放第一個(gè)有數(shù)值的元素的下標(biāo)，相當(dāng)于單鏈表中的頭結(jié)點(diǎn)，當(dāng)整個(gè)鏈表為空時(shí)，則為0.如下圖所示

此時(shí)圖示相當(dāng)于初始化的數(shù)組狀態(tài)，見(jiàn)下面代碼

//將一維數(shù)組space中各分量連成一個(gè)備用鏈表 //space[0].cur為頭指針，0表示空指針 Status InitList(StaticLinkList space){int i;for(i=0;i<MAXSIZE-1;i++)space[i].cur=i+1;space[MAXSIZE-1].cur=0;//目前靜態(tài)鏈表為空，最后一個(gè)元素的cur為0return OK; }

假設(shè)我們已經(jīng)將數(shù)據(jù)存入靜態(tài)鏈表，比如分別存放著甲乙丙丁戊己庚等數(shù)據(jù)

此時(shí)，“甲”這里就存有下一元素“乙”的游標(biāo)2，“乙”則存放著下一元素“丁”的下標(biāo)3.而“庚”是最后一個(gè)有值元素，所以它的cur設(shè)置為0.而最后一個(gè)元素的cur則因?yàn)椤凹住笔堑谝挥兄翟?#xff0c;所以存有“甲”的下標(biāo)1.而第一個(gè)元素則因?yàn)榭臻e空間的第一個(gè)元素下標(biāo)為7，所以它的cur存有7.

3.12.1 靜態(tài)鏈表的插入操作

靜態(tài)鏈表要解決的是：如何用靜態(tài)模擬動(dòng)態(tài)鏈表結(jié)構(gòu)的存儲(chǔ)空間的分配，需要時(shí)申請(qǐng)，無(wú)用時(shí)釋放。

我們前面說(shuō)過(guò)，在動(dòng)態(tài)鏈表中，結(jié)點(diǎn)的申請(qǐng)和釋放分別通過(guò)malloc和free兩個(gè)函數(shù)來(lái)實(shí)現(xiàn)。在靜態(tài)鏈表中，操作的是數(shù)組，不存在像動(dòng)態(tài)鏈表的結(jié)點(diǎn)申請(qǐng)和釋放問(wèn)題，所以我們需要自己實(shí)現(xiàn)這兩個(gè)函數(shù)，才可以做插入和刪除的操作。

為了辨明數(shù)組中哪些分量未被使用，解決的辦法是將所有未被使用過(guò)和已被刪除的分量用游標(biāo)鏈接成一個(gè)備用的鏈表，每當(dāng)進(jìn)行插入時(shí)，便可以從備用鏈表上取得第一個(gè)結(jié)點(diǎn)作為待插入的新結(jié)點(diǎn)。

//若備用空間鏈表非空，則返回分配的結(jié)點(diǎn)下標(biāo)，否則返回0 int Malloc_SLL(StaticLinkList space){int i=space[0].cur; //當(dāng)前備用鏈表第一個(gè)結(jié)點(diǎn)iif(space[0].cur){ //如果結(jié)點(diǎn)i被分配space[0].cur=space[i].cur;// 把i的后繼作為備用鏈表的第一個(gè)結(jié)點(diǎn)} return i; //返回分配的結(jié)點(diǎn)下標(biāo)i}

這段代碼，一方面返回一個(gè)下標(biāo)值，這個(gè)值就是數(shù)組頭元素的cur，它里面存的第一個(gè)空閑的下標(biāo)，從下圖可以看到，這個(gè)值是7.

那么既然下標(biāo)為7的分量準(zhǔn)備要使用了，就得有接替者，所以就把分量7的cur值賦值給頭元素，也就是把8給space[0].cur，之后就可以繼續(xù)分配新的空間分量，實(shí)現(xiàn)類似malloc函數(shù)的作用。（這里需要理解一下，筆者第一遍只看代碼沒(méi)看解釋時(shí)，感到有點(diǎn)迷惑。）

現(xiàn)在我們?nèi)绻枰凇耙摇焙汀岸　敝g，插入一個(gè)值為“丙”的元素，按照以前順序存儲(chǔ)結(jié)構(gòu)的做法，應(yīng)該把后面這些元素往后移，但目前我們不需要，因?yàn)槲覀冇辛诵碌氖侄巍?/p>

新元素“丙”，想插隊(duì)是吧？可以，你先悄悄地在隊(duì)伍最后一排第7個(gè)游標(biāo)位置呆著，我一會(huì)兒就幫你搞定。我接著找到了“乙”，告訴他，你的cur不是游標(biāo)3的“丁”了，這點(diǎn)小錢，意思意思，你把你的下一位的游標(biāo)改為7就可以了。“乙”嘆一口氣，收了錢把cur值給改了。此時(shí)再回到“丙”那里，說(shuō)你把你的cur改為3.就這樣，在絕大多數(shù)人都不知道的情況下，整個(gè)排隊(duì)的次序發(fā)生了變化。如圖所示

代碼

• 當(dāng)我們執(zhí)行插入語(yǔ)句時(shí)，我們的目的是要在“乙”“丁”插入“丙”。調(diào)用代碼時(shí)，輸入i值為3.
• 第3行讓k=MAXSIZE-1=999;
• 第5行，j=Malloc_SLL(L)=7;此時(shí)下標(biāo)為0的cur也因?yàn)?要被占用而更改為備用鏈表的值為8.
• 第8~9行，for循環(huán)l由1到2（因?yàn)閕=3），執(zhí)行兩次.代碼k=L[k].cur=L[999].cur=1，再得到k=L[1].cur=2;
• 第10行，L[j].cur=L[k].cur；因?yàn)閖=7，而k=2，得到L[7].cur=L[2].cur=3.這就是剛才讓“丙”把它的cur改為3，即丙的后面是丁。
• 第11行，L[k].cur=j;意思就是L[2].cur=7。也就是讓“乙”得點(diǎn)好處，把它的cur改為指向“丙”的下標(biāo)。

就這樣，我們實(shí)現(xiàn)了在數(shù)組中，實(shí)現(xiàn)不移動(dòng)元素，卻插入了數(shù)據(jù)的操作。

//在L中第i個(gè)元素之前插入新的數(shù)據(jù)元素e Status ListInsert(StaticLinkList L,int i,ElemType e){int j,k,l;k=MAXSIZE-1; //注意k首先是最后一個(gè)元素的下標(biāo)if(i<1 || i>ListLength(L)-1) return ERROR; j=Malloc_SLL(L);//獲得空閑分量的下標(biāo) if(j){L[j].data=e;for(l=1;l<=i-1;l++) //找到第i個(gè)元素之前的位置k=L[k].cur;L[j].cur=L[k].cur;//把第i個(gè)元素之前的cur賦值給新元素的curL[k].cur=j;//把新元素的下標(biāo)賦值給第i個(gè)元素之前元素的curreturn OK;}return ERROR; }

3.12.2 靜態(tài)鏈表的刪除操作

故事沒(méi)完，接著，排在第一位的甲突然接到一個(gè)電話，看著很急，毫不猶豫就匆匆離開(kāi)。這意味著第一位空出來(lái)了，那么自然剛才的乙便排到了第一位。和前面一樣，刪除元素時(shí)，原來(lái)是需要釋放結(jié)點(diǎn)的函數(shù)free，現(xiàn)在我們也得自己實(shí)現(xiàn)它

//刪除在L中第i個(gè)數(shù)據(jù)元素e Status ListDelete(StaticLinkList L,int i){int j,k;if(i<1 || i>ListLength(L)-1) return ERROR;k=MAXSIZE-1;for(j=1;j<=i-1;j++)k=L[k].cur;//k得到i前面的結(jié)點(diǎn)j=L[k].cur;//得到第i個(gè)結(jié)點(diǎn)L[k].cur=L[j].cur; //把乙的位置賦給k這個(gè)結(jié)點(diǎn)的cur,就是刪除了甲Free_SLL(L,j);return OK;}

Free_SLL(L,j)是什么意思呢？ 來(lái)看代碼

//將下標(biāo)為k的空閑結(jié)點(diǎn)回收到備用鏈表void Free_SLL(StaticLinkList space ,int k){space[k].cur=space[0].cur; //k這個(gè)結(jié)點(diǎn)的后繼是原來(lái)空閑鏈表的第一個(gè)結(jié)點(diǎn)space[0].cur=k; //備用鏈表的第一個(gè)結(jié)點(diǎn)變成 k這個(gè)結(jié)點(diǎn) }

意思就是“甲”現(xiàn)在要走，這個(gè)位置就空出來(lái)了，也就是，未來(lái)如果有新人來(lái)，最優(yōu)先考慮這里，所以原來(lái)的第一個(gè)空位分量，即下標(biāo)是8的分量，它降級(jí)了，把8給“甲”所在下標(biāo)為1的分量的cur，也就是space[1].cur=space[0].cur=8,而space[0].cur=k=1 其實(shí)就是讓這個(gè)刪除的位置成為第一個(gè)優(yōu)先空位，把它存入第一個(gè)元素的cur中，如圖所示

備注：如果這里不好理解，可能是對(duì)第一個(gè)元素和最后一個(gè)元素的作用有所淡忘，這里再次貼出便于復(fù)習(xí)。

數(shù)組的第一個(gè)元素，即下標(biāo)為0的元素的cur就存放備用鏈表的第一個(gè)結(jié)點(diǎn)的下標(biāo)；而數(shù)組的最后一個(gè)元素的cur則存放第一個(gè)有數(shù)值的元素的下標(biāo)，相當(dāng)于單鏈表中的頭結(jié)點(diǎn)，當(dāng)整個(gè)鏈表為空時(shí)，則為0.如下圖所示

當(dāng)然，靜態(tài)鏈表也有相應(yīng)的其他操作的相關(guān)實(shí)現(xiàn)，比如前面代碼中出現(xiàn)的ListLength就是一個(gè)，來(lái)看代碼

int ListLength(StaticLinkList L){int j=0;int i=L[MAXSIZE-1].cur;//第1個(gè)元素的下標(biāo)while(i){//沒(méi)到空結(jié)點(diǎn)i=L[i].cur;//后移j++;//計(jì)數(shù)器++}return j;//返回計(jì)數(shù)器}

3.12.3 靜態(tài)鏈表優(yōu)缺點(diǎn)

總結(jié)一下靜態(tài)鏈表的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)缺點(diǎn)

在插入和刪除操作時(shí)，只需要修改游標(biāo)，不需要移動(dòng)元素，從而改進(jìn)了在順序存儲(chǔ)結(jié)構(gòu)中的插入和刪除操作需要大量移動(dòng)元素的缺點(diǎn)	1.沒(méi)有解決連續(xù)存儲(chǔ)分配帶來(lái)的表長(zhǎng)難以確定的問(wèn)題；2.失去了順序存儲(chǔ)結(jié)構(gòu)隨機(jī)存取（存取時(shí)間都是O(1)）的特性

總的來(lái)說(shuō)，靜態(tài)鏈表其實(shí)是為了給沒(méi)有指針的高級(jí)語(yǔ)言設(shè)計(jì)的一種實(shí)現(xiàn)單鏈表功能的辦法。盡管大家不一定會(huì)用得上，但是這樣的思考方法是很巧妙的，應(yīng)該理解其思想，以備不時(shí)之需。

3.13 循環(huán)鏈表

對(duì)于單鏈表，由于每個(gè)結(jié)點(diǎn)只存儲(chǔ)了向后的指針，到了尾標(biāo)志就停止了向后鏈的操作，這樣，當(dāng)中某一結(jié)點(diǎn)就無(wú)法找到它的前驅(qū)結(jié)點(diǎn)了。也就是說(shuō)，從當(dāng)中一個(gè)結(jié)點(diǎn)遍歷整個(gè)鏈表，對(duì)單鏈表來(lái)說(shuō)是不可能的。

將單鏈表中終端結(jié)點(diǎn)的指針端由空指針改為指向頭結(jié)點(diǎn)，就使整個(gè)單鏈表形成一個(gè)環(huán)，這種頭尾相接的單鏈表稱為單循環(huán)鏈表，簡(jiǎn)稱循環(huán)鏈表（circular linked list）.

這樣，循環(huán)鏈表解決了一個(gè)很麻煩的問(wèn)題，就如如何從當(dāng)中一個(gè)結(jié)點(diǎn)出發(fā)，訪問(wèn)到鏈表的全部結(jié)點(diǎn)。

為了使空鏈表和非空鏈表處理一致，我們通常設(shè)一個(gè)頭結(jié)點(diǎn)，當(dāng)然，這并不是說(shuō)，循環(huán)鏈表一定要頭結(jié)點(diǎn)，這需要注意。 循環(huán)鏈表帶有頭結(jié)點(diǎn)的空鏈表如下圖所示

而非空的循環(huán)鏈表如下圖

其實(shí)循環(huán)鏈表和單鏈表的主要差異就在于循環(huán)的判斷條件上，原來(lái)是判斷p->next是否為空，現(xiàn)在則是p->next不等于頭結(jié)點(diǎn)，則循環(huán)未結(jié)束。

在單鏈表中，我們有了頭結(jié)點(diǎn)時(shí)，可以用O(1)的時(shí)間訪問(wèn)到第一個(gè)結(jié)點(diǎn)，但對(duì)于要訪問(wèn)到最后一個(gè)結(jié)點(diǎn)，卻需要O(n)的時(shí)間，因?yàn)槲覀冃枰獙捂湵砣繏呙枰槐椤?/p>

有沒(méi)有可能用O(1)的時(shí)間由鏈表指針訪問(wèn)到最后一個(gè)結(jié)點(diǎn)呢？當(dāng)然可以。

不過(guò)我們需要改造一下這個(gè)循環(huán)鏈表，不用頭指針，而是用指向終端結(jié)點(diǎn)的尾指針來(lái)表示循環(huán)鏈表，如下圖所示，此時(shí)查找開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便。

從上圖可以看出，終端結(jié)點(diǎn)用尾指針rear指示，則查找終端結(jié)點(diǎn)是O(1),而開(kāi)始結(jié)點(diǎn)，其實(shí)就是rear->next->next，其時(shí)間復(fù)雜度也是O(1).

舉個(gè)程序的例子，要將兩個(gè)循環(huán)鏈表合并成一個(gè)表時(shí)，有了尾指針就很簡(jiǎn)單。比如下面的兩個(gè)循環(huán)鏈表，它們的尾指針?lè)謩e是rearA和rearB。

要想把它們合并，只需要如下的操作即可

p=rearA->next;//保存A表的頭結(jié)點(diǎn) 對(duì)應(yīng)序號(hào)① rearA->next=rearB->next->next; // 連接序號(hào)② rearB->next=p; //將原A表的頭結(jié)點(diǎn)賦值給rearB->next ,即序號(hào)③ free(p); //釋放p

3.14 雙向鏈表

我們?cè)趩捂湵碇?#xff0c;有了next指針，這就使得我們要查找下一結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)。可是如果我們要查找的是上一結(jié)點(diǎn)的話，那最壞的時(shí)間復(fù)雜度便是O(n)，因?yàn)槲覀兠看味家獜念^開(kāi)始遍歷查找。

為了克服單向鏈表的這一缺點(diǎn)，哪些老科學(xué)家們，設(shè)計(jì)了雙向鏈表。雙向鏈表(double linked list)是在單鏈表的每個(gè)結(jié)點(diǎn)中，再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域。所以在雙向鏈表中的結(jié)點(diǎn)都有兩個(gè)指針域，一個(gè)指向直接后繼，一個(gè)指向直接前驅(qū)。

//線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu) typedef struct DulNode{ElemType data;struct DulNode *prior; //直接前驅(qū)指針struct DulNode *next; //直接后繼指針 }DulNode,*DuLinkList;

既然單鏈表也可以有循環(huán)鏈表，那么雙向鏈表當(dāng)然也可以是循環(huán)鏈表。
雙向鏈表的循環(huán)帶頭結(jié)點(diǎn)的空鏈表如下圖

非空的循環(huán)的帶頭結(jié)點(diǎn)的雙向鏈表如下圖所示

由于這是雙向鏈表，那么對(duì)于鏈表中的某一個(gè)結(jié)點(diǎn)p，它的后繼的前驅(qū)是誰(shuí)？當(dāng)然還是它自己。它的前驅(qū)的后繼自然也是它自己。即

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

這就如同上海的下一站是蘇州，那么上海的下一站的前一站是哪里？ 廢話哦。

雙向鏈表是單鏈表擴(kuò)展出來(lái)的結(jié)構(gòu)，所以它的很多操作是和單鏈表相同的，比如求長(zhǎng)度的ListLength，查找元素的GetElem，獲得元素位置的LocateElem等，這些操作都只要涉及一個(gè)方向的指針即可，另一指針多了也不能提供什么幫助。

就像人生一樣，想享樂(lè)就得先努力，欲收獲就得付代價(jià)。雙向鏈表既然是比單鏈表多了比如可以反向遍歷等功能的數(shù)據(jù)結(jié)構(gòu)，那么也就需要付出一些小的代價(jià)：在插入和刪除時(shí)，需要更改兩個(gè)指針變量。

插入操作時(shí)，其實(shí)并不復(fù)雜，不過(guò)順序很重要，千萬(wàn)不能寫(xiě)反。

我們現(xiàn)在假設(shè)存儲(chǔ)元素e的結(jié)點(diǎn)為s，要實(shí)現(xiàn)將結(jié)點(diǎn)s插入到結(jié)點(diǎn)p和結(jié)點(diǎn)p->next之間需要下面幾步，如下圖

s->prior=p;//把p賦值給s的前驅(qū) s->next=p->next;//把p->next賦值給s的后繼 p->next->prior=s;把s賦值給p->next的前驅(qū) p->next=s;//把s賦值給p的后繼

關(guān)鍵在于它們的順序，由于第2步和第3步都用到了p->next，如果第4步先執(zhí)行，則會(huì)使得p->next提前變成了是，使得插入的工作完成不了。所以我們不妨把上面這張圖在理解的基礎(chǔ)上進(jìn)行記憶，順序是先搞定s的前驅(qū)和后繼，再搞定后結(jié)點(diǎn)的前驅(qū)，最后解決前結(jié)點(diǎn)的后繼。

如果插入操作理解了，那么刪除操作，就比較簡(jiǎn)單了。

若要?jiǎng)h除結(jié)點(diǎn)p，只需要下面兩步驟，如下圖

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

好了，簡(jiǎn)單總結(jié)一下，雙向鏈表相對(duì)于單鏈表來(lái)說(shuō)，要更復(fù)雜一些，畢竟它多了prior指針，對(duì)于插入和刪除操作，需要格外小心。另外它由于每個(gè)結(jié)點(diǎn)都需要記錄兩份指針，所以在空間上是要占用略多一些的。不過(guò)，由于它良好的對(duì)稱性，使得對(duì)某個(gè)結(jié)點(diǎn)的前后節(jié)點(diǎn)的操作，變得很方便，可以有效提高算法的時(shí)間性能。說(shuō)白了，就是用空間換時(shí)間。

3.15 總結(jié)

總結(jié)

以上是生活随笔為你收集整理的《大话数据结构》读书笔记-线性表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。