【數(shù)據(jù)結(jié)構(gòu)】帶頭雙向循環(huán)鏈表（小白入門必備知識）

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】帶頭雙向循環(huán)鏈表（小白入門必備知識）。希望對大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

前言:

????個(gè)人主頁:??????Dream_Chaser～?????

??專欄:http://t.csdn.cn/oXkBa

??本篇內(nèi)容:c語言數(shù)據(jù)結(jié)構(gòu)--帶頭雙向循環(huán)鏈表

一.帶頭雙向循環(huán)鏈表

?A.帶頭雙向循環(huán)鏈表概念

B.帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

1.帶頭雙向循環(huán)鏈表的結(jié)構(gòu)

2.動(dòng)態(tài)申請節(jié)點(diǎn)函數(shù)

3.鏈表的初始化

4.鏈表打印

5.鏈表尾部插入節(jié)點(diǎn)

6.鏈表頭部插入節(jié)點(diǎn)

7.鏈表尾刪節(jié)點(diǎn)?

8.鏈表頭刪節(jié)點(diǎn)

9.鏈表查找/修改某個(gè)值

10.在鏈表pos位置之前插入值

LTInsert實(shí)現(xiàn)尾插操作:

LTInsert實(shí)現(xiàn)頭插操作:

11.在鏈表pos位置處刪除此節(jié)點(diǎn)

LTErase實(shí)現(xiàn)尾刪:

LTErase實(shí)現(xiàn)頭刪

12.求鏈表的長度函數(shù)

13.釋放鏈表動(dòng)態(tài)申請的空間

Test.c

List.h

List.c

一.帶頭雙向循環(huán)鏈表

鏈表的分類

實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種鏈表結(jié)構(gòu)：

怎么算出8種情況:每次兩種情況，三次，所以是2*2*2=8。

1. 單向或者雙向

?2. 帶頭或者不帶頭

?3. 循環(huán)或者非循環(huán)

?雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是兩種結(jié)構(gòu)：

【數(shù)據(jù)結(jié)構(gòu)】帶頭雙向循環(huán)鏈表（小白入門必備知識）,C--數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c語言,筆記,vscode

1.? 無頭單向非循環(huán)鏈表： 結(jié)構(gòu)簡單 ，一般不會(huì)單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為 其他數(shù)據(jù)結(jié)

構(gòu)的子結(jié)構(gòu) ，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在 筆試面試 中出現(xiàn)很多。

? 【數(shù)據(jù)結(jié)構(gòu)】帶頭雙向循環(huán)鏈表（小白入門必備知識）,C--數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c語言,筆記,vscode

2. 帶頭雙向循環(huán)鏈表： 結(jié)構(gòu)最復(fù)雜 ，一般用在單獨(dú)存儲數(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ì)帶

來很多優(yōu)勢，實(shí)現(xiàn)反而簡單了，后面我們代碼實(shí)現(xiàn)了就知道了。

?A.帶頭雙向循環(huán)鏈表概念

? ? ? ? 帶頭雙向循環(huán)鏈表（Doubly Circular Linked List with a Head）是一種鏈表數(shù)據(jù)結(jié)構(gòu)，它具有以下特點(diǎn)：

頭節(jié)點(diǎn)：帶頭雙向循環(huán)鏈表包含一個(gè)頭節(jié)點(diǎn)，它位于鏈表的起始位置，并且不存儲實(shí)際數(shù)據(jù)。頭節(jié)點(diǎn)的前驅(qū)指針指向尾節(jié)點(diǎn)，頭節(jié)點(diǎn)的后繼指針指向第一個(gè)實(shí)際數(shù)據(jù)節(jié)點(diǎn)。

循環(huán)連接：尾節(jié)點(diǎn)的后繼指針指向頭節(jié)點(diǎn)，而頭節(jié)點(diǎn)的前驅(qū)指針指向尾節(jié)點(diǎn)，將鏈表形成一個(gè)循環(huán)連接的閉環(huán)。這樣可以使鏈表在遍歷時(shí)可以無限循環(huán)，方便實(shí)現(xiàn)循環(huán)操作。

雙向連接：每個(gè)節(jié)點(diǎn)都有一個(gè)前驅(qū)指針和一個(gè)后繼指針，使得節(jié)點(diǎn)可以向前和向后遍歷。前驅(qū)指針指向前一個(gè)節(jié)點(diǎn)，后繼指針指向后一個(gè)節(jié)點(diǎn)。

????????總結(jié):帶頭雙向循環(huán)鏈表可以支持在鏈表的任意位置進(jìn)行插入和刪除操作，并且可以實(shí)現(xiàn)正向和反向的循環(huán)遍歷。通過循環(huán)連接的特性，鏈表可以在連續(xù)的循環(huán)中遍歷所有節(jié)點(diǎn)，使得鏈表的操作更加靈活和高效。

B.帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

1.帶頭雙向循環(huán)鏈表的結(jié)構(gòu)

typedef int LTDataType;//代碼中將int定義為LTDataType是為了提供代碼的可讀性和可維護(hù)性，并增加代碼的靈活性。

typedef struct ListNode
{
	struct ListNode* next;//存儲下一個(gè)節(jié)點(diǎn)的地址
	struct ListNode* prev;//存儲上一個(gè)節(jié)點(diǎn)的地址
	LTDataType data;
}LTNode;//重新命名結(jié)構(gòu)體類型

通過將int定義為LTDataType，可以在代碼中使用LTDataType作為數(shù)據(jù)類型，而不是直接使用int。這樣做的好處有以下幾點(diǎn)：

可讀性：使用LTDataType作為數(shù)據(jù)類型可以使代碼更具可讀性。LTDataType作為一個(gè)自定義的數(shù)據(jù)類型名稱，可以更好地表達(dá)代碼中數(shù)據(jù)的含義和用途，提高代碼的可理解性。

可維護(hù)性：將int定義為LTDataType可以方便地在代碼中統(tǒng)一修改數(shù)據(jù)類型。如果將來需要將數(shù)據(jù)類型更改為其他類型，只需修改typedef語句中的定義，而不需要在整個(gè)代碼中逐個(gè)修改具體的數(shù)據(jù)類型，減少了修改的工作量和出錯(cuò)的可能性。

靈活性：通過使用LTDataType，可以在代碼中輕松更改數(shù)據(jù)類型，而不會(huì)對代碼的其他部分產(chǎn)生影響。這種抽象化的方式可以使代碼更具通用性，便于在不同的場景中重用。

2.動(dòng)態(tài)申請節(jié)點(diǎn)函數(shù)

函數(shù)代碼:

????????此函數(shù)是關(guān)于一個(gè)結(jié)點(diǎn)動(dòng)態(tài)申請的實(shí)現(xiàn)，包含兩個(gè)指針域，一個(gè)數(shù)據(jù)域。如果分配成功，它會(huì)返回指向該內(nèi)存塊起始位置的指針。你可以使用這個(gè)指針來訪問和操作所分配的內(nèi)存。如果分配失敗，malloc會(huì)返回NULL指針，表示內(nèi)存分配未成功。

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    
    //剛申請下的堆區(qū)空間有可能開辟失敗，所以要進(jìn)行檢查
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

    //開辟好后就賦值
	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;

	return newnode;
}

3.鏈表的初始化

????????鏈表的初始化就是要?jiǎng)?chuàng)建哨兵位的頭節(jié)點(diǎn),此頭節(jié)點(diǎn)不存儲有效數(shù)據(jù)，并且因一開始不知道指向誰，所以根據(jù)雙向鏈表循環(huán)的特性，就讓該結(jié)點(diǎn)的兩個(gè)指針自己指向自己。

//初始化--因?yàn)橐膭?dòng)指向結(jié)構(gòu)體的指針，所以要么就取地址，用二級指針接收。
//要么就像下面這樣，用返回值接收。
LTNode* LTInit()// 由于形參phead是實(shí)參plist的拷貝
{
	LTNode* guard = BuyLTNode(-1);
	guard->next = guard;
	guard->prev = guard;
	
	return guard;
}
int main()
{
    LTNode* plist = LTInit();
}

圖解:

4.鏈表打印

????????打印鏈表就是,遍歷鏈表的每一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域，開始時(shí)用assert斷言傳過來的結(jié)點(diǎn)地址是否為NULL。接著cur用phead->next賦值的原因是，phead傳過來的是哨兵位的頭節(jié)點(diǎn)，它的下一位才是鏈表真正的頭節(jié)點(diǎn)（有數(shù)據(jù)域），接著遍歷鏈表，當(dāng)cur指針回到哨兵位時(shí)，遍歷結(jié)束。

圖解:

函數(shù)代碼:?

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

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

5.鏈表尾部插入節(jié)點(diǎn)

與單鏈表有兩個(gè)不一樣的點(diǎn):

情況一:

1.單鏈表尾插結(jié)點(diǎn)需要遍歷全鏈表，當(dāng)指針走到鏈表最后一個(gè)結(jié)點(diǎn)的時(shí)候，判斷tail->next是否為NULL，若為NULL，則跳出遍歷的循環(huán)，尾插新結(jié)點(diǎn)。然而帶頭雙向循環(huán)鏈表不需要遍歷鏈表，只需要對哨兵位的頭節(jié)點(diǎn)的prev域解引用，直接找到帶頭雙向循環(huán)鏈表的尾節(jié)點(diǎn)，尾插新節(jié)點(diǎn)。

情況二:

2.頭指針的區(qū)別:帶頭雙向循環(huán)鏈表不需要判斷頭指針是否指向NULL，因?yàn)樯诒坏念^節(jié)點(diǎn)也是有它的地址的,添加新節(jié)點(diǎn)時(shí)只需要直接在尾節(jié)點(diǎn)尾插。然而單鏈表卻需要判斷頭指針是否指向NULL，而且需要用到二級指針，比較棘手。

函數(shù)代碼:?

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	
	LTNode* tail = phead->prev;//通過哨兵位的頭節(jié)點(diǎn)的prev找到鏈表最后一個(gè)結(jié)點(diǎn)，并用tail指向
	LTNode* newnode = BuyLTNode(x);
	
	tail->next= newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

測試案例:

????????知識點(diǎn):要改變一個(gè)變量的值，特別是傳參傳過去的，一定要注意是傳值還是傳址。如果是傳值調(diào)用，那么傳過去的函數(shù)(自定義的函數(shù))參數(shù)就是形參，不會(huì)改變實(shí)參(main函數(shù)里面的就是實(shí)參)。如果傳址調(diào)用，一般是取這個(gè)變量的地址，函數(shù)那邊要用二級指針接收，并且函數(shù)(自定義函數(shù))里面要有一層解引用，才能操作實(shí)參的值，給實(shí)參賦值，或者其它改變實(shí)參的操作。

????????malloc如果分配成功，它會(huì)返回指向該內(nèi)存塊起始位置的指針，意味著返回的是在堆上分配指定大小的內(nèi)存塊的地址，相等于取出內(nèi)存塊的地址，然后用一級指針接收，傳一級指針過去，然后用結(jié)構(gòu)體指針訪問結(jié)構(gòu)體成員的方式改變節(jié)點(diǎn)的值。

//初始化和尾插
void TestList1()
{
	LTNode* plist = LTInit();//相等于取出內(nèi)存塊的地址，然后用一級指針接收，傳一級指針過去，然后            
                               用結(jié)構(gòu)體指針訪問結(jié)構(gòu)體成員的方式改變節(jié)點(diǎn)的值。
    LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
}
int main()
{
	TestList1();
}

實(shí)現(xiàn)思路:依舊是數(shù)字代表順序

?代碼執(zhí)行：

6.鏈表頭部插入節(jié)點(diǎn)

請先看錯(cuò)誤操作，請多注意！:

正確方法:

方法1：無需創(chuàng)建變量

圖上的數(shù)字代表順序

?代碼實(shí)現(xiàn):

//方法一,不需要?jiǎng)?chuàng)建變量
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);

	newnode->next = phead->next;//把頭結(jié)點(diǎn)后面的d1的地址賦值給新結(jié)點(diǎn)的next
	phead->next->prev = newnode;//d1指向新節(jié)點(diǎn)
	
	phead->next = newnode;//改變頭節(jié)點(diǎn)的next，讓它指向新結(jié)點(diǎn)
	newnode->prev = phead;//新結(jié)點(diǎn)的prev指向phead頭插完畢.
}

方法2：創(chuàng)建變量first

圖上的數(shù)字代表順序

?代碼實(shí)現(xiàn):

//方法二創(chuàng)建一個(gè)first變量
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;

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

}

代碼執(zhí)行:

7.鏈表尾刪節(jié)點(diǎn)?

圖解:

當(dāng)鏈表不止一個(gè)節(jié)點(diǎn)時(shí):

?當(dāng)鏈表只有一個(gè)節(jié)點(diǎn)（哨兵位不算）時(shí):

若鏈表為NULL(只剩哨兵位就是鏈表為NULL)時(shí)，再尾刪就會(huì)出錯(cuò)

檢查鏈表是否為空,進(jìn)行函數(shù)封裝:

bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

函數(shù)解析:?

? ? ? ? LTEmpty(LTNode* phead)是一個(gè)函數(shù)調(diào)用，它將鏈表頭節(jié)點(diǎn)phead作為參數(shù)傳遞給LTEmpty函數(shù)。LTEmpty函數(shù)的作用是判斷循環(huán)鏈表是否為空，如果為空則返回true，否則返回false。

? ? ? ?如果LTEmpty(phead)返回true，即鏈表為空，那么!LTEmpty(phead)將為false。如果LTEmpty(phead)返回false，即鏈表不為空，那么?!LTEmpty(phead)將為true

? ? ? ? assert 宏用于在運(yùn)行時(shí)進(jìn)行斷言檢查。它接受一個(gè)表達(dá)式作為參數(shù)，如果表達(dá)式的結(jié)果為false,則會(huì)觸發(fā)斷言失敗，程序可能會(huì)終止執(zhí)行。如果表達(dá)式的結(jié)果為true，則斷言通過，程序繼續(xù)執(zhí)行。

//尾刪
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail= phead->prev;
	LTNode* tailPrev=tail->prev ;
	
	free(tail);	//先刪除再鏈接
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

代碼執(zhí)行:
【數(shù)據(jù)結(jié)構(gòu)】帶頭雙向循環(huán)鏈表（小白入門必備知識）,C--數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c語言,筆記,vscode

8.鏈表頭刪節(jié)點(diǎn)

鏈表不止一個(gè)結(jié)點(diǎn)時(shí):

圖解:

數(shù)字代表順序

鏈表為一個(gè)結(jié)點(diǎn)時(shí):

數(shù)字代表順序

函數(shù)代碼:?

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* first = phead->next;
	LTNode* second = first->next;

	phead->next = second;
	second->prev = phead;  
	free(first);
}

代碼執(zhí)行:

9.鏈表查找/修改某個(gè)值


LTNode* STFind(LTNode* phead, LTDataType x)
{
	//assert(phead);
	LTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
		if (cur->data == phead->data)//若重新回到哨兵位，則說明鏈表遍歷完畢，找不到x值，返回NULL
		{
			break;
		}
	}
	return NULL;
}

?代碼執(zhí)行:

找到了:

?找不到:

10.在鏈表pos位置之前插入值

圖解:

【數(shù)據(jù)結(jié)構(gòu)】帶頭雙向循環(huán)鏈表（小白入門必備知識）,C--數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c語言,筆記,vscode ?

void LTInsert(LTNode* pos,LTDataType x)//輸入要?jiǎng)h除的數(shù)的位置即可
{
	assert(pos);

	LTNode* newnode = BuyLTNode(x);
	LTNode* prev = pos->prev;

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

代碼執(zhí)行:?

LTInsert實(shí)現(xiàn)尾插操作:

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead, x);
}

LTInsert實(shí)現(xiàn)頭插操作:

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead->next);
	LTInsert(phead->next, x);
}

11.在鏈表pos位置處刪除此節(jié)點(diǎn)

void LTErase(LTNode* pos)
{
	assert(pos);
	
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	 
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

代碼執(zhí)行:?

LTErase實(shí)現(xiàn)尾刪:

//LTPopBack鏈表尾刪
void LTPopBack(LTNode* phead)
{
	assert(phead);
	
    assert(!LTEmpty(phead));
	LTErase(phead->prev);


}

LTErase實(shí)現(xiàn)頭刪

//LTPopFront鏈表頭刪
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->next);

}

12.求鏈表的長度函數(shù)

簡單來說就是計(jì)算鏈表的結(jié)點(diǎn)個(gè)數(shù)

void TestList8()//求鏈表長度
{
	LTNode* plist = LTInit();
	size_t count = LTSize(plist);
	printf("當(dāng)前鏈表長度為:%zu\n", count);
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	
	count = LTSize(plist);
	printf("當(dāng)前鏈表長度為%zu", count);
}

代碼執(zhí)行：

13.釋放鏈表動(dòng)態(tài)申請的空間

函數(shù)代碼:

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

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

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//初始化和尾插
void TestList1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
}
//頭插
void TestList2()
{
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);

}
//尾刪
void TestList3()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);
}
//頭刪
void TestList4()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);
}
void TestList5()//查找/修改
{
	LTNode* plist = LTInit();
	printf("尾插:");
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	printf("請輸入你要找的值:");
	int n = 0;
	scanf("%d", &n);
	LTNode* find = STFind(plist,n);
	if (find)
	{
		printf("找到了\n");
		find->data = 300;
		printf("修改節(jié)點(diǎn)的值成功\n");
		LTPrint(plist);
	} 
	else
	{
		printf("沒找到\n");
	}
}
void TestList6()//pos之前插入值
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTNode* pos = STFind(plist, 3);
	if (pos)
	{
		LTInsert( pos, 30);
	}
	LTPrint(plist);
}
void TestList7()//刪除pos位置的值
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTNode* pos = STFind(plist, 3);
	if (pos)
	{
		LTErase(pos);
	}
	LTPrint(plist);
}
void TestList8()//求鏈表長度
{
	LTNode* plist = LTInit();
	size_t count = LTSize(plist);
	printf("當(dāng)前鏈表長度為:%zu\n", count);
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	
	count = LTSize(plist);
	printf("當(dāng)前鏈表長度為%zu", count);
}

int main()
{
	//TestList1();//初始化和尾插
	TestList2();//頭插
	//TestList3();//尾刪
	//TestList4();//頭刪
	//TestList5();//查找、修改
	//TestList6();pos之前插入值
	//TestList7();//刪除pos位置的值
	//TestList8();//求鏈表長度
}

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

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

LTNode*LTInit();
void LTPrint(LTNode* phead);
//判斷鏈表是否為NULL
bool LTEmpty(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead,LTDataType x);
//頭插
void LTPushFront(LTNode* phead, LTDataType x);
//尾刪
void LTPopBack(LTNode* phead);
//查找
LTNode* STFind(LTNode* phead, LTDataType x);
//頭刪
void LTPopFront(LTNode* phead);
//pos之前插入
void LTInsert(LTNode* pos, LTDataType x);

//計(jì)算鏈表節(jié)點(diǎn)個(gè)數(shù)
size_t LTSize(LTNode* phead);
//釋放鏈表
void LTErase(LTNode* pos);

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));

	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;

	return newnode;
}

LTNode* LTInit()
{
	LTNode* guard = BuyLTNode(-1);
	guard->next = guard;
	guard->prev = guard;
	
	return guard;
}

//打印
void LTPrint(LTNode* phead)
{
	assert(phead);

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

bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

//尾插
//void LTPushBack(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	
//	LTNode* tail = phead->prev;
//	LTNode* newnode = BuyLTNode(x);
//	
//	tail->next= newnode;
//	newnode->prev = tail;
//	newnode->next = phead;
//	phead->prev = newnode;
//}


//頭插
//方法一,不需要?jiǎng)?chuàng)建變量
//void LTPushFront(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTNode* newnode = BuyLTNode(x);
//
//	newnode->next = phead->next;//把頭結(jié)點(diǎn)后面的d1的地址賦值給新結(jié)點(diǎn)的next
//	phead->next->prev = newnode;//d1指向新節(jié)點(diǎn)
//	
//	phead->next = newnode;//改變頭節(jié)點(diǎn)的next，讓它指向新結(jié)點(diǎn)
//	newnode->prev = phead;//新結(jié)點(diǎn)的prev指向phead頭插完畢.
//}
//方法二創(chuàng)建一個(gè)first變量
//void LTPushFront(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTNode* newnode = BuyLTNode(x);
//	LTNode* first = phead->next;
//
//	phead->next = newnode;
//	newnode->next = first;
//	newnode->prev = phead;
//	first->prev = newnode;
//
//}
//尾刪
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail= phead->prev;
	LTNode* tailPrev=tail->prev ;
	
	free(tail);	//先刪除再鏈接

	tailPrev->next = phead;
	phead->prev = tailPrev;
}

LTNode* STFind(LTNode* phead, LTDataType x)
{
	//assert(phead);
	LTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
		if (cur->data == phead->data)
		{
			break;
		}
	}
	return NULL;
}



//頭刪
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* first = phead->next;
	LTNode* second = phead->next->next;

	phead->next = second;
	second->prev = phead;  
	free(first);
}


void LTInsert(LTNode* pos,LTDataType x)//輸入要?jiǎng)h除的數(shù)的位置即可
{
	assert(pos);

	LTNode* newnode = BuyLTNode(x);
	LTNode* prev = pos->prev;

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

//INsert尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead, x);
}

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead->next);
	LTInsert(phead->next, x);
}



void LTErase(LTNode* pos)
{
	assert(pos);
	
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	 
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}
//LTPopBack鏈表尾刪
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->prev);

	

}
//LTPopFront鏈表頭刪
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->next);

}

size_t LTSize(LTNode* phead)
{
	assert(phead);
	size_t n = 0; 
	LTNode * cur = phead->next;
	while (cur!=phead)
	{
		n++;
		cur = cur->next;
	}
	return n;
}


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

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

? ? ? ? 本篇完畢，如有錯(cuò)誤，歡迎大佬指正！?文章來源地址http://www.zghlxwxcb.cn/news/detail-661669.html

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