建站
咨詢
售后
建站咨詢
新聞中心
接著上一篇博文http://12172969.blog.51cto.com/12162969/1918256，把循環(huán)鏈表里的雙循環(huán)鏈表的基本操縱按照我個(gè)人的理解進(jìn)行總結(jié)一下。
寧城網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司,寧城網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為寧城上千提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)營(yíng)銷網(wǎng)站建設(shè)要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的寧城做網(wǎng)站的公司定做！
依然沿襲過(guò)去的風(fēng)格，進(jìn)入雙循環(huán)鏈表之前，先提另一種結(jié)構(gòu)，雙向鏈表，先有了雙向鏈表再有了雙循環(huán)鏈表。這兩種結(jié)構(gòu)和單鏈表一樣都有帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)之分。我們先來(lái)看一下這幾種結(jié)構(gòu)的結(jié)構(gòu)圖:
雙鏈表
雙循環(huán)鏈表
既然單向鏈表有普通的鏈表也就是不循環(huán)的鏈表、那么雙向鏈表也一樣，也有普通的雙向鏈表和雙向循環(huán)鏈表；也有帶頭結(jié)點(diǎn)，不帶頭結(jié)點(diǎn)的結(jié)構(gòu)，這里依然是兩種結(jié)構(gòu)都給出算法，但是普通的循環(huán)鏈表不寫，這里只寫循環(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;
struct node *prev;
}Node;
typedef struct node *SeqNode;
//定義管理鏈表的結(jié)構(gòu)
typedef struct list
{
struct node *phead;
struct node *ptail;
size_t length;
}List;
//判斷結(jié)點(diǎn)是否為空，空返回FALSE,不空返回TRUE;
Status IsEmpty(SeqNode p)
{
if(NULL ==p)
{
return FALSE;
}
return TRUE;
}
//構(gòu)造新結(jié)點(diǎn),寫后面的插入函數(shù)后會(huì)重復(fù)使用構(gòu)造節(jié)點(diǎn)的代碼，因此將重復(fù)代碼封裝在函數(shù)中減少重復(fù)代碼量
Node *BuyNode(ElemType x)
{
SeqNode s = (Node*)malloc(sizeof(Node));
if(FALSE == IsEmpty(s))
{
printf("out of mommery\n");
return FALSE;
}
s->data = x;
s->next = NULL;
s->prev = NULL;
return s;
}
//查找函數(shù)：按照值插入，都需要找到需要插入的位置，為了優(yōu)化代碼，因此將這一部分封裝起來(lái)。
//查找要插入的結(jié)點(diǎn)，因?yàn)殡p循環(huán)鏈表可以通過(guò)當(dāng)前節(jié)點(diǎn)找到自己的地址，因此不需用額外的變量保存當(dāng)前的地址,
//查找成功返回當(dāng)前結(jié)點(diǎn)的地址，查找失敗返回最后一個(gè)空間的地址
Node *Find(List head,SeqNode s,ElemType x)
{
while(head.length--)
{
if(s->data < x)
{
s = s->next;
continue;
}
return s;
}
return s;
}
//查找函數(shù)：按照值刪除，都需要找到需要插入的位置，為了優(yōu)化代碼，因此將這一部分封裝起來(lái)。
//查找要插入的結(jié)點(diǎn)，因?yàn)殡p循環(huán)鏈表可以通過(guò)當(dāng)前節(jié)點(diǎn)找到自己的地址，因此不需用額外的變量保存當(dāng)前的地址,
//查找成功返回當(dāng)前結(jié)點(diǎn)的地址，查找失敗返回NULL
Node *_Find(List head,SeqNode s,ElemType x)
{
while(head.length--)
{
if(s->data == x)
{
return s;
}
s = s->next;
}
return NULL;
}
初始化
初始化的時(shí)候，就是要建立一個(gè)空表，上圖中已經(jīng)給出了空表的示意圖，那么 初始化就是建立這樣一個(gè)結(jié)構(gòu)。
//初始化帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，初始化成功返回TRUE,失敗FALSE.
Status Init_Yes_SeqNode(List *head)
{
SeqNode s = BuyNode(0);
if(FALSE == IsEmpty(s))
{
printf("初始化失敗\n");
return FALSE;
}
head->length = 0;
head->phead = s;
head->ptail = s;
s->next = s;
s->prev = s;
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 FALSE;
}
雙循環(huán)鏈表頭插
個(gè)人一直覺(jué)得只要結(jié)構(gòu)弄清了，寫代碼就好辦了。所以我繼續(xù)給出頭插的示意圖：
帶不帶頭結(jié)點(diǎn)的雙循環(huán)鏈表頭插只要按照?qǐng)D中標(biāo)號(hào)順序，執(zhí)行就可以頭插成功，兩者都有一個(gè)特殊情況，就是空表的時(shí)候，需要維護(hù)結(jié)構(gòu)的完整性，需要單獨(dú)處理。當(dāng)然我給出的順序只是其中一種，其他的順序同樣可以達(dá)到相同的作用。
具體代碼實(shí)現(xiàn)如下
//帶頭結(jié)點(diǎn)的的雙循環(huán)雙鏈表頭插，插入成功返回TRUE,失敗返回FALSE
Status Insert_Yes_Head(List *head,ElemType x)
{
SeqNode s = BuyNode(x);
//需要注意這里SeqNode 定義的變量是一個(gè)結(jié)點(diǎn)類型的指針，BuyNode(x)函數(shù)是我之前定義的函數(shù)，用來(lái)構(gòu)造結(jié)點(diǎn)的，后邊不在說(shuō)明
if(FALSE == IsEmpty(s))
{
printf("out of memory\n");
return FALSE;
}
s->next = head->phead->next;
s->prev = head->phead;
s->next->prev = s;
s->prev->next = s;
if(0 == head->length) //處理空表的情況
{
head->ptail = s;
}
head->length++;
return TRUE;
}
//不帶頭結(jié)點(diǎn)的循環(huán)雙鏈表頭插，插入成功返回TRUE,失敗返回FALSE
Status Insert_No_Head(List *head,ElemType x)
{
SeqNode s = BuyNode(x);
if(FALSE == IsEmpty(s))
{
printf("out of memory\n");
return FALSE;
}
if(0 == head->length)
{
s->next = s;
s->prev = s;
head->phead = s;
head->ptail = s;
}
s->next = head->phead;
s->prev = head->ptail;
s->next->prev = s;
s->prev->next = s;
head->phead = s;
head->length++;
return TRUE;
}
雙循環(huán)鏈表尾插
我們繼續(xù)看圖：
圖看明白了，只要按照步驟來(lái)寫帶就可以了。
具體的實(shí)現(xiàn)代碼如下：
//帶頭結(jié)點(diǎn)的雙循環(huán)鏈表的尾插，插入成功返回TRUE,失敗返回FALSE
Status Insert_Yes_Tail(List *head,ElemType x)
{
SeqNode s = BuyNode(x);
if(FALSE == IsEmpty(s))
{
printf("out of memory\n");
return FALSE;
}
s->next = head->phead;
s->prev = head->ptail;
s->prev->next = s;
s->next->prev = s;
head->ptail = s;
head->length++;
return TRUE;
}
//不帶頭結(jié)點(diǎn)的雙循環(huán)鏈表的尾插，插入成功返回TRUE,失敗返回FALSE
Status Insert_No_Tail(List *head,ElemType x)
{
SeqNode s = BuyNode(x);
if(FALSE == IsEmpty(s))
{
printf("out of memory\n ");
return FALSE;
}
if(0 == head->length) //處理空鏈表的情況
{
head->phead = s;
head->ptail = s;
s->next = s;
s->prev = s;
}
s->next = head->phead;
s->prev = head->ptail;
s->next->prev = s;
s->prev->next = s;
head->ptail = s;
head->length++;
return TRUE;
}
雙循環(huán)鏈表的按值插（這里是按照從小到大的順序）
雙循環(huán)鏈表按值插入（這里是從小到大的順序），無(wú)論是帶頭結(jié)點(diǎn)還是不帶頭結(jié)點(diǎn)，當(dāng)是空表的時(shí)候，直接插入鏈表，不需用查找插入位置。
其他情況調(diào)用Find函數(shù)查找要插入的位置，F(xiàn)ind函數(shù)的返回值是要插入的地址的后一個(gè)元素的地址。由于雙循環(huán)鏈表可以同過(guò)當(dāng)前元素找到前一個(gè)結(jié)點(diǎn)所以Find返回來(lái)的地址就可以完成插入操作。當(dāng)是空表的時(shí)候，與頭插或者尾插的空表示意圖一樣，讀者返回到前邊看，這里不給出示意圖，這里只給出有元素的按值插入示意圖：
不帶頭結(jié)點(diǎn)的按值插入，有一點(diǎn)需要注意，當(dāng)只有一個(gè)結(jié)點(diǎn)的時(shí)候再次插入第二個(gè)結(jié)點(diǎn)的時(shí)候需要修改phead和ptail的指向，由于只有一個(gè)結(jié)點(diǎn)，不管是第二個(gè)要插入的值比第一個(gè)大還是小，由于是循環(huán)鏈表，F(xiàn)ind函數(shù)返回的都是第一個(gè)結(jié)點(diǎn)，這樣就需要在插如函數(shù)中，進(jìn)行單獨(dú)處理。
由于帶頭結(jié)點(diǎn)，所以不會(huì)出現(xiàn)不帶頭結(jié)點(diǎn)那種需要單獨(dú)處理的特殊情況，但是帶頭節(jié)點(diǎn)與不帶頭結(jié)點(diǎn)都有共同的特殊情況，那就是空表時(shí)的情況。
具體代碼實(shí)現(xiàn)：
//帶頭結(jié)點(diǎn)的按值插入，插入成功返回TRUE,失敗返回FALSE。
Status Insert_Yse_Value(List *head,ElemType value)
{
SeqNode s = BuyNode(value);
SeqNode p = NULL;
if(FALSE == IsEmpty(s))
{
printf("out of memory\n");
return FALSE;
}
if(0 == head->length) //處理空表的情況
{
s->next = head->phead;
s->prev = head->phead;
head->phead->next = s;
head->ptail = s;
head->phead->prev = s;
head->length++;
return TRUE;
}
p = Find(*head,head->phead->next,value); //Find函數(shù)，之前定義的，返回要插入的位置的地址。
//這里我提一下這個(gè)判斷條件，給Find函數(shù)傳過(guò)去的地址，是首元結(jié)點(diǎn)的地址，所以當(dāng)Find()函數(shù)返回的地址為head->phead時(shí)，說(shuō)明該元素需要插入到表尾，所以就需要修改ptial的指向。
if(head->phead == p)
{
head->ptail = s;
}
s->next = p;
s->prev = p->prev;
s->prev->next = s;
s->next->prev = s;
head->length++;
return TRUE;
}
//不帶頭結(jié)點(diǎn)的按值插入，插入成功返回TRUE,失敗返回FALSE。
Status Insert_No_Value(List *head,ElemType value)
{
SeqNode s = BuyNode(value);
SeqNode p = NULL;
if(FALSE == IsEmpty(s))
{
printf("out of memory\n");
return FALSE;
}
if(0 == head->length) //處理空表的情況
{
head->phead = s;
head->ptail = s;
s->next = s;
s->prev = s;
head->length++;
return TRUE;
}
p = Find(*head,head->phead,value); //Find函數(shù)，之前定義的，返回要插入的位置的地址。
s->next = p;
s->prev = p->prev;
p->prev = s;
s->prev->next = s;
//重點(diǎn)說(shuō)一下這一部分，由于沒(méi)有頭結(jié)點(diǎn)，所以當(dāng)Find()函數(shù)head->phead時(shí)，有可能是往頭插，也有可能是往尾插，所以就需要進(jìn)行判斷，當(dāng)Find()函數(shù)的返回值等于頭指針時(shí)，如果將要插入的值大于首元結(jié)點(diǎn)的值，那么就是說(shuō)，要插入的值是往最后插，即就是需要把ptail修改指向新結(jié)點(diǎn)。否則修改phead。
if(head->phead == p)
{
if( s->data > head->ptail->data)
{
head->ptail = s;
}
else
{
head->phead = s;
}
}
head->length++;
return TRUE;
}
循環(huán)雙鏈表的頭刪
不論是帶頭結(jié)點(diǎn)的鏈表還是不帶頭結(jié)點(diǎn)當(dāng)鏈表為空時(shí)直接返回FALSE;對(duì)于帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)的雙循環(huán)鏈表，都需要注意一個(gè)結(jié)點(diǎn)的情況，對(duì)于帶頭結(jié)點(diǎn)的雙循環(huán)鏈表，由于phead始終是指向頭結(jié)點(diǎn)的，所以，不需用修改頭指針的指向，以及最后一個(gè)節(jié)點(diǎn)的next域除了當(dāng)刪除到最后一個(gè)結(jié)點(diǎn)時(shí)，其他的都不用修改phead、ptail、ptail->next、phead->prev。然而對(duì)于不帶頭結(jié)點(diǎn)就需要每次維護(hù)循環(huán)鏈表的完整性，修改這些值。我們繼續(xù)看圖：
具體代碼實(shí)現(xiàn)：
//帶頭結(jié)點(diǎn)的循環(huán)雙鏈表的頭刪，刪除失敗返回FALSE,刪除成功返回TRUE.
Status Delite_Yes_Head(List *head)
{
SeqNode p = head->phead->next;
if(head->phead == p)
{
printf("鏈表中已空，無(wú)元素可刪\n");
return FALSE;
}
head->phead->next = p->next;
p->next->prev = head->phead;
free(p);
p = NULL;
if(1 == head->length) //處理刪除時(shí)只有一個(gè)結(jié)點(diǎn)時(shí)的情況
{
head->ptail = head->phead;
}
head->length--;
return TRUE;
}
//不帶頭結(jié)點(diǎn)的頭刪，刪除失敗返回FALSE,刪除成功返回TRUE.
Status Delite_No_Head(List *head)
{
SeqNode p = head->phead;
if(NULL == p)
{
printf("鏈表已空，已經(jīng)無(wú)元素可以刪除\n");
return FALSE;
}
if(1 == head->length) //處理刪除時(shí)只有一個(gè)結(jié)點(diǎn)時(shí)的情況
{
head->phead = NULL;
head->ptail = NULL;
}
else //處理一般情況
{
head->phead = p->next;
p->next->prev = head->phead;
head->ptail->next = head->phead; //維護(hù)循環(huán)鏈表的完整性
head->phead->prev = head->ptail;
}
free(p);
p = NULL;
head->length--;
return TRUE;
}
循環(huán)雙鏈表的尾刪
由于尾刪每次都需要修改ptail的指向，并且修改頭結(jié)點(diǎn)的prev的指向，所以對(duì)于帶頭結(jié)點(diǎn)的雙循環(huán)鏈表，所有情況都是一樣的不需用單獨(dú)處理那種情況，然而對(duì)于不帶頭結(jié)點(diǎn)的雙循環(huán)鏈表，由于刪除最后一個(gè)結(jié)點(diǎn)后phead和ptail都會(huì)指向NULL，所以要對(duì)不帶頭結(jié)點(diǎn)的雙循環(huán)鏈表的一個(gè)結(jié)點(diǎn)的情況單獨(dú)處理。ok,能用圖解決的問(wèn)題覺(jué)絕不廢話，當(dāng)然這是玩笑
，好了我們來(lái)看圖:
具體代碼實(shí)現(xiàn)：
//帶頭結(jié)點(diǎn)的尾刪，刪除成功返回TRUE，失敗返回FALSE;
Status Delite_Yes_Tail(List *head)
{
SeqNode p = head->ptail;
if(head->phead == p)
{
printf("鏈表已空、已經(jīng)無(wú)元素可以刪除\n");
return FALSE;
}
p->prev->next = head->phead;
head->phead->prev = p->prev;
head->ptail = p->prev;
free(p);
p = NULL;
head->length--;
return TRUE;
}
//不帶頭結(jié)點(diǎn)的循環(huán)雙鏈表的尾刪
Status Delite_No_Tail(List *head)
{
SeqNode p = head->ptail;
if(NULL == p)
{
printf("鏈表已空、已經(jīng)無(wú)元素可以刪除\n");
return FALSE;
}
if(1 == head->length) //處理只有一個(gè)結(jié)點(diǎn)的情況
{
head->phead = NULL;
head->ptail = NULL;
}
else
{
p->prev->next = head->phead;
head->phead->prev = p->prev;
head->ptail = p->prev;
}
free(p); //釋放結(jié)點(diǎn)空間
p = NULL;
head->length--;
return TRUE;
}
循環(huán)雙鏈表的尾刪
為了便于操作，這里就要用到之前寫的另一個(gè)Find函數(shù)，注意這兩個(gè)Find是不一樣的這里Find函數(shù)名是_Find函數(shù)名前有個(gè)下劃線，這只是從名字上的差別，它的功能也不同_Find函數(shù)在鏈表中搜索一個(gè)特定值，如果搜索到返回當(dāng)前地址，沒(méi)有搜索到返回NULL。
然后對(duì)于帶頭結(jié)點(diǎn)的雙循環(huán)單鏈表，就有這么幾種情況，1、如果表為空，直接返回不用查找了。2、如果_Find返回NULL，說(shuō)明表中沒(méi)有此元素，所以也刪除失敗，3、再就是找到元素，返回它的地址，將其刪除掉釋放掉空間，這里需要注意，由于帶頭結(jié)點(diǎn)phead始終指向頭結(jié)點(diǎn)，絕不需要修改phead的指向，但是當(dāng)刪除ptail指向的結(jié)點(diǎn)時(shí)就需要修改指向。這個(gè)要單獨(dú)處理。
對(duì)于不帶頭結(jié)點(diǎn)的雙循環(huán)鏈表。1、同樣如果鏈表為空，不用查找直接返回，刪除失??；2、如果_Find返回NULL，說(shuō)明表中沒(méi)有此元素，所以也刪除失??；3、再就是找到元素，對(duì)于不帶頭結(jié)點(diǎn)的鏈表，又分為四種情況：a、如果phead == ptail 并且 _Find 返回的地址等于他們說(shuō)明鏈表只有一個(gè)結(jié)點(diǎn)，并且要把他刪除了；b、如果_Find 返回的地址 == ptail 就需要修改 ptail的指向以及附帶的指向；c、如果_Find 返回的地址 == phead 就需要修改phead的指向以及附帶的指向。d、再就是一般情況，注意這幾個(gè)條件判斷是有順序的，如果沒(méi)有順序就需要b和c再添加條件。接下來(lái)我們繼續(xù)不看圖了，直接上代碼，這篇都畫了那么多圖了，并且這里會(huì)出現(xiàn)的情況，也就是之前那么多刪除操作的綜合，ok，所以沒(méi)有圖咯，不上圖了呢，代碼呢我就會(huì)給出盡可能多的注釋。
//帶頭結(jié)點(diǎn)的按照值，刪除，這里先不考慮重復(fù)值，刪除成功返回TRUE，失敗返回FALSE;
Status Delite_Yes_Value(List *head,ElemType value)
{
SeqNode p = NULL;
if(0 == head->length) //表為空，不用查找，刪除失敗，直接返回FALSE
{
printf("鏈表已空,%d刪除失敗\n",value);
return FALSE;
}
p = _Find(*head,head->phead->next,value);
if(NULL == p) //查找完成，表中不存在特定值的情況，刪除失敗，返回FALSE
{
printf("%d刪除失敗，鏈表中沒(méi)有%d\n",value,value);
return FALSE;
}
if(head->ptail == p ) //刪除尾結(jié)點(diǎn)的情況，就需要修改ptail指向
{
head->ptail = head->ptail->prev;
}
p->prev->next = p->next;
p->next->prev = p->prev;
free(p);
p = NULL;
head->length--;
return TRUE;
}
//不帶頭結(jié)點(diǎn)的按照值刪除，這里不考慮重復(fù)值，只刪除第一個(gè)遇到的，刪除成功返回TRUE，失敗返回FALSE;
Status Delite_No_Value(List *head,ElemType value)
{
SeqNode p = head->phead;
if(FALSE == IsEmpty(p)) //表為空，不用查找，刪除失敗，直接返回
{
printf("鏈表已空，%d刪除失敗\n",value);
return FALSE;
}
p = _Find(*head,head->phead,value);
if(NULL == p) //查找完成，表中不存在特定值的情況，刪除失敗，返回FALSE
{
printf("%d刪除失敗，鏈表中沒(méi)有%d元素\n",value,value);
return FALSE;
}
//表中元素只有一個(gè)并且要?jiǎng)h除的元素就是這一個(gè)，就需要修改phead 和 ptail的指向
if(head->phead == head->ptail && p == head->phead)
{
head->phead = NULL;
head->ptail = NULL;
}
//刪除頭結(jié)點(diǎn)的情況，就需要修改phead指向，以及附帶的其他指向，使其保持循環(huán)結(jié)構(gòu)的完整性
else if(head->phead == p)
{
head->phead = head->phead->next;
head->ptail = head->phead;
}
//刪除尾結(jié)點(diǎn)的情況，就需要修改ptail指向，以及附帶的其他指向，使其保持循環(huán)結(jié)構(gòu)的完整性
else if(head->ptail == p)
{
head->ptail = head->ptail->prev;
head->phead->prev = head->phead;
}
//一般情況
p->prev->next = p->next;
p->next->prev = p->prev;
free(p);
p = NULL;
head->length--;
return TRUE;
}
循環(huán)雙鏈表的打印輸出
//打印輸出不帶頭結(jié)點(diǎn)的循環(huán)雙鏈表中所有元素。
void Show_No(List head)
{
SeqNode p = head.phead;
if(NULL == p)
{
printf("鏈表為空\(chéng)n");
return ;
}
if(1 == head.length)
{
printf("%d ",p->data);
printf("\n");
return ;
}
while(head.phead != p->next)
{
printf("%d ",p->data);
p = p->next;
}
printf("%d ",p->data);
printf("\n");
}
//打印輸出帶頭結(jié)點(diǎn)的循環(huán)雙鏈表中所有元素。
void Show_Yes(List head)
{
SeqNode p = head.phead->next;
while(head.phead != p)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
寫到這里循環(huán)鏈表的基本操作就寫完了，當(dāng)然有幾個(gè)操作沒(méi)有寫，比如排序，這里先不寫，后邊會(huì)有一個(gè)專題是寫排序的。還有獲取鏈表長(zhǎng)度等大家都很容易實(shí)現(xiàn)的就沒(méi)有寫，主要把帶頭結(jié)點(diǎn)不帶頭結(jié)點(diǎn)的插入刪除對(duì)比的實(shí)現(xiàn)。后續(xù)會(huì)繼續(xù)完善。好了以上就是雙循環(huán)鏈表的基本操作，雙循環(huán)鏈表寫完了，線性表也就告一段落了。ok，從線性表到鏈表，我把帶頭節(jié)點(diǎn)不帶頭結(jié)點(diǎn)的基本操作都盡可能多的實(shí)現(xiàn)了，我們會(huì)發(fā)現(xiàn)帶頭結(jié)點(diǎn)的操作會(huì)方便了好多。接下來(lái)，數(shù)據(jù)結(jié)構(gòu)繼續(xù)向前推進(jìn)
當(dāng)前名稱：循環(huán)鏈表之雙循環(huán)鏈表（C語(yǔ)言版）
新聞來(lái)源：http://m.biofuelwatch.net/article/pehcsp.html
