? ?
??博客昵稱：博客小夢(mèng)
??最喜歡的座右銘：全神貫注的上吧！?。?br> ??作者簡(jiǎn)介：一名熱愛C/C++，算法等技術(shù)、喜愛運(yùn)動(dòng)、熱愛K歌、敢于追夢(mèng)的小博主！
??博主小留言：哈嘍！??各位CSDN的uu們，我是你的博客好友小夢(mèng)，希望我的文章可以給您帶來(lái)一定的幫助，話不多說(shuō)，文章推上！歡迎大家在評(píng)論區(qū)嘮嗑指正，覺得好的話別忘了一鍵三連哦！??

前言??

? ? 哈嘍各位友友們??，我今天又學(xué)到了很多有趣的知識(shí)，現(xiàn)在迫不及待的想和大家分享一下！??我僅已此文，手把手帶領(lǐng)大家學(xué)習(xí)C語(yǔ)言動(dòng)態(tài)實(shí)現(xiàn)實(shí)現(xiàn)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表結(jié)構(gòu)~ 用代碼來(lái)實(shí)現(xiàn)一個(gè)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表結(jié)構(gòu)，完成增刪查改，順序輸出和逆序輸出，判空的功能。都是精華內(nèi)容，可不要錯(cuò)過(guò)喲?。?！??????

預(yù)備小知識(shí)??

鏈表的概念及結(jié)構(gòu)??

鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈
接次序?qū)崿F(xiàn)的 。

預(yù)備小知識(shí)??

鏈表的概念及結(jié)構(gòu)??

鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈
接次序?qū)崿F(xiàn)的 。

帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表結(jié)構(gòu)??

帶頭雙向循環(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)單了

整體實(shí)現(xiàn)內(nèi)容分析??

首先在頭文件先定義結(jié)構(gòu)體和各個(gè)功能函數(shù)的聲明，并把有關(guān)的頭文件包含上去。各個(gè)函數(shù)如何實(shí)現(xiàn)的，已在實(shí)驗(yàn)步驟描述清楚，這里就不在贅述了，主要是對(duì)各個(gè)函數(shù)的實(shí)現(xiàn)，用到malloc動(dòng)態(tài)開辟新節(jié)點(diǎn)的空間，用assert斷言確保指針有效，通過(guò)畫圖來(lái)幫助理清代碼實(shí)現(xiàn)的思路，指針的指向如何，要考慮哪些情況。然后再測(cè)試代碼中，將上述代碼都進(jìn)行測(cè)試，顯示結(jié)果。

1.頭文件編碼實(shí)現(xiàn)??

1、	
2、	#pragma once
3、	#include <stdio.h>
4、	#include <stdlib.h>
5、	#include <assert.h>
6、	#include <stdbool.h>
7、	
8、	typedef int LTDataType;
9、	// 帶頭雙向循環(huán)鏈表結(jié)構(gòu)體
10、	typedef struct ListNode
11、	{
12、		struct ListNode* next;
13、		struct ListNode* prev;
14、		LTDataType data;
15、	}ListNode;
16、	ListNode* ListInit();//鏈表初始化
17、	void ListDestory(ListNode* phead);//刪除鏈表
18、	void ListPrintFront(ListNode* phead);//鏈表順序輸出
19、	void ListPrintBack(ListNode* phead);//鏈表逆序輸出
20、	void ListPushBack(ListNode* phead, LTDataType x);//尾插
21、	void ListPushFront(ListNode* phead, LTDataType x);//頭插
22、	void ListPopFront(ListNode* phead);//頭刪
23、	void ListPopBack(ListNode* phead);//尾刪
24、	ListNode* ListFind(ListNode* phead, LTDataType x);//查找
25、	void ListInsert(ListNode* pos, LTDataType x);// pos位置之前插入x
26、	void ListErase(ListNode* pos);// 刪除pos位置的值
27、	bool ListEmpty(ListNode* phead);判空函數(shù)

2.代碼功能實(shí)現(xiàn)??

1）這是生成新節(jié)點(diǎn)函數(shù)實(shí)現(xiàn)。??

代碼實(shí)現(xiàn)思路詳解：

//用malloc動(dòng)態(tài)開辟新節(jié)點(diǎn)的空間，把數(shù)值賦值給新節(jié)點(diǎn)
//,newnode的next和prev指針指向空。

ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

2)生成帶頭結(jié)點(diǎn)的空鏈表函數(shù)實(shí)現(xiàn)。??

代碼實(shí)現(xiàn)思路詳解：

//2)生成帶頭結(jié)點(diǎn)的空鏈表，將頭結(jié)點(diǎn)的指針都指向自己即可。

ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

3)刪除鏈表函數(shù)實(shí)現(xiàn)。??

代碼實(shí)現(xiàn)思路詳解：

//3)先用assert斷言以下確保phead指針不為空，生成cur指針先指向第一個(gè)結(jié)點(diǎn)位置。用while循環(huán)執(zhí)行刪表：在定義一個(gè)next指針指向cur的下一個(gè)結(jié)點(diǎn)，free掉cur指向的結(jié)點(diǎn)，cur移動(dòng)到next位置。最后刪除頭結(jié)點(diǎn)即可
//

void ListDestory(ListNode* phead)//刪除鏈表
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	phead = NULL;
}

4)順序輸出鏈表函數(shù)實(shí)現(xiàn)。??

代碼實(shí)現(xiàn)思路詳解：

//4)順序輸出鏈表。先assert斷言確保指針有效。定義一個(gè)指向鏈表首結(jié)點(diǎn)的指針，打印完一個(gè)，cur到下一個(gè)節(jié)點(diǎn)知道cur回到phead為止。

void ListPrintFront(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

5)尾插函數(shù)實(shí)現(xiàn)。??

代碼實(shí)現(xiàn)思路詳解：

//5）尾插函數(shù)。先assert確保指針有效性，定義tail指針指向最后一個(gè)節(jié)點(diǎn)，然后生成新節(jié)點(diǎn)然后通過(guò)指針將tail指向的節(jié)點(diǎn)與新生成的節(jié)點(diǎn)相連，新生成的節(jié)點(diǎn)與哨兵位頭結(jié)點(diǎn)相連

void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);

	ListNode* tail = phead->prev;
	ListNode* newnode = BuyListNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

6）頭插函數(shù)實(shí)現(xiàn)。??

代碼實(shí)現(xiàn)思路詳解：

//6）頭插函數(shù)實(shí)現(xiàn)。先assert斷言一下確保傳入進(jìn)來(lái)的指針有效。定義一個(gè)指向首節(jié)點(diǎn)的指針然后生成一個(gè)新節(jié)點(diǎn)，讓新節(jié)點(diǎn)與頭結(jié)點(diǎn)相連，讓新節(jié)點(diǎn)的next指針指向原來(lái)首節(jié)點(diǎn)，原來(lái)首節(jié)點(diǎn)的prev指向新節(jié)點(diǎn)讓新節(jié)點(diǎn)位于原來(lái)首節(jié)點(diǎn)的前面從而實(shí)現(xiàn)頭插。

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);

	ListNode* first = phead->next;
	ListNode* newnode = BuyListNode(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

7）頭刪函數(shù)實(shí)現(xiàn)。??

代碼實(shí)現(xiàn)思路詳解：

//7）頭刪函數(shù)實(shí)現(xiàn)。assert確保傳入指針有效和確保頭結(jié)點(diǎn)不要被刪掉。定義first指針指向鏈表首節(jié)點(diǎn)，second指向first下一個(gè)。然后讓頭結(jié)點(diǎn)與second指針指向的節(jié)點(diǎn)相連，然后free掉first指向的節(jié)點(diǎn)。

void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* first = phead->next;
	ListNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
    first = NULL;

	
}

8）尾刪函數(shù)的實(shí)現(xiàn)。??

代碼實(shí)現(xiàn)思路詳解：

//8）尾刪函數(shù)的實(shí)現(xiàn)。頭刪函數(shù)實(shí)現(xiàn)。assert確保傳入指針有效和確保頭結(jié)點(diǎn)不要被刪掉。定義tail函數(shù)指向尾節(jié)點(diǎn)，定義prev指針指向tail的前一個(gè)節(jié)點(diǎn)，讓prev指向的那個(gè)節(jié)點(diǎn)與頭結(jié)點(diǎn)相連，然后刪掉tail指向的尾節(jié)點(diǎn)，實(shí)現(xiàn)尾刪。

void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;

	prev->next = phead;
	phead->prev = prev;

	free(tail);
	tail = NULL;

}

9）查找函數(shù)實(shí)現(xiàn)。??

代碼實(shí)現(xiàn)思路詳解：

//9）查找函數(shù)，先assert斷言確保傳入指針有效性，定義一個(gè)cur指向首節(jié)點(diǎn)，然后利用while遍歷鏈表，找到的話就返回指針。找不到則返回空。

ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}

10）pos位置之前插入x的函數(shù)實(shí)現(xiàn)。??

代碼實(shí)現(xiàn)思路詳解：

// 10）pos位置之前插入x。定義一個(gè)prev指針指向pos指向的前一個(gè)節(jié)點(diǎn)，然后新生成一個(gè)節(jié)點(diǎn)，通過(guò)指針相連方式將新生成的節(jié)點(diǎn)放到pos與prev的中間。

void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);

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

11）刪除pos位置的值的函數(shù)實(shí)現(xiàn)。??

代碼實(shí)現(xiàn)思路詳解：

// 11）刪除pos位置的值。定義一個(gè)prev指針指向pos前一個(gè)節(jié)點(diǎn)，定義一個(gè)next指向pos后一個(gè)節(jié)點(diǎn)，然后讓這兩個(gè)節(jié)點(diǎn)相連，刪掉pos指向的節(jié)點(diǎn)。

void ListErase(ListNode* pos)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}

12）逆序輸出的函數(shù)實(shí)現(xiàn)。??

代碼實(shí)現(xiàn)思路詳解：

//12)逆序輸出函數(shù)實(shí)現(xiàn)。定義一個(gè)phead指針指向尾節(jié)點(diǎn)，從后往前遍歷鏈表，直到cur走到頭結(jié)點(diǎn)為止。

void ListPrintBack(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->prev;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->prev;
	}
	printf("\n");
}

13）判空函數(shù)實(shí)現(xiàn)。??

代碼實(shí)現(xiàn)思路詳解：

//13）判空函數(shù)實(shí)現(xiàn)，只要phead的前指針指向自己，則認(rèn)為這鏈表為空鏈表。

bool ListEmpty(ListNode* phead)
{
	assert(phead);
	if (phead->prev == phead)
	{
		return 1;
	}
	return -1;

3.測(cè)試文件源碼分享：??

#include "SlistNode.h"

void TestList1()
{
	//創(chuàng)建帶頭節(jié)點(diǎn)的空雙向鏈表
	ListNode* plist = ListInit();
	//判空
	int ret = ListEmpty(plist);
	if (ret == 1)
	{
		printf("鏈表為空\(chéng)n");
	}
	else
	{
		printf("鏈表不為空\(chéng)n");
	}

	//尾插1,2,3,4,5
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPrintFront(plist);
	//頭插0,-1
	ListPushFront(plist, 0);
	ListPushFront(plist, -1);
	ListPrintFront(plist);
	//頭刪三個(gè)數(shù)據(jù)
	ListPopFront(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrintFront(plist);
	//尾刪一個(gè)數(shù)據(jù)
	ListPopBack(plist);
	ListPrintFront(plist);
	//判空
	int ret1 = ListEmpty(plist);
	if (ret1 == 1)
	{
		printf("鏈表不為空\(chéng)n");
	}
	else
	{
		printf("鏈表為空\(chéng)n");
	}
	// 查找，附帶著修改的作用
	ListNode* pos = ListFind(plist, 3);
	if (pos)
	{
		pos->data *= 10;
		printf("找到了，并且節(jié)點(diǎn)的值乘以10\n");
	}
	else
	{
		printf("沒有找到\n");
	}
	ListPrintFront(plist);
	//在pos前插入一個(gè)300
	ListInsert(pos, 300);
	ListPrintFront(plist);
	//刪除pos位置的節(jié)點(diǎn)
	ListErase(pos);
	//順序輸出鏈表數(shù)據(jù)
	ListPrintFront(plist);
	//逆序輸出鏈表數(shù)據(jù)
	ListPrintBack(plist);
//刪除鏈表
	ListDestory(plist);

}

int main()
{
	TestList1();

	return 0;
}

程序功能測(cè)試結(jié)果圖：

總結(jié)撒花??

? ?本篇文章旨在分享詳解C語(yǔ)言動(dòng)態(tài)實(shí)現(xiàn)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表結(jié)構(gòu)。希望大家通過(guò)閱讀此文有所收獲！實(shí)現(xiàn)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表結(jié)構(gòu)，相比于單鏈表結(jié)構(gòu)更加復(fù)雜一點(diǎn)，它的成員相比單鏈表多了一個(gè)指針。本次實(shí)現(xiàn)難點(diǎn)在于對(duì)指針的運(yùn)用和對(duì)多種情況的考慮。在實(shí)現(xiàn)前一定要通過(guò)畫圖的方式將思路和需要注意的情況想清楚然后再來(lái)嘗試用代碼進(jìn)行實(shí)現(xiàn)。基本實(shí)現(xiàn)出雙鏈表后可以思考能不能優(yōu)化代碼的問題。
? ???如果我寫的有什么不好之處，請(qǐng)?jiān)谖恼孪路浇o出你寶貴的意見??。如果覺得我寫的好的話請(qǐng)點(diǎn)個(gè)贊贊和關(guān)注哦~??????文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-797186.html

到了這里，關(guān)于追夢(mèng)之旅【數(shù)據(jù)結(jié)構(gòu)篇】——詳解C語(yǔ)言動(dòng)態(tài)實(shí)現(xiàn)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！