C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

發(fā)布時(shí)間：2022-04-11 13:47:57 來源：億速云閱讀：153 作者：iii 欄目：開發(fā)技術(shù)

這篇文章主要講解了“C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)”吧！

一、概念

來畫張圖總體回顧下：

在我們學(xué)習(xí)的鏈表中，其實(shí)總共有8種，都是單雙向和帶不帶頭以及帶不帶環(huán)的任意組合

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

今兒要學(xué)習(xí)的是雙向 - 帶頭 - 循環(huán)鏈表，聽名字就覺著結(jié)構(gòu)很復(fù)雜，要比曾經(jīng)學(xué)的單向 - 不帶頭 - 不循環(huán) 鏈表的結(jié)構(gòu)復(fù)雜的多，確實(shí)也是。先來畫張圖整體感受下：

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

解釋：

雙向：就要確保每個(gè)數(shù)據(jù)存兩個(gè)指針next和prev。next指向下一個(gè)節(jié)點(diǎn)，prev指向上一個(gè)節(jié)點(diǎn)
帶頭：帶一個(gè)哨兵位的頭節(jié)點(diǎn)在數(shù)據(jù)的最前頭。
循環(huán)：尾節(jié)點(diǎn)的next指向哨兵位頭節(jié)點(diǎn)，而哨兵位的上一個(gè)節(jié)點(diǎn)prev指向尾節(jié)點(diǎn)，構(gòu)成循環(huán)。

正文開始：

二、必備工作

2.1、創(chuàng)建雙向鏈表結(jié)構(gòu)

因?yàn)槭请p向鏈表，所以在結(jié)構(gòu)體里頭必然有兩個(gè)指針，一個(gè)next指向下一個(gè)節(jié)點(diǎn)，一個(gè)prev指向上一個(gè)節(jié)點(diǎn)。

List.h 文件：

//創(chuàng)建雙向鏈表結(jié)構(gòu)
typedef int LTDataType;   //方便后續(xù)更改數(shù)據(jù)類型，本文以int整型為主
typedef struct ListNode
{
	LTDataType data; //存儲(chǔ)數(shù)據(jù)
	struct ListNode* next; //指向下一個(gè)
	struct ListNode* prev; //指向上一個(gè)
}LTNode; //方便后續(xù)使用，不需要重復(fù)些struct

2.2、初始化鏈表

思路：

在初始化的時(shí)候要傳地址，因?yàn)樾螀⒌母淖儾粫?huì)影響實(shí)參，pphead的改變不會(huì)影響pList，要傳pList的地址，用**pphead來接收，此時(shí)就要assert斷言了，因?yàn)槎?jí)指針地址不可能位空。因?yàn)槭请p向循環(huán)鏈表，所以要將創(chuàng)建好的哨兵位節(jié)點(diǎn)的next和prev均指向自己。

List.h 文件：（1）

//初始化鏈表（二級(jí)指針版）
void ListInit(LTNode* pphead);

List.c 文件：（1）

//初始化鏈表（二級(jí)指針版）
void ListInit(LTNode** pphead)
{
	//傳二級(jí)指針，那么當(dāng)然要斷言
	assert(pphead);
	*pphead = BuyLTNode(0);//因?yàn)槭菐诒坏念^節(jié)點(diǎn)，所以一開始就要給一個(gè)節(jié)點(diǎn)
	//為了循環(huán)，要讓哨兵位的next和prev均指向自己
	(*pphead)->next = *pphead; //注意優(yōu)先級(jí)，*pphead要加括號(hào)
	(*pphead)->prev = *pphead;
}

注意：

上一種方法我們傳的是二級(jí)指針，那么可以傳一級(jí)指針嗎，其實(shí)也是可以的，只需寫個(gè)函數(shù)返回指針即可

List.h 文件：（2）

//初始化鏈表（一級(jí)指針版本）
LTNode* ListInit();

List.c 文件：（2）

//初始化鏈表（一級(jí)指針版）
LTNode* ListInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

2.3、動(dòng)態(tài)申請(qǐng)節(jié)點(diǎn)

List.c 文件：

//創(chuàng)建新節(jié)點(diǎn)
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode; //返回新創(chuàng)建的節(jié)點(diǎn)
}

2.4、打印鏈表

思路：

既然是打印，首先要搞明白一點(diǎn)，哨兵位不用來存放有效數(shù)據(jù)，那么就不需要打印，定義一個(gè)cur指針來迭代，那么應(yīng)該從phead的next開始打印，當(dāng)cur走完一遍，重又回到phead的時(shí)候停止

List.h 文件：

//打印鏈表
void ListPrint(LTNode* phead);

List.c 文件：

//打印鏈表
void ListPrint(LTNode* phead)
{
	assert(phead);//斷言
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.5、銷毀鏈表

思路：

既然是銷毀鏈表了，那么自然是要把鏈表的所有元素包括哨兵位都給銷毀掉，但畢竟剛開始傳phead的時(shí)候是不能為空的，所以要斷言，在把所有有效數(shù)據(jù)銷毀后最后再銷毀哨兵位即可。

法一：遍歷

定義一個(gè)指針cur，從phead的next第一個(gè)有效數(shù)據(jù)開始free，保存下一個(gè)，再free，依次遍歷下去

法二：附用ListErase函數(shù)

此法也可以，不過每次Erase完，都會(huì)把前后兩個(gè)節(jié)點(diǎn)再鏈接起來，雖說最后都會(huì)銷毀，但duck不必多此一舉，所有直接采用法一比較好

List.h 文件：

//銷毀鏈表
void ListDestory(LTNode* phead);

List.c 文件：

//銷毀鏈表
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	//銷毀從第一個(gè)節(jié)點(diǎn)到尾部的數(shù)據(jù)
	while (cur != phead)
	{
		LTNode* next = cur->next;
		//ListErase(cur);
		free(cur);
		cur = next;
	}
	//置空哨兵位節(jié)點(diǎn)phead
	free(phead);
	phead = NULL;
}

Test.c 文件：

void TestList7()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)字
	}
	ListPrint(pList);//打印
	//銷毀鏈表
	ListDestory(pList);
	pList = NULL;
}

三、主要功能

3.1、在pos節(jié)點(diǎn)前插入數(shù)據(jù)

思路：

假設(shè)我們已經(jīng)進(jìn)行了尾插4個(gè)數(shù)字，現(xiàn)在想在數(shù)字3的前面插入30，那么首先就要查找有無數(shù)字3，若有，則插入。注意：這里需要用到后文才講到的查找函數(shù)，這里直接引用了，詳解看后文即可，問題不大！

首先，將30放到新創(chuàng)建的節(jié)點(diǎn)newnode里頭，為了實(shí)現(xiàn)雙向，要先把3的前一個(gè)數(shù)據(jù)2的next指向新節(jié)點(diǎn)newnode，把newnode的prev指向2，newnode的next指向3，3的prev指向newnode。

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

List.h 文件：

//在pos前插入數(shù)據(jù)
void ListInsert(LTNode* pos, LTDataType x);

List.c 文件：

//在pos前插入數(shù)據(jù)
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	//創(chuàng)建插入數(shù)據(jù)的新節(jié)點(diǎn)
	LTNode* newnode = BuyLTNode(x);
	//鏈接左側(cè)
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	//鏈接右側(cè)
	newnode->next = pos;
	pos->prev = newnode;
}

Test.c 文件：

void TestList3()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個(gè)
	//尋找數(shù)字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListInsert(pos, 30); //找到數(shù)字3就插入
	}
	ListPrint(pList);//打印
}

效果如下：

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

尾插

思路：

首先，因?yàn)榇随湵硎菐诒坏念^節(jié)點(diǎn)，所以頭節(jié)點(diǎn)必然不為空，剛開始就要assert斷言。其次，單鏈表尾插需要找尾，雙向鏈表雖然也需要，不過非常簡(jiǎn)單，不需要再遍歷鏈表了，因?yàn)樯诒活^節(jié)點(diǎn)的phead的上一個(gè)節(jié)點(diǎn)指向的就是尾，這就充分體現(xiàn)了雙向循環(huán)的好處，找到了尾節(jié)點(diǎn)就需要再創(chuàng)建一個(gè)節(jié)點(diǎn)存儲(chǔ)插入數(shù)據(jù)，方便尾插。

List.h 文件：

//尾插
void ListPushBack(LTNode* phead, LTDataType x);

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

List.c 文件：1.0

//尾插1.0
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); //斷言，防止頭節(jié)點(diǎn)為空
	LTNode* tail = phead->prev; //找到尾節(jié)點(diǎn)，便于后續(xù)插入數(shù)據(jù)
	LTNode* newnode = BuyLTNode(x);//創(chuàng)建新節(jié)點(diǎn)
	//將此新插入的尾節(jié)點(diǎn)與上一個(gè)節(jié)點(diǎn)鏈接起來
	tail->next = newnode;
	newnode->prev = tail;
	//將尾節(jié)點(diǎn)與哨兵位phead鏈接起來構(gòu)成循環(huán)
	newnode->next = phead;
	phead->prev = newnode;
}

Test.c 文件：

void TestList1()
{
	//初始化（法一）
	/*LTNode* pList = NULL;
	ListInit(&pList);*/
	//初始化（法二）
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個(gè)
}

效果如下：

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

注意：

在上文中，我們學(xué)習(xí)了在pos前插入數(shù)據(jù)，那么設(shè)想一下，當(dāng)pos就等于phead的時(shí)候，它（phead）的前不就是鏈表的尾部嗎，那么理所應(yīng)當(dāng)，尾插也可以這樣完成：

List.c 文件：2.0

//尾插2.0
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); 
	ListInsert(phead, x);
}

頭插

思路：

前面我們已經(jīng)學(xué)習(xí)了在pos前插入數(shù)據(jù)，那么頭插的實(shí)現(xiàn)就尤為簡(jiǎn)單了，當(dāng)pos為原第一個(gè)數(shù)據(jù)phead->next時(shí)，此時(shí)就是在其之前插入數(shù)據(jù)，那么實(shí)現(xiàn)的不久是頭插嗎，如下：

List.h 文件：

//頭插
void ListPushFront(LTNode* phead, LTDataType x);

List.c 文件：

//頭插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

Test.c 文件：

void TestList4()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)字
	}
	ListPrint(pList);//打印
	for (int i = -2; i <= 0; i++)
	{
		ListPushFront(pList, i); //頭插3個(gè)數(shù)字
	}
	ListPrint(pList);//打印
}

效果如下：

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

3.2、刪除pos處節(jié)點(diǎn)數(shù)據(jù)

思路：

刪除pos處數(shù)據(jù)其實(shí)也很簡(jiǎn)單，有點(diǎn)類似于把pos處直接忽略的思想，或者說是繞過去。首先，需要找到pos的上一個(gè)節(jié)點(diǎn)prev和下一個(gè)節(jié)點(diǎn)next，將prev和next互相鏈接即可，直接跳過了pos，這樣就實(shí)現(xiàn)了刪除pos處節(jié)點(diǎn)的數(shù)據(jù)，記得把pos處給free釋放掉。這里我們以pos為2示例：

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

List.h 文件：

//刪除pos處數(shù)據(jù)
void ListErase(LTNode* pos);

List.c 文件：

//刪除pos處數(shù)據(jù)
void ListErase(LTNode* pos)
{
	assert(pos);
	//定義兩個(gè)指針保存pos兩邊的節(jié)點(diǎn)
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	//將prev和next鏈接起來
	prev->next = next;
	next->prev = prev;
	//free釋放
	free(pos);
	pos = NULL;
}

Test.c 文件：

void TestList5()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個(gè)
	//尋找數(shù)字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListErase(pos); //刪除pos處數(shù)據(jù)
		pos = NULL; //形參的改變不會(huì)影響實(shí)參，最好在這置空pos
	}
	ListPrint(pList);//打印
}

效果如下：

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

尾刪

思路：

雙向循環(huán)鏈表的特點(diǎn)將再次得以體現(xiàn)，根據(jù)其特性，我們知道phead的prev指向尾節(jié)點(diǎn)，用tail指針保存，再定義一個(gè)指針tailPrev指向tail的prev，現(xiàn)僅需將tailPrev的next指向哨兵位節(jié)點(diǎn)phead，再把哨兵位phead的prev重新置成tailPrev即可，但是別忘記把刪掉的尾節(jié)點(diǎn)給釋放掉，得free(tail)。記得要斷言鏈表不能為空，因?yàn)椴荒軇h除哨兵位節(jié)點(diǎn)。

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

List.H 文件：

//尾刪
void ListPopBack(LTNode* phead);

List.c 文件：1.0

//尾刪
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位，不能為空，要斷言
	assert(phead->next != phead); //防止鏈表為空，導(dǎo)致刪除哨兵位節(jié)點(diǎn)
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	//釋放尾節(jié)點(diǎn)
	free(tail);
	tail = NULL;
	//將鏈表循環(huán)起來
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

Test.c 文件：

void TestList2()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個(gè)
	//尾刪兩次
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//再次打印
}

效果如下：

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

注意：

前文我們已經(jīng)學(xué)了刪除pos處節(jié)點(diǎn)的數(shù)據(jù)，那么當(dāng)pos為phead->prev時(shí)，刪除的是不是就是尾節(jié)點(diǎn)，所以，尾刪理所應(yīng)當(dāng)可以這樣寫：

List.c 文件：2.0

//尾刪
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位，不能為空，要斷言
	assert(phead->next != phead); //防止鏈表為空，導(dǎo)致刪除哨兵位節(jié)點(diǎn)
	ListErase(phead->prev);
}

頭刪

思路：

有了上文之鑒，我們可以直接利用前面寫的刪除pos處數(shù)據(jù)的函數(shù)來完成，當(dāng)pos為phead->prev時(shí)，pos的位置就是尾，此時(shí)刪除的就是尾。當(dāng)然還得注意一點(diǎn)，需要額外assert斷言防止刪除的數(shù)據(jù)為哨兵位的節(jié)點(diǎn)。

List.h 文件：

//頭刪
void ListPopFront(LTNode* phead);

List.c 文件：

//頭刪
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); //防止刪除哨兵位節(jié)點(diǎn)
	ListErase(phead->next);
}

Test.c 文件：

void TestList6()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)字
	}
	ListPrint(pList);//打印
	//頭插3個(gè)數(shù)字
	ListPushFront(pList, 0);
	ListPushFront(pList, -1);
	ListPushFront(pList, -2);
	ListPrint(pList);//打印
	//尾刪3個(gè)數(shù)字
	ListPopBack(pList);
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//打印
	//頭刪3個(gè)數(shù)字
	ListPopFront(pList);
	ListPopFront(pList);
	ListPopFront(pList);
	ListPrint(pList);//打印
}

效果如下：

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

3.3、查找數(shù)據(jù)

思路：

查找數(shù)據(jù)其實(shí)也比較簡(jiǎn)單，首先，定義一個(gè)指針cur指向哨兵位phead的next，依次遍歷cur看cur->data是否為查找的數(shù)據(jù)x，如果是，則返回cur，否則繼續(xù)（cur=cur->next），若找不到則返回NULL。

List.h 文件：

//鏈表查找
LTNode* ListFind(LTNode* phead, LTDataType x);

List.c 文件：

//鏈表查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur; //找到就返回cur
		}
		cur = cur->next;
	}
	return NULL; //找不到就返回空
}

四、總代碼

List.h 文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//創(chuàng)建雙向鏈表結(jié)構(gòu)
typedef int LTDataType;   //方便后續(xù)更改數(shù)據(jù)類型，本文以int整型為主
typedef struct ListNode
{
	LTDataType data; //存儲(chǔ)數(shù)據(jù)
	struct ListNode* next; //指向下一個(gè)
	struct ListNode* prev; //指向上一個(gè)
}LTNode; //方便后續(xù)使用，不需要重復(fù)些struct
 
//初始化鏈表（二級(jí)指針版本）
/*void ListInit(LTNode** pphead);*/
//初始化鏈表（一級(jí)指針版本）
LTNode* ListInit();
 
//打印鏈表
void ListPrint(LTNode* phead);
//鏈表查找
LTNode* ListFind(LTNode* phead, LTDataType x);
//銷毀鏈表
void ListDestory(LTNode* phead);
 
//尾插
void ListPushBack(LTNode* phead, LTDataType x);
//尾刪
void ListPopBack(LTNode* phead);
//頭插
void ListPushFront(LTNode* phead, LTDataType x);
//頭刪
void ListPopFront(LTNode* phead);
 
//在pos前插入數(shù)據(jù)
void ListInsert(LTNode* pos, LTDataType x);
//刪除pos處數(shù)據(jù)
void ListErase(LTNode* pos);

List.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//創(chuàng)建新節(jié)點(diǎn)
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode; //返回新創(chuàng)建的節(jié)點(diǎn)
}
//初始化鏈表（二級(jí)指針版）
/*void ListInit(LTNode** pphead)
{
	//傳二級(jí)指針，那么當(dāng)然要斷言
	assert(pphead);
	*pphead = BuyLTNode(0);//因?yàn)槭菐诒坏念^節(jié)點(diǎn)，所以一開始就要給一個(gè)節(jié)點(diǎn)
	//為了循環(huán)，要讓哨兵位的next和prev均指向自己
	(*pphead)->next = *pphead; //注意優(yōu)先級(jí)，*pphead要加括號(hào)
	(*pphead)->prev = *pphead;
}*/
//初始化鏈表（一級(jí)指針版）
LTNode* ListInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
 
//打印鏈表
void ListPrint(LTNode* phead)
{
	assert(phead);//斷言
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//鏈表查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur; //找到就返回cur
		}
		cur = cur->next;
	}
	return NULL; //找不到就返回空
}
//銷毀鏈表
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	//銷毀從第一個(gè)節(jié)點(diǎn)到尾部的數(shù)據(jù)
	while (cur != phead)
	{
		LTNode* next = cur->next;
		//ListErase(cur);
		free(cur);
		cur = next;
	}
	//置空哨兵位節(jié)點(diǎn)phead
	free(phead);
	phead = NULL;
}
 
//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); //斷言，防止頭節(jié)點(diǎn)為空
	/*
	法一：
	LTNode* tail = phead->prev; //找到尾節(jié)點(diǎn)，便于后續(xù)插入數(shù)據(jù)
	LTNode* newnode = BuyLTNode(x);//創(chuàng)建新節(jié)點(diǎn)
	//將此新插入的尾節(jié)點(diǎn)與上一個(gè)節(jié)點(diǎn)鏈接起來
	tail->next = newnode;
	newnode->prev = tail;
	//將尾節(jié)點(diǎn)與哨兵位phead鏈接起來構(gòu)成循環(huán)
	newnode->next = phead;
	phead->prev = newnode;
	*/
	//法二：
	ListInsert(phead, x);
}
//尾刪
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位，不能為空，要斷言
	assert(phead->next != phead); //防止鏈表為空，導(dǎo)致刪除哨兵位節(jié)點(diǎn)
	/*
	法一：
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	//釋放尾節(jié)點(diǎn)
	free(tail);
	tail = NULL;
	//將鏈表循環(huán)起來
	tailPrev->next = phead;
	phead->prev = tailPrev;
	*/
	//法二：
	ListErase(phead->prev);
}
 
//頭插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}
//頭刪
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); //防止刪除哨兵位節(jié)點(diǎn)
	ListErase(phead->next);
}
 
//在pos前插入數(shù)據(jù)
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	//創(chuàng)建插入數(shù)據(jù)的新節(jié)點(diǎn)
	LTNode* newnode = BuyLTNode(x);
	//鏈接左側(cè)
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	//鏈接右側(cè)
	newnode->next = pos;
	pos->prev = newnode;
}
//刪除pos處數(shù)據(jù)
void ListErase(LTNode* pos)
{
	assert(pos);
	//定義兩個(gè)指針保存pos兩邊的節(jié)點(diǎn)
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	//將prev和next鏈接起來
	prev->next = next;
	next->prev = prev;
	//free釋放
	free(pos);
	pos = NULL;
}

Test.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void TestList1()
{
	//初始化（法一）
	/*LTNode* pList = NULL;
	ListInit(&pList);*/
	//初始化（法二）
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個(gè)
}
 
void TestList2()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個(gè)
	//尾刪兩次
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//再次打印
}
 
void TestList3()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個(gè)
	//尋找數(shù)字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListInsert(pos, 30); //找到數(shù)字3就插入
	}
	ListPrint(pList);//打印
}
 
void TestList4()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)字
	}
	ListPrint(pList);//打印
	for (int i = -2; i <= 0; i++)
	{
		ListPushFront(pList, i); //頭插3個(gè)數(shù)字
	}
	ListPrint(pList);//打印
}
 
void TestList5()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)據(jù)
	}
	ListPrint(pList);//打印尾插的7個(gè)
	//尋找數(shù)字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListErase(pos); //刪除pos處數(shù)據(jù)
		pos = NULL; //形參的改變不會(huì)影響實(shí)參，最好在這置空pos
	}
	ListPrint(pList);//打印
}
 
void TestList6()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)字
	}
	ListPrint(pList);//打印
	//頭插3個(gè)數(shù)字
	ListPushFront(pList, 0);
	ListPushFront(pList, -1);
	ListPushFront(pList, -2);
	ListPrint(pList);//打印
	//尾刪3個(gè)數(shù)字
	ListPopBack(pList);
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//打印
	//頭刪3個(gè)數(shù)字
	ListPopFront(pList);
	ListPopFront(pList);
	ListPopFront(pList);
	ListPrint(pList);//打印
	//銷毀鏈表
	ListDestory(pList);
	pList = NULL;
}
 
void TestList7()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個(gè)數(shù)字
	}
	ListPrint(pList);//打印
	//銷毀鏈表
	ListDestory(pList);
	pList = NULL;
}
int main()
{
	//TestList1();
	//TestList2();
	//TestList3();
	//TestList4();
	//TestList5();
	//TestList6();
	TestList7();
	return 0;
}

五、拓展

對(duì)比順序表和鏈表

不同點(diǎn)	順序表	鏈表
存儲(chǔ)空間上	物理上一定連續(xù)	邏輯上連續(xù)，但物理上不一定連續(xù)
隨機(jī)訪問	支持O(1)	不支持O(N)
任意位置插入或者刪除元素	可能需要搬移元素，效率低O(N)	只需修改指針指向
插入	動(dòng)態(tài)順序表，空間不夠時(shí)需要擴(kuò)容	沒有容量的概念
應(yīng)用場(chǎng)景	元素高效存儲(chǔ)+頻繁訪問	任意位置插入和刪除數(shù)據(jù)
緩存利用率	高	低

優(yōu)缺點(diǎn)對(duì)比：

順序表

鏈表

優(yōu)點(diǎn)

1、物理空間是連續(xù)的，方便用下標(biāo)隨機(jī)訪問。

2、CPU高速緩存命中率會(huì)更高。（補(bǔ)充）

1、按需申請(qǐng)釋放空間。

2、任意位置可以O(shè)(1)插入刪除數(shù)據(jù)。

缺點(diǎn)

1、正因?yàn)槲锢砜臻g連續(xù)，空間不夠需要擴(kuò)容，擴(kuò)容本身又一定消耗，其次擴(kuò)容機(jī)制還存在一定的空間浪費(fèi)。

2、頭部或者中部插入刪除，挪動(dòng)數(shù)據(jù)，效率低，O(N)。

1、不支持下標(biāo)的隨機(jī)訪問。

2、有些算法不適合在它上面進(jìn)行，如：二分查找、排序等。

感謝各位的閱讀，以上就是“C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

向AI問一下細(xì)節(jié)

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中雙向帶頭循環(huán)鏈表怎么實(shí)現(xiàn)

一、概念

二、必備工作

2.1、創(chuàng)建雙向鏈表結(jié)構(gòu)

2.2、初始化鏈表

2.3、動(dòng)態(tài)申請(qǐng)節(jié)點(diǎn)

2.4、打印鏈表

2.5、銷毀鏈表

三、主要功能

3.1、在pos節(jié)點(diǎn)前插入數(shù)據(jù)

尾插

頭插

3.2、刪除pos處節(jié)點(diǎn)數(shù)據(jù)

尾刪

頭刪

3.3、查找數(shù)據(jù)

四、總代碼

List.h 文件

List.c 文件

Test.c 文件

五、拓展

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽

一、概念

二、必備工作

2.1、創(chuàng)建雙向鏈表結(jié)構(gòu)

2.2、初始化鏈表

2.4、打印鏈表

2.5、銷毀鏈表

三、主要功能

四、總代碼