鏈表之循環(huán)鏈表（C語言版）

進(jìn)入循環(huán)鏈表之前我先解決一下上篇博文最后提到到的一種更方便的管理鏈表的結(jié)構(gòu):

typedef struct node  //節(jié)點(diǎn)類型

{

type value;

struct node *next;

}Node;

typedef struct list

{

Node *phead;

Node *ptail;

int length;

}List;

    首先來說這種結(jié)構(gòu)只是為了方便管理，對(duì)于鏈表之前提的帶頭節(jié)點(diǎn)與不帶頭結(jié)點(diǎn)所提的區(qū)別依然是有效的，ok我們繼續(xù)上圖，先認(rèn)識(shí)一下這種結(jié)構(gòu)：

   分別通過phead、ptail指向鏈表的頭和尾，length記錄鏈表的長度，這樣就可以方便的記錄鏈表的信息，我們之前說過帶頭結(jié)點(diǎn)的鏈表方便操作，那么兩者加起來就更方便。接下來進(jìn)入今天的主題，循環(huán)鏈表，為什么會(huì)出現(xiàn)循環(huán)鏈表，我個(gè)人認(rèn)為，就是為了彌補(bǔ)單鏈表的不足，在單鏈表中，當(dāng)我們已經(jīng)遍歷過某個(gè)元素，當(dāng)我們希望再次查找時(shí)，就需要讓臨時(shí)指針重新指向頭首元結(jié)點(diǎn)，重新遍歷。這樣就很麻煩，有了單循環(huán)鏈表，由于尾結(jié)點(diǎn)是指向頭，就可以直接找到頭，不需用額外語句，我想這就是單循環(huán)鏈表出來的緣故。找到頭的問題解決了，之前單鏈表按位置插入刪除的時(shí)候，當(dāng)我們?cè)谛枰迦?、刪除某個(gè)元素的時(shí)候不僅要找到特定元素，還需要記住這個(gè)元素之前的元素，才能找到特定元素的地址。ok，為了解決這個(gè)問題，我們聰明的計(jì)算機(jī)前輩，又發(fā)明了雙循環(huán)鏈表，解決了這個(gè)問題。接下來，依然為了便于理解，給出我在學(xué)習(xí)過程中的一些理解圖：帶頭結(jié)點(diǎn)、不帶頭結(jié)點(diǎn)的鏈表，這里都給出。不過，這里不在采用之前給出的管理鏈表的方式管理鏈表，通過我剛給出的方式處理，請(qǐng)看下圖：

    ok看完了結(jié)構(gòu)圖，我們來看循環(huán)鏈表主要的基本操作，同樣的這里把帶頭結(jié)點(diǎn)的操作，不帶頭結(jié)點(diǎn)的的結(jié)構(gòu)的操作都按照我個(gè)人的理解都給出。這里先給出單循環(huán)鏈表的代碼以及示意圖

首先我們先給出結(jié)構(gòu)定義等部分的代碼：

typedef int Status;

#define OK        1

#define ERROR     0

#define TRUE      1

#define FALSE     0

typedef int ElemType;

//定義單鏈表的結(jié)點(diǎn)

typedef struct node

{

ElemType data;

struct node *next;

}Node;

typedef struct node *LinkNode;

//定義管理鏈表的結(jié)構(gòu)

typedef struct list 

{

LinkNode Phead;

LinkNode Ptail;

int length ;

}List;

//構(gòu)造新結(jié)點(diǎn),寫后面的插入函數(shù)后會(huì)重復(fù)使用構(gòu)造節(jié)點(diǎn)的代碼，因此將重復(fù)代碼封裝在函數(shù)中減少重復(fù)代碼量

Node * BuyNode(ElemType x)

{

LinkNode s = (Node *)malloc(sizeof(Node));

if(NULL == s)

{

return NULL;

}

s->data = x;

s->next = NULL;

return s;

}

//同樣構(gòu)造完結(jié)點(diǎn)后多次使用到判斷是否為空，因此也將代碼封裝成函數(shù)精簡代碼。

//判斷是空返回FALSE;不是空返回TRUE;

Status IsEmpty(LinkNode s )

{

if(NULL == s)

{

printf("Out of memory\n");

return FALSE;

}

return TRUE;

}

初始化

//初始化不帶頭結(jié)點(diǎn)的循環(huán)單鏈表,初始化成功返回TRUE;失敗返回FALSE;

Status Init_No_Head(List * head)

{

head->length = 0;

head->Phead = NULL;

head->Ptail = NULL;

return TRUE;

}

//初始化帶頭結(jié)點(diǎn)是循環(huán)單鏈表,初始化成功返回TRUE;失敗返回FALSE;

Status Init_Yes_Head(List *head)

{

LinkNode s = BuyNode(0);

if(NULL == s)

{

printf("內(nèi)存不足，初始化失敗\n");

return ERROR;

}

head->length = 0;

head->Phead = head->Ptail = s;

s->next = head->Phead;

return TRUE;

}

單循環(huán)鏈表的頭插

同樣也為了便于理解，我這里給出頭插操作的示意圖：

    帶頭結(jié)點(diǎn)的頭插，由于帶頭結(jié)點(diǎn)，所以頭指針phead始終指向頭結(jié)點(diǎn)，但是有一種特殊情況，為了維護(hù)其結(jié)構(gòu)的完整性，那么對(duì)于空表的頭插就是一種特殊情況，就要單獨(dú)處理，需要把尾指針的指向修改。

    由于不帶頭結(jié)點(diǎn)，所以每次頭插就需要修改頭指針的指向。所以不帶頭結(jié)點(diǎn)的頭插就會(huì)出現(xiàn)兩種情況，1、表中已經(jīng)有多個(gè)元素，頭插時(shí)需要把phead始終指向第一個(gè)結(jié)點(diǎn)，這里沒有頭結(jié)點(diǎn)，因此就需要每次需改phead，2、空表的時(shí)候，就需要修改頭指針phead和尾指針ptail的指向，并且要把第一個(gè)結(jié)點(diǎn)next指向自己，構(gòu)成循環(huán)。

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

//不帶頭結(jié)點(diǎn)的頭插，插入成功返回TRUE,失敗返回FASLE

Status Insert_No_Head(List *head,ElemType x)

{

LinkNode s = BuyNode(x);                  //構(gòu)造新結(jié)點(diǎn)

if(FALSE == IsEmpty(s))

{

return FALSE;

}

if(0 == head->length)                  //處理空鏈表的情況

{

head->Ptail = head->Phead = s;

}

s->next = head->Phead;           

head->Phead = s;

head->Ptail->next = s;

head->length++;

return TRUE;

}

//帶頭結(jié)點(diǎn)的循環(huán)單鏈表的頭插,插入成功返回TRUE,失敗返回FASLE

//帶頭結(jié)點(diǎn)的頭插需要注意一點(diǎn)，那就是當(dāng)鏈表為空時(shí)要維護(hù)結(jié)構(gòu)的完整性，那么就需要修改ptail的指向

Status Isert_Yse_Head(List *head ,ElemType x)

{

LinkNode s = BuyNode(x);

if(FALSE == IsEmpty(s))

{

return FALSE;

}

s->next = head->Phead->next;

head->Phead->next= s; 

if(0 == head->length)            //處理空鏈表的情況

{

head->Ptail = s;

s->next = head->Phead;

}

head->length++;

return TRUE;

}

單循環(huán)鏈表的尾插

同樣我們來看尾插的示意圖：

    帶頭結(jié)點(diǎn)的尾插不論是空表還是有元素的表處理的情況是一樣，每次都要修改ptail的指向

    對(duì)于不帶頭結(jié)點(diǎn)的鏈表，需要注意空表時(shí)的情況，此時(shí)鏈表為空phead和ptail都指向空，所以就需要修改phead的指向。

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

//不帶頭結(jié)點(diǎn)的循環(huán)單鏈表的尾插，插入成功返回RUE，失敗返回FALSE

Status Isert_No_Tail(list *head,ElemType x)

{

LinkNode s = BuyNode(x);

if(FALSE == IsEmpty(s))

{

return FALSE;

}

if(0 == head->length)           //處理空鏈表的情況

{

head->Phead = head->Ptail = s;

}

s->next = head->Phead;

head->Ptail->next = s;

head->Ptail = s;

//帶頭結(jié)點(diǎn)的循環(huán)單鏈表尾插，插入成功返回RUE，失敗返回FALSE

Status Insert_Yes_Tail(list *head, ElemType x)

{

LinkNode s = BuyNode(x);

if(FALSE == IsEmpty(s))

{

return FALSE;

}

s->next = head->Phead;

head->Ptail->next = s;

head->Ptail = s;

head->length++;

return TRUE;

}

單循環(huán)鏈表的頭刪

我們繼續(xù)來循環(huán)單鏈表的頭刪的示意圖：

    對(duì)于不帶頭結(jié)點(diǎn)的循環(huán)單鏈表，表中有多個(gè)元素的時(shí)候，按照步驟修改指向，特別注意一定要釋放刪除的結(jié)點(diǎn)內(nèi)存，不讓會(huì)造成內(nèi)存泄露，并且為了防止產(chǎn)生野指針，把指向刪除結(jié)點(diǎn)的指針指向NULL；頭刪一個(gè)結(jié)點(diǎn)的時(shí)候是一個(gè)種特殊情況，需要特別關(guān)注，需要把phead和ptail 的指向全部修改。

    對(duì)于帶頭結(jié)點(diǎn)的循環(huán)單鏈表，表中元素較多時(shí)，依然是按照?qǐng)D中標(biāo)的步驟操作，這沒得說，當(dāng)然也需要注意釋放刪除的結(jié)點(diǎn)的空間并把指針指向NULL;帶頭結(jié)點(diǎn)的循環(huán)單鏈表一個(gè)結(jié)點(diǎn)的時(shí)候，也是一種特殊情況。需要把ptail的指向修改，當(dāng)然釋放內(nèi)存空間，并把指針指向NULL，依然沒的說。

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

//不帶頭結(jié)點(diǎn)的頭刪，刪除成功返回TRUE,失敗失敗返回FALSE;

Status Delite_No_Head(list *head,ElemType *x)

{

LinkNode p = head->Phead;

if(NULL == p)

{

printf("鏈表已空，不能刪除了\n");

return FALSE;

}

*x = p->data;

head->Phead = p->next;

head->Ptail->next = head->Phead;

if(1  == head->length)                    //處理只有一個(gè)結(jié)點(diǎn)的情況

{

head->Phead = NULL;

head->Ptail = NULL;

}

free(p);

p = NULL;

head->length--;

return TRUE;

}

//帶頭結(jié)點(diǎn)的頭刪，刪除成功返回TRUE,失敗失敗返回FALSE;

Status Delite_Yes_Head(list *head,ElemType *x)

{

LinkNode p = head->Phead->next;

if(head->Phead == p)

{

printf("鏈表已空，已經(jīng)無法刪除\n");

return FALSE;

}

head->Phead->next = p->next;

*x = p->data;

if(1 == head->length)           //處理只有一個(gè)結(jié)點(diǎn)的情況

{

head->Ptail = head->Phead;

}

free(p);

p = NULL;

head->length--;

return TRUE;

}

單循環(huán)鏈表的尾刪

最后我們來看循環(huán)單鏈表尾刪的示意圖：

    不管是帶頭結(jié)點(diǎn)還是不帶頭結(jié)點(diǎn)的循環(huán)單鏈表的尾刪，都需要定位到最后一個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，只有前一個(gè)結(jié)點(diǎn)才知道后一個(gè)節(jié)點(diǎn)的內(nèi)存，并且，尾刪的時(shí)候需要修改最后一個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的指針指向。最后還是要強(qiáng)調(diào)一下釋放內(nèi)存空間并且把指針指向指向NULL。需要注意：不帶頭結(jié)點(diǎn)的尾刪，當(dāng)是一個(gè)結(jié)點(diǎn)的時(shí)候需要單獨(dú)處理。

//不帶頭結(jié)點(diǎn)的尾刪，刪除成功返回TRUE,失敗失敗返回FALSE;

Status  Delite_No_Tail(list *head,ElemType *x)

{

LinkNode s = head->Phead;

if(NULL == s)

{

printf("鏈表已空，已經(jīng)無元素可以刪除\n");

return FALSE;

}

if(1 == head->length)                  //處理只有一個(gè)結(jié)點(diǎn)的情況

{

head->Phead = head->Ptail = NULL;

*x = s->data;

head->length--;

return TRUE;

}

while(head->Ptail != s->next)         //尋找最后一個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)

{

s = s->next;

}

*x = s->next->data;

head->Ptail = s;

free(s->next);

s->next = head->Phead;

head->length--;

return TRUE;

}

//帶頭結(jié)點(diǎn)尾刪，刪除成功返回TRUE,失敗失敗返回FALSE;

Status Delite_Yes_Tail(list *head,ElemType *x)

{

LinkNode s = head->Phead->next;

if(0 == head->length)

{

printf("鏈表已空，已經(jīng)無元素可以刪除\n");

return FALSE;

}

while(head->Ptail != s->next)  //尋找最后一個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)

{

s = s->next;

}

head->Ptail = s;

*x = s->next->data;

free(s->next);

s->next = head->Phead;

head->length--;

return TRUE;

}

以上就是按照我個(gè)人理解總結(jié)的單循環(huán)鏈表的基本操作，已經(jīng)經(jīng)過測(cè)試。上邊盡可能詳細(xì)的給出了操作的主要思想以及示意圖，代碼還有許多可以優(yōu)化的地方。希望讀者提出意見和建議。雙循環(huán)鏈表的基本操作不在本篇總結(jié)了，在后續(xù)的博文中會(huì)對(duì)其按照我個(gè)人的理解總結(jié)。