腳本之家服務器常用軟件

快捷導航

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

更新時間：2022年03月28日 08:57:19 作者：_奇奇

本文主要介紹了C語言實現(xiàn)帶頭雙向循環(huán)鏈表，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

前言

在這里插入圖片描述

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

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

//申請一個新節(jié)點
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é)點

注意：這里因為需要改變plist指針的內(nèi)容，也就是改變plist指針的指向，所以需要傳遞plist的地址。

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

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

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

在這里插入圖片描述

test.c

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

List.h

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

4.尾插

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

這里沒有傳地址的原因是因為，你不需要改變plist的指向，你改變的是plist指向的結(jié)構(gòu)體里面的值。

多個節(jié)點尾插的情況如圖。

在這里插入圖片描述

一個節(jié)點的尾插。

在這里插入圖片描述

//尾插
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.打印

注意：因為帶個頭，所以cur從第二個位置開始。

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

6.尾刪

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

//尾刪
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記錄下一個節(jié)點。這樣方便，思路清晰

//頭插
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的前面進行插入

一般情況

在這里插入圖片描述

只有一個節(jié)點時。

在這里插入圖片描述

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

//指定位置前插入，極限是頭插
void ListNodeInsert(LN* pos, LNDataType x)
{
	if (pos == NULL)
	{
		printf("沒有找到這個數(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é)點

正常情況

在這里插入圖片描述

極限尾刪

在這里插入圖片描述

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

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

10.銷毀鏈表

注意：這里相當于malloc用完之后的free。否則會造成內(nèi)存泄漏。
cur可以置空，但用處不大，因為cur是形參，形參是實參的一份臨時拷貝，形參置空并不能改變實參。外部的實參還是依舊能非法訪問到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;
}

到此這篇關(guān)于C語言實現(xiàn)帶頭雙向循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C語言帶頭雙向循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: