一口氣搞懂「鏈表」，就靠這20+張圖了

說真的，任何說起嵌入式軟件怎么入門啊？需要學(xué)些什么東西啊，我差不多一致的回答都是：軟件方面C語言和數(shù)據(jù)結(jié)構(gòu)加上一些簡單常用的算法，這些需要學(xué)好。

借著自己的回顧學(xué)習(xí)，我也寫一些基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)知識，多畫圖，少BB，與大家一起學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

順序存儲和鏈?zhǔn)酱鎯?/h2>

數(shù)組—順序存儲

數(shù)組作為一個順序儲存方式的數(shù)據(jù)結(jié)構(gòu)，可是有大作為的，它的靈活使用為我們的程序設(shè)計帶來了大量的便利；

但是，但是，數(shù)組最大的缺點就是我們的插入和刪除時需要移動大量的元素，所以呢，大量的消耗時間，以及冗余度難以接受了。

以C語言數(shù)組插入一個元素為例，當(dāng)我們需要在一個數(shù)組{1,2,3,4}的第1個元素后的位置插入一個’A’時，我們需要做的有：

1. 將第1個元素后的整體元素后移，形成新的數(shù)組{1,2,2,3,4}

2. 再將第2個元素位置的元素替換為我們所需要的元素’A’

3. 最終形成我們的預(yù)期，這需要很多的操作喔。

上圖可以看出，使用數(shù)組都有這兩大缺點：

1. 插入刪除操作所需要移動的元素很多，浪費算力。

2. 必須為數(shù)組開足夠的空間，否則有溢出風(fēng)險。

鏈表—鏈?zhǔn)酱鎯?span style="display: none;">

由于數(shù)組的這些缺點，自然而然的就產(chǎn)生鏈表的思想了。

鏈表通過不連續(xù)的儲存方式，自適應(yīng)內(nèi)存大小，以及指針的靈活使用，巧妙的簡化了上述的內(nèi)容。

鏈表的基本思維是，利用結(jié)構(gòu)體的設(shè)置，額外開辟出一份內(nèi)存空間去作指針，它總是指向下一個結(jié)點，一個個結(jié)點通過NEXT指針相互串聯(lián)，就形成了鏈表。

其中DATA為自定義的數(shù)據(jù)類型，NEXT為指向下一個鏈表結(jié)點的指針，通過訪問NEXT，可以引導(dǎo)我們?nèi)ピL問鏈表的下一個結(jié)點。

對于一連串的結(jié)點而言，就形成了鏈表如下圖：

上文所說的插入刪除操作只需要修改指針?biāo)赶虻膮^(qū)域就可以了，不需要進(jìn)行大量的數(shù)據(jù)移動操作。如下圖：

相比起數(shù)組，鏈表解決了數(shù)組不方便移動，插入，刪除元素的弊端，但相應(yīng)的，鏈表付出了更加大的內(nèi)存犧牲換來的這些功能的實現(xiàn)。

鏈表概述

包含單鏈表，雙鏈表，循環(huán)單鏈表，實際應(yīng)用中的功能不同，但實現(xiàn)方式都差不多。

• 單鏈表就像是美國男籃，一代一代往下傳；

• 雙鏈表像是中國男足，你傳球給我，我傳球給你，最終傳給了守門員；

• 循環(huán)鏈表就像是中國男籃，火炬從姚明傳給王治郅，王治郅傳給易建聯(lián)，現(xiàn)在易建聯(lián)傷了，又傳給了姚明

單鏈表

單鏈表概念和簡單的設(shè)計

單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，鏈表中的數(shù)據(jù)是以結(jié)點來表示的，每個結(jié)點由元素和指針構(gòu)成。

元素表示數(shù)據(jù)元素的映象，就是存儲數(shù)據(jù)的存儲單元；指針指示出后繼元素存儲位置，就是連接每個結(jié)點的地址數(shù)據(jù)。

以結(jié)點的序列表示的線性表稱作線性鏈表，也就是單鏈表，單鏈表是鏈?zhǔn)酱嫒〉慕Y(jié)構(gòu)。

對于鏈表的每一個結(jié)點，我們使用結(jié)構(gòu)體進(jìn)行設(shè)計，其主要內(nèi)容有：

其中，DATA數(shù)據(jù)元素，可以為你想要儲存的任何數(shù)據(jù)格式，可以是數(shù)組，可以是int，甚至可以是結(jié)構(gòu)體（這就是傳說中的結(jié)構(gòu)體套結(jié)構(gòu)體）

NEXT為一個指針，其代表了一個可以指向的區(qū)域，通常是用來指向下一個結(jié)點，鏈表的尾部NEXT指向NULL（空），因為尾部沒有任何可以指向的空間了

故，對于一個單鏈表的結(jié)點定義，可以代碼描述成：

//定義結(jié)點類型
typedef?struct?Node?{
????int?data;???????//數(shù)據(jù)類型，你可以把int型的data換成任意數(shù)據(jù)類型，包括結(jié)構(gòu)體struct等復(fù)合類型
????struct?Node?*next;??????????//單鏈表的指針域
}?Node,*LinkedList;??
//Node表示結(jié)點的類型，LinkedList表示指向Node結(jié)點類型的指針類型

鏈表的初始化

初始化主要完成以下工作：創(chuàng)建一個單鏈表的前置節(jié)點并向后逐步添加節(jié)點，一般指的是申請結(jié)點的空間，同時對一個結(jié)點賦空值(NULL)，其代碼可以表示為：

LinkedList?listinit(){
????Node?*L;
????L=(Node*)malloc(sizeof(Node));??????//開辟空間?
????if(L==NULL){?????????????????????//判斷是否開辟空間失敗，這一步很有必要
????????printf("申請空間失敗");
????????//exit(0);??????????????????//開辟空間失敗可以考慮直接結(jié)束程序
????}
????L->next=NULL;???????//指針指向空
}

注意：一定要判斷是否開辟空間失敗，否則生產(chǎn)中由于未知的情況造成空間開辟失敗，仍然在繼續(xù)執(zhí)行代碼，后果將不堪設(shè)想啦，因此養(yǎng)成這樣的判斷是很有必要的。

頭插入法創(chuàng)建單鏈表

利用指針指向下一個結(jié)點元素的方式進(jìn)行逐個創(chuàng)建，使用頭插入法最終得到的結(jié)果是逆序的。如圖所示：

從一個空表開始，生成新結(jié)點，并將讀取到的數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭，即頭結(jié)點之后。

//頭插法建立單鏈表
LinkedList?LinkedListCreatH()?{
????Node?*L;
????L?=?(Node?*)malloc(sizeof(Node));???//申請頭結(jié)點空間
????L->next?=?NULL;??????????????????????//初始化一個空鏈表
??
????int?x;?????????????????????????//x為鏈表數(shù)據(jù)域中的數(shù)據(jù)
????while(scanf("%d",&x)?!=?EOF)?{
????????Node?*p;
????????p?=?(Node?*)malloc(sizeof(Node));???//申請新的結(jié)點
????????p->data?=?x;?????????????????????//結(jié)點數(shù)據(jù)域賦值
????????p->next?=?L->next;?????//將結(jié)點插入到表頭L-->|2|-->|1|-->NULL
????????L->next?=?p;
????}
????return?L;
}

尾插入法創(chuàng)建單鏈表

如圖所示為尾插入法的創(chuàng)建過程。

頭插法生成的鏈表中，結(jié)點的次序和輸入數(shù)據(jù)的順序不一致。若希望兩者次序一致，則需要尾插法。

該方法是將新結(jié)點逐個插入到當(dāng)前鏈表的表尾上，為此必須增加一個尾指針r, 使其始終指向當(dāng)前鏈表的尾結(jié)點，代碼如下：

//尾插法建立單鏈表
??
LinkedList?LinkedListCreatT()?{
????Node?*L;
????L?=?(Node?*)malloc(sizeof(Node));???//申請頭結(jié)點空間
????L->next?=?NULL;??????????????????//初始化一個空鏈表
????Node?*r;
????r?=?L;??????????????????????????//r始終指向終端結(jié)點，開始時指向頭結(jié)點
????int?x;?????????????????????????//x為鏈表數(shù)據(jù)域中的數(shù)據(jù)
????while(scanf("%d",&x)?!=?EOF)?{
????????Node?*p;
????????p?=?(Node?*)malloc(sizeof(Node));???//申請新的結(jié)點
????????p->data?=?x;?????????????????????//結(jié)點數(shù)據(jù)域賦值
????????r->next?=?p;????????????//將結(jié)點插入到表頭L-->|1|-->|2|-->NULL
????????r?=?p;
????}
????r->next?=?NULL;
????return?L;
}

遍歷單鏈表如打印、修改

從鏈表的頭開始，逐步向后進(jìn)行每一個元素的訪問，稱為遍歷。

對于遍歷操作，我們可以衍生出很多常用的數(shù)據(jù)操作，比如查詢元素，修改元素，獲取元素個數(shù)，打印整個鏈表數(shù)據(jù)等等。

進(jìn)行遍歷的思路極其簡單，只需要建立一個指向鏈表L的結(jié)點，然后沿著鏈表L逐個向后搜索即可，代碼如下：

//便利輸出單鏈表
void?printList(LinkedList?L){
????Node?*p=L->next;
????int?i=0;
????while(p){
????????printf("第%d個元素的值為:%d\n",++i,p->data);
????????p=p->next;
????}
}

對于元素修改操作，以下是代碼實現(xiàn)：

//鏈表內(nèi)容的修改，在鏈表中修改值為x的元素變?yōu)闉閗。
LinkedList?LinkedListReplace(LinkedList?L,int?x,int?k)?{
????Node?*p=L->next;
????int?i=0;
????while(p){
????????if(p->data==x){
????????????p->data=k;
????????}
????????p=p->next;
????}
????return?L;
}

簡單的遍歷設(shè)計的函數(shù)只需要void無參即可，而當(dāng)涉及到元素操作時，可以設(shè)計一個LinkedList類型的函數(shù)，使其返回一個操作后的新鏈表。

插入操作

鏈表的插入操作主要分為查找到第i個位置，將該位置的next指針修改為指向我們新插入的結(jié)點，而新插入的結(jié)點next指針指向我們i+1個位置的結(jié)點。

其操作方式可以設(shè)置一個前驅(qū)結(jié)點，利用循環(huán)找到第i個位置，再進(jìn)行插入。

如圖，在DATA1和DATA2數(shù)據(jù)結(jié)點之中插入一個NEW_DATA數(shù)據(jù)結(jié)點：

從原來的鏈表狀態(tài)

到新的鏈表狀態(tài)：

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

//單鏈表的插入，在鏈表的第i個位置插入x的元素
??
LinkedList?LinkedListInsert(LinkedList?L,int?i,int?x)?{
????Node?*pre;??????????????????????//pre為前驅(qū)結(jié)點
????pre?=?L;
????int?tempi?=?0;
????for?(tempi?=?1;?tempi?????????pre?=?pre->next;?????????????????//查找第i個位置的前驅(qū)結(jié)點
????}
????Node?*p;????????????????????????????????//插入的結(jié)點為p
????p?=?(Node?*)malloc(sizeof(Node));
????p->data?=?x;
????p->next?=?pre->next;
????pre->next?=?p;
??
????return?L;
}

刪除操作

刪除元素要建立一個前驅(qū)結(jié)點和一個當(dāng)前結(jié)點，當(dāng)找到了我們需要刪除的數(shù)據(jù)時，直接使用前驅(qū)結(jié)點跳過要刪除的結(jié)點指向要刪除結(jié)點的后一個結(jié)點，再將原有的結(jié)點通過free函數(shù)釋放掉。如圖所示：

代碼如下：

//單鏈表的刪除，在鏈表中刪除值為x的元素
??
LinkedList?LinkedListDelete(LinkedList?L,int?x)?{
??? Node *p,*pre;???????????????????//pre為前驅(qū)結(jié)點，p為查找的結(jié)點。
????p?=?L->next;
?????
????while(p->data?!=?x)?{??????????????//查找值為x的元素
????????pre?=?p;
????????p?=?p->next;
????}
??? pre->next = p->next;??????????//刪除操作，將其前驅(qū)next指向其后繼。
????free(p);
?????
????return?L;
}

雙向鏈表

雙向鏈表的簡介以及概念

單鏈表是指結(jié)點中只有一個指向其后繼的指針，具有單向性，但是有時需要搜索大量數(shù)據(jù)的時候，就需要多次進(jìn)行從頭開始的遍歷，這樣的搜索就不是很高效了。

在單鏈表的基礎(chǔ)上，對于每一個結(jié)點設(shè)計一個前驅(qū)結(jié)點，前驅(qū)結(jié)點與前一個結(jié)點相互連接，構(gòu)成一個鏈表，就產(chǎn)生了雙向鏈表的概念了。

雙向鏈表可以簡稱為雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。

一個完整的雙向鏈表應(yīng)該是頭結(jié)點的pre指針指為空，尾結(jié)點的next指針指向空，其余結(jié)點前后相鏈。

雙向鏈表的結(jié)點設(shè)計

對于每一個結(jié)點而言，有：

其中，DATA表示數(shù)據(jù)，其可以是簡單的類型也可以是復(fù)雜的結(jié)構(gòu)體；

pre代表的是前驅(qū)指針，它總是指向當(dāng)前結(jié)點的前一個結(jié)點，如果當(dāng)前結(jié)點是頭結(jié)點，則pre指針為空；

next代表的是后繼指針，它總是指向當(dāng)前結(jié)點的下一個結(jié)點，如果當(dāng)前結(jié)點是尾結(jié)點，則next指針為空

其代碼設(shè)計如下：

typedef?struct?line{
????int?data;???????????//data
????struct?line?*pre;???//pre?node
????struct?line?*next;??//next?node
}line,*a;
//分別表示該結(jié)點的前驅(qū)(pre)，后繼(next)，以及當(dāng)前數(shù)據(jù)(data)

3. 雙鏈表的創(chuàng)建

創(chuàng)建雙向鏈表需要先創(chuàng)建頭結(jié)點，然后逐步的進(jìn)行添加雙向鏈表的頭結(jié)點是有數(shù)據(jù)元素的，也就是頭結(jié)點的data域中是存有數(shù)據(jù)的，這與一般的單鏈表是不同的。

對于逐步添加數(shù)據(jù)，先開辟一段新的內(nèi)存空間作為新的結(jié)點，為這個結(jié)點進(jìn)行的data進(jìn)行賦值，然后將已成鏈表的上一個結(jié)點的next指針指向自身，自身的pre指針指向上一個結(jié)點。

其代碼可以設(shè)計為：

//創(chuàng)建雙鏈表
line*?initLine(line?*?head){
????int?number,pos=1,input_data;
????//三個變量分別代表結(jié)點數(shù)量，當(dāng)前位置，輸入的數(shù)據(jù)
????printf("請輸入創(chuàng)建結(jié)點的大小\n");
????scanf("%d",&number);
????if(number<1){return?NULL;}?//輸入非法直接結(jié)束
????//////頭結(jié)點創(chuàng)建///////
????head=(line*)malloc(sizeof(line));
????head->pre=NULL;
????head->next=NULL;
????printf("輸入第%d個數(shù)據(jù)\n",pos++);
????scanf("%d",&input_data);
????head->data=input_data;
??
????line?*?list=head;
????while?(pos<=number)?{
????????line?*?body=(line*)malloc(sizeof(line));
????????body->pre=NULL;
????????body->next=NULL;
????????printf("輸入第%d個數(shù)據(jù)\n",pos++);
????????scanf("%d",&input_data);
????????body->data=input_data;
????????
????????list->next=body;
????????body->pre=list;
????????list=list->next;
????}
????return?head;
}

雙向鏈表創(chuàng)建的過程可以分為：創(chuàng)建頭結(jié)點->創(chuàng)建一個新的結(jié)點->將頭結(jié)點和新結(jié)點相互鏈接->再度創(chuàng)建新結(jié)點，這樣會有助于理解。

雙向鏈表的插入操作

如圖所示：

對于每一次的雙向鏈表的插入操作，首先需要創(chuàng)建一個獨立的結(jié)點，并通過malloc操作開辟相應(yīng)的空間；

其次我們選中這個新創(chuàng)建的獨立節(jié)點，將其的pre指針指向所需插入位置的前一個結(jié)點；

同時，其所需插入的前一個結(jié)點的next指針修改指向為該新的結(jié)點，該新的結(jié)點的next指針將會指向一個原本的下一個結(jié)點，而修改下一個結(jié)點的pre指針為指向新結(jié)點自身，這樣的一個操作我們稱之為雙向鏈表的插入操作。

其代碼可以表示為：

//插入數(shù)據(jù)
line?*?insertLine(line?*?head,int?data,int?add){
????//三個參數(shù)分別為：進(jìn)行此操作的雙鏈表，插入的數(shù)據(jù)，插入的位置
????//新建數(shù)據(jù)域為data的結(jié)點
????line?*?temp=(line*)malloc(sizeof(line));
????temp->data=data;
????temp->pre=NULL;
????temp->next=NULL;
????//插入到鏈表頭，要特殊考慮
????if?(add==1)?{
????????temp->next=head;
????????head->pre=temp;
????????head=temp;
????}else{
????????line?*?body=head;
????????//找到要插入位置的前一個結(jié)點
????????for?(int?i=1;?i????????????body=body->next;
????????}
????????//判斷條件為真，說明插入位置為鏈表尾
????????if?(body->next==NULL)?{
????????????body->next=temp;
????????????temp->pre=body;
????????}else{
????????????body->next->pre=temp;
????????????temp->next=body->next;
????????????body->next=temp;
????????????temp->pre=body;
????????}
????}
????return?head;
}

雙向鏈表的刪除操作

如圖：

刪除操作的過程是：選擇需要刪除的結(jié)點->選中這個結(jié)點的前一個結(jié)點->將前一個結(jié)點的next指針指向自己的下一個結(jié)點->選中該節(jié)點的下一個結(jié)點->將下一個結(jié)點的pre指針修改指向為自己的上一個結(jié)點。

在進(jìn)行遍歷的時候直接將這一個結(jié)點給跳過了，之后，我們釋放刪除結(jié)點，歸還空間給內(nèi)存，這樣的操作我們稱之為雙鏈表的刪除操作。

其代碼可以表示為：

//刪除元素
line?*?deleteLine(line?*?head,int?data){
????//輸入的參數(shù)分別為進(jìn)行此操作的雙鏈表，需要刪除的數(shù)據(jù)
????line?*?list=head;
????//遍歷鏈表
????while?(list)?{
????????//判斷是否與此元素相等
????????//刪除該點方法為將該結(jié)點前一結(jié)點的next指向該節(jié)點后一結(jié)點
????????//同時將該結(jié)點的后一結(jié)點的pre指向該節(jié)點的前一結(jié)點
????????if?(list->data==data)?{
????????????list->pre->next=list->next;
????????????list->next->pre=list->pre;
????????????free(list);
????????????printf("--刪除成功--\n");
????????????return?head;
????????}
????????list=list->next;
????}
????printf("Error:沒有找到該元素，沒有產(chǎn)生刪除\n");
????return?head;
}

雙向鏈表的遍歷

雙向鏈表的遍歷利用next指針逐步向后進(jìn)行索引即可。

注意，在判斷這里，我們既可以用while(list)的操作直接判斷是否鏈表為空，也可以使用while(list->next)的操作判斷該鏈表是否為空，其下一節(jié)點為空和本結(jié)點是否為空的判斷條件是一樣的效果。

其簡單的代碼可以表示為：

//遍歷雙鏈表,同時打印元素數(shù)據(jù)
void?printLine(line?*head){
????line?*list?=?head;
????int?pos=1;
????while(list){
????????printf("第%d個數(shù)據(jù)是:%d\n",pos++,list->data);
????????list=list->next;
????}
}

循環(huán)鏈表

循環(huán)鏈表概念

對于單鏈表以及雙向鏈表，就像一個小巷，無論怎么走最終都能從一端走到另一端，顧名思義，循環(huán)鏈表則像一個有傳送門的小巷，當(dāng)你以為你走到結(jié)尾的時候，其實這就是開頭。

循環(huán)鏈表和非循環(huán)鏈表其實創(chuàng)建的過程唯一不同的是，非循環(huán)鏈表的尾結(jié)點指向空（NULL），而循環(huán)鏈表的尾指針指向的是鏈表的開頭。

通過將單鏈表的尾結(jié)點指向頭結(jié)點的鏈表稱之為循環(huán)單鏈表（Circular linkedlist）

一個完整的循環(huán)單鏈表如圖：

循環(huán)鏈表結(jié)點設(shè)計（以單循環(huán)鏈表為例）

對于循環(huán)單鏈表的結(jié)點，可以完全參照于單鏈表的結(jié)點設(shè)計，如圖：

data表示數(shù)據(jù)；

next表示指針，它總是指向自身的下一個結(jié)點，對于只有一個結(jié)點的存在，這個next指針則永遠(yuǎn)指向自身，對于一個鏈表的尾部結(jié)點，next永遠(yuǎn)指向開頭。

其代碼如下：

typedef?struct?list{
????int?data;
????struct?list?*next;
}list;
//data為存儲的數(shù)據(jù)，next指針為指向下一個結(jié)點

循環(huán)單鏈表初始化

先創(chuàng)建一個頭結(jié)點并且給其開辟內(nèi)存空間，在開辟內(nèi)存空間成功之后，將頭結(jié)點的next指向head自身，創(chuàng)建一個init函數(shù)來完成；

為了重復(fù)創(chuàng)建和插入，我們可以在init函數(shù)重新創(chuàng)建的結(jié)點next指向空，而在主函數(shù)調(diào)用創(chuàng)建之后，將head頭結(jié)點的next指針指向自身。

這樣的操作方式可以方便過后的創(chuàng)建單鏈表，直接利用多次調(diào)用的插入函數(shù)即可完成整體創(chuàng)建。

其代碼如下：

//初始結(jié)點
list?*initlist(){
????list?*head=(list*)malloc(sizeof(list));
????if(head==NULL){
????????printf("創(chuàng)建失敗，退出程序");
????????exit(0);
????}else{
????????head->next=NULL;
????????return?head;
????}
}

在主函數(shù)重調(diào)用可以是這樣

????//////////初始化頭結(jié)點//////////////
????list?*head=initlist();
????head->next=head;

循環(huán)鏈表的創(chuàng)建操作

如圖所示：

通過逐步的插入操作，創(chuàng)建一個新的節(jié)點，將原有鏈表尾結(jié)點的next指針修改指向到新的結(jié)點，新的結(jié)點的next指針再重新指向頭部結(jié)點，然后逐步進(jìn)行這樣的插入操作，最終完成整個單項循環(huán)鏈表的創(chuàng)建。

其代碼如下：

//創(chuàng)建——插入數(shù)據(jù)
int?insert_list(list?*head){
????int?data;???//插入的數(shù)據(jù)類型
????printf("請輸入要插入的元素：");
????scanf("%d",&data);
??
????list?*node=initlist();
????node->data=data;
????//初始化一個新的結(jié)點，準(zhǔn)備進(jìn)行鏈接
??
????if(head!=NULL){
????????list?*p=head;
????????//找到最后一個數(shù)據(jù)
????????while(p->next!=head){
????????????p=p->next;
????????}
????????p->next=node;
????????node->next=head;
????????return?1;
????}else{
????????printf("頭結(jié)點已無元素\n");
????????return?0;
????}
??
}

循環(huán)單鏈表的插入操作

如圖，對于插入數(shù)據(jù)的操作，可以創(chuàng)建一個獨立的結(jié)點，通過將需要插入的結(jié)點的上一個結(jié)點的next指針指向該節(jié)點，再由需要插入的結(jié)點的next指針指向下一個結(jié)點的方式完成插入操作。

其代碼如下：

//插入元素
list?*insert_list(list?*head,int?pos,int?data){
????//三個參數(shù)分別是鏈表，位置，參數(shù)
????list?*node=initlist();??//新建結(jié)點
????list?*p=head;???????//p表示新的鏈表
????list?*t;
????t=p;
????node->data=data;
????if(head!=NULL){
????????for(int?i=1;i????????????t=t->next;??//走到需要插入的位置處
????????}
????????node->next=t->next;
????????t->next=node;
????????return?p;
????}
????return?p;
}

循環(huán)單鏈表的刪除操作

如下圖所示，循環(huán)單鏈表的刪除操作是先找到需要刪除的結(jié)點，將其前一個結(jié)點的next指針直接指向刪除結(jié)點的下一個結(jié)點即可。

需要注意的是尾結(jié)點，因為刪除尾節(jié)點后，尾節(jié)點前一個結(jié)點就成了新的尾節(jié)點，這個新的尾節(jié)點需要指向的是頭結(jié)點而不是空。

其代碼如下：

//刪除元素
int?delete_list(list?*head)?{
????if(head?==?NULL)?{
????????printf("鏈表為空！\n");
????????return?0;
????}
????//建立臨時結(jié)點存儲頭結(jié)點信息（目的為了找到退出點）
????//如果不這么建立的化需要使用一個數(shù)據(jù)進(jìn)行計數(shù)標(biāo)記，計數(shù)達(dá)到鏈表長度時自動退出
????//循環(huán)鏈表當(dāng)找到最后一個元素的時候會自動指向頭元素，這是我們不想讓他發(fā)生的
????list?*temp?=?head;??????????
????list?*ptr?=?head->next;
??
????int?del;
????printf("請輸入你要刪除的元素：");
????scanf("%d",&del);
??
????while(ptr?!=?head)?{
????????if(ptr->data?==?del)?{
????????????if(ptr->next?==?head)?{?
????????????????temp->next?=?head;
????????????????free(ptr);
????????????????return?1;
????????????}
????????????temp->next?=?ptr->next;????//核心刪除操作代碼
????????????free(ptr);
????????????//printf("元素刪除成功！\n");
????????????return?1;
????????}
????????temp?=?temp->next;
????????ptr?=?ptr->next;
????}
????printf("沒有找到要刪除的元素\n");
????return?0;
}

循環(huán)單鏈表的遍歷

與普通的單鏈表和雙向鏈表的遍歷不同，循環(huán)鏈表需要進(jìn)行結(jié)點的特殊判斷。

先找到尾節(jié)點的位置，由于尾節(jié)點的next指針是指向頭結(jié)點的，所以不能使用鏈表本身是否為空（NULL）的方法進(jìn)行簡單的循環(huán)判斷，我們需要通過判斷結(jié)點的next指針是否等于頭結(jié)點的方式進(jìn)行是否完成循環(huán)的判斷。

此外還有一種計數(shù)的方法，即建立一個計數(shù)器count=0，每一次next指針指向下一個結(jié)點時計數(shù)器+1，當(dāng)count數(shù)字與鏈表的節(jié)點數(shù)相同的時候即完成循環(huán)；

但是這樣做會有一個問題，就是獲取到鏈表的節(jié)點數(shù)同時，也需要完成一次遍歷才可以達(dá)成目標(biāo)。

其代碼如下：

//遍歷元素
int?display(list?*head)?{
????if(head?!=?NULL)?{
????????list?*p??=?head;
????????//遍歷頭節(jié)點到，最后一個數(shù)據(jù)
????????while(p->next?!=?head?)?{
????????????printf("%d???",p->next->data);
????????????p?=?p->next;
????????}
????????printf("\n");???//換行
????????//把最后一個節(jié)點賦新的節(jié)點過去
????????return?1;
????}?else?{
????????printf("頭結(jié)點為空!\n");
????????return?0;
????}
}

進(jìn)階概念——雙向循環(huán)鏈表

循環(huán)單鏈表也有一個孿生兄弟——雙向循環(huán)鏈表，其設(shè)計思路與單鏈表和雙向鏈表的設(shè)計思路一樣，就是在原有的雙向鏈表的基礎(chǔ)上，將尾部結(jié)點和頭部結(jié)點進(jìn)行互相連接。交給大家了。

關(guān)于鏈表的總結(jié)

在順序表中做插入刪除操作時，平均移動大約表中一半的元素，因此對n較大的順序表效率低。并且需要預(yù)先分配足夠大的存儲空間，而鏈表恰恰是其中運用的精華。

基于存儲，運算，環(huán)境這幾方面考慮，可以讓我們更好的在項目中使用鏈表。

今天鏈表基礎(chǔ)就講到這里，下一期，我們再見！