導(dǎo)航

1、帶頭雙向循環(huán)鏈表介紹

在上一篇博客我們講述了鏈表的概念和結(jié)構(gòu)，還實(shí)現(xiàn)了無頭單向非循環(huán)鏈表接口寫法，那么這一章節(jié)，我們來實(shí)現(xiàn)另一種常用的鏈表組成結(jié)構(gòu)——帶頭雙向循環(huán)鏈表。
如果對(duì)前面的鏈表基本概念還是不了解，可以看作者的上一篇博客：
線性表中鏈表介紹及無頭單向非循環(huán)鏈表接口實(shí)現(xiàn)

2、結(jié)構(gòu)體及接口函數(shù)定義

首先是結(jié)構(gòu)體的定義
代碼如下：

typedef int LTDateType;
typedef struct ListNode
{
	LTDateType data;//結(jié)點(diǎn)存儲(chǔ)元素
	struct ListNode* next;//下一結(jié)點(diǎn)指針
	struct ListNode* prev;//上一結(jié)點(diǎn)指針
}LTNode;

然后就是接口函數(shù)的定義
代碼如下：

void ListInit(LTNode* phead)；//哨兵位頭結(jié)點(diǎn)初始化
LTNode* BuyListNode(LTDateType x);//動(dòng)態(tài)申請(qǐng)結(jié)點(diǎn)
void ListPushBack(LTNode* phead, LTDateType x);//雙向鏈表尾插
void ListPopBack(LTNode* phead);//雙向鏈表尾刪
void ListPushFront(LTNode* phead, LTDateType x);//雙向鏈表頭插
void ListPopFront(LTNode* phead);//雙向鏈表頭刪
LTNode* ListFind(LTNode* phead, LTDateType x);//雙向鏈表查找
void ListInsert(LTNode* pos, LTDateType x);//在pos位置前插入
void ListErase(LTNode* pos);//刪除pos位置的結(jié)點(diǎn)
void ListPrint(LTNode* phead);//打印雙向鏈表
void ListDestroy(LTNode* phead);//銷毀雙向鏈表

3、接口函數(shù)實(shí)現(xiàn)

在上一篇博客中我們講到不帶頭的單非循環(huán)鏈表存在一定缺陷，就是無法訪問上一結(jié)點(diǎn)，但是這一節(jié)講的帶頭雙向循環(huán)鏈表就很好的彌補(bǔ)了這一缺點(diǎn)，帶頭雙向循環(huán)鏈表看來比單鏈表結(jié)構(gòu)要復(fù)雜很多，但其實(shí)實(shí)現(xiàn)起來要比單鏈表更簡(jiǎn)單，更高效；下面我們就來實(shí)現(xiàn)帶頭雙向循環(huán)鏈表的接口函數(shù)吧！

3.1 頭結(jié)點(diǎn)初始化

頭結(jié)點(diǎn)初始化（ListInit）
首先是我們的頭結(jié)點(diǎn)的定義，它是不存放數(shù)據(jù)的，起到一個(gè)哨兵的作用
代碼如下：

void ListInit(LTNode* phead)
{
	// 哨兵位頭結(jié)點(diǎn)
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

第一步當(dāng)然是先使用malloc函數(shù)申請(qǐng)內(nèi)存空間，然后就是兩個(gè)指針的建立，尾部指針指向頭結(jié)點(diǎn)頭部，頭部指針指向頭結(jié)點(diǎn)尾部，返回帶頭結(jié)點(diǎn)，頭結(jié)點(diǎn)初始化完成。

3.2 結(jié)點(diǎn)動(dòng)態(tài)內(nèi)存申請(qǐng)

結(jié)點(diǎn)動(dòng)態(tài)內(nèi)存申請(qǐng)（BuyListNode）
這個(gè)函數(shù)和上一篇中的單鏈表的函數(shù)類似
代碼如下:

LTNode* BuyListNode(LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

第一步也是先使用malloc函數(shù)申請(qǐng)內(nèi)存空間，然后就是初始化這個(gè)結(jié)點(diǎn)的操作，將元素插入，兩個(gè)指針指向空，返回新結(jié)點(diǎn)，完成結(jié)點(diǎn)初始化操作。

3.3 雙向鏈表尾插

雙向鏈表尾插（ListPushBack）
代碼如下：

void ListPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);

	LTNode* tail = phead->prev;
	LTNode* newnode = BuyListNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

這里我們先是把phead的上一級(jí)指針賦給tail
再將要插入的元素賦給臨時(shí)結(jié)點(diǎn)newnode
接著將tail的下一級(jí)指針指向newnode
再將newnode上一級(jí)指針指向tail
newnode下一級(jí)指針指向被插入結(jié)點(diǎn)phead
最后將phead的上一級(jí)指針再指向newnode完成尾插操作

3.4 雙向鏈表尾刪

雙向鏈表尾刪（ListPopBack）
代碼如下：

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//防止鏈表中無元素繼續(xù)刪除的斷言

	LTNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next = phead;

	free(tail);
}

上述代碼中第二個(gè)斷言是為了防止鏈表中無元素繼續(xù)刪除
這里我們也是先把phead的上一級(jí)指針賦給tail
再將tail的上一級(jí)指針賦給phead的上一級(jí)指針
也就是指向要?jiǎng)h除結(jié)點(diǎn)的上一結(jié)點(diǎn)
最后將要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的下一級(jí)指針指向頭結(jié)點(diǎn)
然后釋放掉tail的內(nèi)存空間完成尾刪

3.5 雙向鏈表頭插

雙向鏈表頭插（ListPushFront）
代碼如下：

void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* next = phead->next;

	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = next;
	next->prev = newnode;
}

這里我們先和尾插一樣將要插入的元素值賦給臨時(shí)結(jié)點(diǎn)newnode
將phead下一級(jí)指針賦給臨時(shí)結(jié)點(diǎn)next
再將newnode賦給phead下一級(jí)指針
也就是把phead的尾部指針指向newnode
把phead賦給newnode的上一級(jí)指針
再將next賦給newnode的下一級(jí)指針
最后把newnode賦給next的上一級(jí)指針，完成頭插

3.6 雙向鏈表頭刪

雙向鏈表頭刪（ListPopFront）
代碼如下：

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//防止鏈表中無元素繼續(xù)刪除的斷言

	LTNode* next = phead->next;
	LTNode* nextNext = next->next;

	phead->next = nextNext;
	nextNext->prev = phead;
	free(next);
}

和尾刪一樣這里的第二個(gè)斷言也是為了防止鏈表中無元素繼續(xù)刪除
頭刪的第一步就是將phead的下一級(jí)指針賦給next
再將next的下一級(jí)指針賦給nextNext
再將nextNext賦給phead的下一級(jí)指針
最后將phead賦給nextNext的上一指針
把next的內(nèi)存空間釋放完成頭刪

3.7 雙向鏈表查找

雙向鏈表查找（ListFind）
代碼如下：

LTNode* ListFind(LTNode* phead, LTDateType x)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

這里的查找就是使用一個(gè)while循環(huán)遍歷鏈表找到某節(jié)點(diǎn)的data符合要查找的值
找到了便返回結(jié)點(diǎn)，如果遍歷一遍沒找到，則返回空（NULL）。

3.8 在pos位置前插入

pos位置前插入（ListInsert）
代碼如下：

void ListInsert(LTNode* pos, LTDateType x)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyListNode(x);

	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

插入函數(shù)的實(shí)現(xiàn)首先創(chuàng)建第一個(gè)臨時(shí)結(jié)點(diǎn)posPrev
把pos的上一級(jí)指針賦給posPrev
將要插入的元素x賦給newnode
再將newnode賦給posPrev的下一級(jí)指針
再將posPrev賦給newnode的上一級(jí)指針
再將pos賦給newnode的下一級(jí)指針
最后將再將newnode賦給pos的上一級(jí)指針完成插入操作
在這里我們可以利用ListInsert函數(shù)將前面的尾插和頭插進(jìn)行同義替換
雙向鏈表尾插（ListPushBack）同義替換
代碼如下：

void ListPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);
	ListInsert(phead, x);
}

雙向鏈表頭插（ListPushFront）同義替換
代碼如下：

void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

3.9 刪除pos位置的結(jié)點(diǎn)

刪除pos位置的結(jié)點(diǎn)（ListErase）
代碼如下：

void ListErase(LTNode* pos)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
	pos = NULL;
}

首先將pos的上一級(jí)指針賦給posPrev
再將將pos的下一級(jí)指針賦給posNext
再將posNext賦給posPrev下一級(jí)指針
最后把posPrev賦給posNext上一級(jí)指針
將pos內(nèi)存空間釋放，使pos等于空（NULL），完成刪除。
同樣的，我們也可以利用這個(gè)ListErase函數(shù)對(duì)尾刪和頭刪進(jìn)行同義替換
雙向鏈表尾刪（ListPopBack）同義替換
代碼如下：

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListErase(phead->prev);
}

雙向鏈表頭刪（ListPopFront）同義替換
代碼如下：

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListErase(phead->next);
}

3.10 打印雙向鏈表

打印雙向鏈表（ListPrint）
代碼如下：

void ListPrint(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

這里的打印操作同樣是利用while循環(huán)進(jìn)行一遍遍歷打印輸出

3.11 銷毀雙向鏈表

銷毀雙向鏈表（ListDestroy）
代碼如下：

void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	phead = NULL;
}

和打印函數(shù)原理一樣，只不過這里是再進(jìn)行遍歷的同時(shí)進(jìn)行逐個(gè)刪除
最后將phead內(nèi)存空間釋放，令phead等于空（NULL）完成鏈表銷毀操作。
在這里最后講一下斷言，在之前的單鏈表那一節(jié)的接口函數(shù)都有，寫斷言是為了讓代碼更健壯
一旦出現(xiàn)了編譯錯(cuò)誤，我們可以立馬排查出問題出在哪里，這是一個(gè)不錯(cuò)的代碼習(xí)慣
帶頭雙向循環(huán)鏈表接口代碼可能不是那么好理解，但是實(shí)現(xiàn)起來時(shí)，卻更方便，所以帶頭雙向循環(huán)鏈表對(duì)于我們來說是非常必要的知識(shí)點(diǎn)！

4、順序表和鏈表的區(qū)別

5、結(jié)語

順序表到這一篇就結(jié)束了，這里的帶頭雙向循環(huán)鏈表可能在代碼體現(xiàn)上不是那么容易理解，這需要我們不斷的去進(jìn)行學(xué)習(xí)和實(shí)操，如果知識(shí)光看，在數(shù)據(jù)結(jié)構(gòu)這門課的學(xué)習(xí)上是不會(huì)有提高的，最重要的還是練習(xí)！?。?mark hidden color="red">文章來源：http://www.zghlxwxcb.cn/news/detail-410927.html

制作不易，如有不正之處敬請(qǐng)指出，感謝大家的來訪，UU們的觀看是我堅(jiān)持下去的動(dòng)力，在時(shí)間的催化劑下，讓我們彼此都成為更優(yōu)秀的人吧?。?！不要忘了一鍵三連呦！文章來源地址http://www.zghlxwxcb.cn/news/detail-410927.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)入門（C語言版）線性表帶頭雙向循環(huán)鏈表接口實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！