C語言如何實(shí)現(xiàn)帶頭雙向循環(huán)鏈表

這篇文章主要介紹了C語言如何實(shí)現(xiàn)帶頭雙向循環(huán)鏈表，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

前言

在實(shí)際生活中最常用的就是這兩種鏈表。無頭單向非循環(huán)鏈表。和帶頭雙向循環(huán)鏈表。
無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會(huì)單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
帶頭雙向循環(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ì)帶來很多優(yōu)勢，實(shí)現(xiàn)反而簡單了，后面我們代碼實(shí)現(xiàn)了就知道了。

1. 創(chuàng)建結(jié)構(gòu)體

注意：typedef起作用是在第7行哦。所以第5,6還需要寫struct ListNode類型。

typedef int LNDataType;

typedef struct ListNode
{
	  struct ListNode* prev;
 	  struct ListNode* next;
      LNDataType val;
}LN;

2.malloc新節(jié)點(diǎn)

注意：需判斷新開辟的節(jié)點(diǎn)是否為空。

//申請(qǐng)一個(gè)新節(jié)點(diǎn)
LN* BuynewNode(LNDataType x)
{
	LN* newNode = (LN*)malloc(sizeof(LN));
	if (newNode == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}
	newNode->next = NULL;
	newNode->prev = NULL;
	newNode->val = x;
	return newNode;
}

3.創(chuàng)建哨兵位節(jié)點(diǎn)

注意：這里因?yàn)樾枰淖僷list指針的內(nèi)容，也就是改變plist指針的指向，所以需要傳遞plist的地址。

一句話就是：需要改變誰的內(nèi)容，就傳誰的地址。

這里有一點(diǎn)非常巧非常妙，就是phead的后繼和前驅(qū)都是指向自己（phead），這里是模仿C++STL庫里的哨兵位節(jié)點(diǎn)。

只能佩服想出來這些東西的大神。這樣設(shè)計(jì)哨兵位節(jié)點(diǎn)的話，后續(xù)尾插，尾刪，都特別的巧妙。

test.c

	LN* plist = NULL;
	ListNodeInit(&plist);

List.h

//初始化節(jié)點(diǎn)
void ListNodeInit(LN** pphead)
{
	LN* newNode = BuynewNode(0);
	*pphead = newNode;
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
}

4.尾插

注意：需要斷言的原因是因?yàn)?，即使鏈表沒有一個(gè)節(jié)點(diǎn)，那鏈表至少還有個(gè)頭，所以phead肯定不為空。

這里沒有傳地址的原因是因?yàn)椋悴恍枰淖僷list的指向，你改變的是plist指向的結(jié)構(gòu)體里面的值。

多個(gè)節(jié)點(diǎn)尾插的情況如圖。

一個(gè)節(jié)點(diǎn)的尾插。

//尾插
void ListNodePushBack(LN* phead, LNDataType x)
{
	assert(phead);
	LN* newNode = BuynewNode(x);
	LN* tail = phead->prev;
	tail->next = newNode;
	newNode->prev = tail;
	newNode->next = phead;
	phead->prev = newNode;
}

5.打印

注意：因?yàn)閹€(gè)頭，所以cur從第二個(gè)位置開始。

//打印
void ListNodePrint(LN* phead)
{
	LN* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

6.尾刪

注意不能刪掉頭結(jié)點(diǎn)，free掉頭結(jié)點(diǎn)的話會(huì)造成野指針，再次訪問時(shí)會(huì)造成非法訪問。
所以要用assert斷言不為首節(jié)點(diǎn)。

//尾刪
void ListNodePopBack(LN* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LN* tail = phead->prev;
	LN* tailPrev = tail->prev;
	free(tail);
	tail = NULL;
	phead->prev = tailPrev;
	tailPrev->next = phead;
}

7.頭插

最好用next記錄下一個(gè)節(jié)點(diǎn)。這樣方便，思路清晰

//頭插
void ListNodePushFront(LN* phead, LNDataType x)
{
	assert(phead);
	LN* newNode = BuynewNode(x);
	LN* next = phead->next;
	phead->next = newNode;
	newNode->prev = phead;
	newNode->next = next;
	next->prev = newNode;
}

8.在指定位置pos的前面進(jìn)行插入

一般情況

只有一個(gè)節(jié)點(diǎn)時(shí)。

兩種情況都適用以下代碼。

//指定位置前插入，極限是頭插
void ListNodeInsert(LN* pos, LNDataType x)
{
	if (pos == NULL)
	{
		printf("沒有找到這個(gè)數(shù)\n");
		return;
	}
	LN* newNode = BuynewNode(x);
	LN* tailPrev = pos->prev;
	tailPrev->next = newNode;
	newNode->prev = tailPrev;
	newNode->next = pos;
	pos->prev = newNode;
}

9. 刪除指定位置pos節(jié)點(diǎn)

正常情況

極限尾刪

兩種情況都適用以下代碼。

//指定位置刪除
void ListNodeErease(LN* phead, LN* pos)
{
	if (pos == phead || pos == NULL)
	{
		printf("pos指向頭，或?yàn)榭誠n");
		return;
	}
	LN* posPrev = pos->prev;
	LN* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
	pos = NULL;
}

10.銷毀鏈表

注意：這里相當(dāng)于malloc用完之后的free。否則會(huì)造成內(nèi)存泄漏。
cur可以置空，但用處不大，因?yàn)閏ur是形參，形參是實(shí)參的一份臨時(shí)拷貝，形參置空并不能改變實(shí)參。外部的實(shí)參還是依舊能非法訪問到cur所指向的空間。

//鏈表銷毀
void ListNodeDestroy(LN* phead)
{
	assert(phead);
	LN* cur = phead->next;
	LN* next = cur->next;
	while (cur != phead)
	{
		next = cur->next;
		free(cur);
		cur = NULL;
		cur = next;
	}
	free(phead);
	phead = NULL;
}

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“C語言如何實(shí)現(xiàn)帶頭雙向循環(huán)鏈表”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來學(xué)習(xí)!