C++零基礎(chǔ)精通數(shù)據(jù)結(jié)構(gòu)之帶頭雙向循環(huán)鏈表

更新時(shí)間：2022年03月30日 16:43:41 作者：雪芙花

帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來(lái)很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡(jiǎn)單

與單鏈表的區(qū)別

單向/雙向

單向：只有一個(gè)ｎｅｘｔ指針，只指向下一位元素

雙向：有兩個(gè)指針，指向上一位和下一位元素，尋找前一節(jié)點(diǎn)和后一節(jié)點(diǎn)很便利

在這里插入圖片描述

帶頭/不帶頭

帶頭：在本來(lái)的頭結(jié)點(diǎn)之前還有一個(gè)哨兵衛(wèi)節(jié)點(diǎn)作為頭節(jié)點(diǎn)，它的址域指針指向頭節(jié)點(diǎn)，值域不做使用
不帶頭：沒(méi)有哨兵衛(wèi)頭節(jié)點(diǎn)，在尾刪尾插等問(wèn)題中要考慮頭結(jié)點(diǎn)的情況（局限）

循環(huán)/非循環(huán)

循環(huán)：頭結(jié)點(diǎn)會(huì)與尾節(jié)點(diǎn)相連

非循環(huán)：頭結(jié)點(diǎn)不與尾節(jié)點(diǎn)相連

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

接口

// 創(chuàng)建鏈表（鏈表初始化）
ListNode* ListCreate();
//創(chuàng)建節(jié)點(diǎn)
ListNode* BuyListNode(ListNode* pHead);
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead);
// 雙向鏈表打印
void ListPrint(ListNode* pHead);
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead);
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead);
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表刪除pos位置的節(jié)點(diǎn)
void ListErase(ListNode* pos);

節(jié)點(diǎn)的構(gòu)造

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

初始化鏈表

// 創(chuàng)建鏈表（初始化）
ListNode* ListCreate()
{
	//開(kāi)辟哨兵衛(wèi)頭結(jié)點(diǎn)
	ListNode* plist = (ListNode*)malloc(sizeof(ListNode));
	if (plist == NULL)//失敗打印錯(cuò)誤信息并結(jié)束進(jìn)程
	{
		perror("ListCreat fail:");
		exit(-1);
	}
	plist->next = plist;
	plist->prev = plist;
	return plist;
}

開(kāi)辟節(jié)點(diǎn)

//創(chuàng)建節(jié)點(diǎn)
ListNode* BuyListNode(LTDataType x)
{
	//創(chuàng)建節(jié)點(diǎn)
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)//失敗打印錯(cuò)誤信息并結(jié)束進(jìn)程
	{
		perror("creatnode fail:");
		exit(-1);
	}
	newnode->data = x;
	//初始化結(jié)點(diǎn)
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

銷毀鏈表

注：動(dòng)態(tài)開(kāi)辟的鏈表空間，在不使用后需要將之釋放，避免造成內(nèi)存泄漏

// 雙向鏈表銷毀
void ListDestory(ListNode* pHead)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	ListNode* cur = pHead;
	pHead->prev->next = NULL;
	while (cur!=NULL)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	return;
}

打印鏈表

// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	//創(chuàng)建尋址指針
	ListNode* cur = pHead->next;
	//循環(huán)遍歷鏈表
	while (cur != pHead)
	{
		//打印數(shù)據(jù)
		printf("%d->", cur->data);
		//找到下一個(gè)節(jié)點(diǎn)
		cur = cur->next;
	}printf("NULL\n");
	return;
}

尾插鏈表

// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	//創(chuàng)建節(jié)點(diǎn)
	ListNode* newnode = BuyListNode(x);
	//找到尾節(jié)點(diǎn)
	ListNode* tail=pHead->prev;
	tail->next = newnode;
	newnode->prev = tail;
 
	pHead->prev = newnode;
	newnode->next = pHead;
}

尾刪鏈表

尾刪前記錄前一節(jié)點(diǎn)的地址

// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	//只剩哨兵衛(wèi)頭結(jié)點(diǎn)的情況
	if (pHead->prev == pHead)
		return;
	//記錄尾節(jié)點(diǎn)及其前一節(jié)點(diǎn)
	ListNode* tail = pHead->prev;
	ListNode* tailprev = tail->prev;
	//釋放尾節(jié)點(diǎn)
	free(tail);
	//構(gòu)建尾節(jié)點(diǎn)前一節(jié)點(diǎn)與哨兵衛(wèi)頭結(jié)點(diǎn)的關(guān)系
	tailprev->next = pHead;
	pHead->prev = tailprev;
	return;
}

頭插鏈表

頭插前記錄哨兵衛(wèi)頭節(jié)點(diǎn)的下一節(jié)點(diǎn)

// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	//創(chuàng)建節(jié)點(diǎn)
	ListNode* newnode = BuyListNode(x);
	//記錄哨兵衛(wèi)頭結(jié)點(diǎn)的下一節(jié)點(diǎn)
	ListNode* next = pHead->next;
	//構(gòu)建各節(jié)點(diǎn)之間的關(guān)系
	pHead->next = newnode;
	newnode->prev = pHead;
 
	newnode->next = next;
	next->prev = newnode;
	return;
}

頭刪鏈表

// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	//只剩哨兵衛(wèi)頭結(jié)點(diǎn)的情況
	if (pHead->next == pHead)
		return;
	//記錄哨兵衛(wèi)頭結(jié)點(diǎn)下一節(jié)點(diǎn)及其的下一節(jié)點(diǎn)
	ListNode* next = pHead->next;
	ListNode* nextNext = next->next;
	//釋放節(jié)點(diǎn)
	free(next);
	pHead->next = nextNext;
	nextNext->prev = pHead;
	return;
}

查找鏈表

// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	//斷言傳入指針不為NULL
	assert(pHead);
	//創(chuàng)建尋址指針
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		//比較數(shù)據(jù)
		if (cur->data == x)
			return cur;
		//找到下一個(gè)節(jié)點(diǎn)
		cur = cur->next;
	}
	//沒(méi)找到則返回NULL
	return NULL;
}

鏈表pos位置的刪除

void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
	return;
}

總結(jié)

我們?cè)趯?shí)帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來(lái)很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡(jiǎn)單現(xiàn)的時(shí)候可以看出其實(shí)帶頭雙向循環(huán)鏈表實(shí)現(xiàn)起來(lái)并不難，而且在雙向循環(huán)特點(diǎn)的加持下，在一些方面顯得格外方便。

但是因?yàn)閹ь^雙向循環(huán)鏈表結(jié)構(gòu)的復(fù)雜性，我們通常還是會(huì)使用邏輯結(jié)構(gòu)相對(duì)簡(jiǎn)單的單鏈表，并且在oj題上考的最多的也是單鏈表。

但我們?nèi)砸炀氄莆諑ь^雙向循環(huán)鏈表的結(jié)構(gòu)和實(shí)現(xiàn)方式，因?yàn)檫@是一種特別且方便的結(jié)構(gòu)，且用處十分強(qiáng)大。

到此這篇關(guān)于C++零基礎(chǔ)精通數(shù)據(jù)結(jié)構(gòu)之帶頭雙向循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C++ 帶頭雙向循環(huán)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: