欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間:2022年04月23日 11:52:31   作者:風(fēng)&646  
帶頭雙向循環(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)反而簡單

創(chuàng)建鏈表存儲(chǔ)結(jié)構(gòu)

我們需要?jiǎng)?chuàng)建一個(gè)結(jié)構(gòu)體來存儲(chǔ)一個(gè)鏈表結(jié)點(diǎn)的相關(guān)信息。

typedef int ListDataType;//將ListDataType先定義為int類型,根據(jù)需要可以改為不同的類型
//創(chuàng)建一個(gè)鏈表的結(jié)構(gòu)體
typedef struct ListNode
{
	ListDataType data;//存儲(chǔ)數(shù)據(jù)
	struct ListNode* next;//存儲(chǔ)下一個(gè)結(jié)點(diǎn)的地址的指針
	struct ListNode* prev;//存儲(chǔ)上一個(gè)結(jié)點(diǎn)的地址的指針
}ListNode;

創(chuàng)建結(jié)點(diǎn)

我們每次增加數(shù)據(jù)都要?jiǎng)?chuàng)建一個(gè)新的結(jié)點(diǎn),但每次都創(chuàng)建就會(huì)非常的麻煩。所以我們考慮把創(chuàng)建一個(gè)結(jié)點(diǎn)這個(gè)功能封裝成一個(gè)函數(shù),每次要使用只要調(diào)用一下就可以了。

ListNode* BuyListNode(ListDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//向內(nèi)存申請一個(gè)新的結(jié)點(diǎn)
	if (newnode == NULL)
	{
		printf("BuyListNode::%s\n", strerror(errno));//打印結(jié)點(diǎn)空間申請失敗的原因
		exit(-1);//終止程序
	}
	newnode->data = x;//將x放入申請的結(jié)點(diǎn)數(shù)據(jù)區(qū)
	newnode->next = NULL;//讓新結(jié)點(diǎn)的next指向空
	newnode->prev = NULL;//讓新結(jié)點(diǎn)的prev指向空
	return newnode;//返回新結(jié)點(diǎn)的地址
}

鏈表的初始化

帶頭雙向循環(huán)鏈表我們對其初始化就是申請一個(gè)帶哨兵位的頭結(jié)點(diǎn)。接下來我們看初始化的兩種方法。

void ListInit(ListNode** pphead)//這里我們需要對頭結(jié)點(diǎn)進(jìn)行改變,所以傳二級指針
{
	assert(pphead);//檢測傳過來的pphead的地址是否為空
	*pphead = BuyListNode(0);//創(chuàng)建一個(gè)新的哨兵位頭結(jié)點(diǎn)
	(*pphead)->next = *pphead;//讓這個(gè)結(jié)點(diǎn)指向自己
	(*pphead)->prev = *pphead;
}
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);//創(chuàng)建一個(gè)新的哨兵位頭結(jié)點(diǎn)
	phead->next = phead;//讓這個(gè)結(jié)點(diǎn)的next指向自己
	phead->prev = phead;//讓prev指向自己
	return phead;//返回哨兵位頭結(jié)點(diǎn)的地址
}

雙向鏈表的打印

我們才用遍歷鏈表的方式來打印鏈表中的數(shù)據(jù)。

void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;//讓cur指向哨兵位的下一個(gè)結(jié)點(diǎn)
	while (cur != phead)//鏈表打印是否結(jié)束的條件判斷
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

雙向鏈表尾插

雙向循環(huán)鏈表結(jié)構(gòu)比較優(yōu),所以很方便找到尾結(jié)點(diǎn)。尾結(jié)點(diǎn)就是哨兵位結(jié)點(diǎn)prev指向的結(jié)點(diǎn)。

void ListPushBack(ListNode* phead, ListDataType x)
{
	assert(phead);//檢查傳過來的頭結(jié)點(diǎn)是否為空
	ListNode* tail = phead->prev;//找到鏈表的尾結(jié)點(diǎn)
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新的結(jié)點(diǎn)

	tail->next = newnode;//讓尾結(jié)點(diǎn)的next指向新的結(jié)點(diǎn)
	newnode->prev = tail;//讓新結(jié)點(diǎn)的prev指向之前的尾結(jié)點(diǎn)
	newnode->next = phead;//讓新的結(jié)點(diǎn)的next指向頭結(jié)點(diǎn)
	phead->prev = newnode;//讓頭結(jié)點(diǎn)指向新的尾結(jié)點(diǎn)
}

雙向鏈表尾刪

void ListPopBack(ListNode* phead)
{
	assert(phead);
	if (phead->next == phead)//如果鏈表只有哨兵位結(jié)點(diǎn)的情況,就不能繼續(xù)刪除了
		return;

	ListNode* tail = phead->prev;//找到尾結(jié)點(diǎn)
	ListNode* tailPrev = tail->prev;//定義尾結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
	free(tail);//釋放要?jiǎng)h除的結(jié)點(diǎn)
	tailPrev->next = phead;//讓前一個(gè)結(jié)點(diǎn)指向哨兵位結(jié)點(diǎn)
	phead->prev = tailPrev;//讓哨兵位結(jié)點(diǎn)指向新的尾結(jié)點(diǎn)
}

雙向鏈表頭插

雙向鏈表的頭插就是在哨兵位結(jié)點(diǎn)的下一個(gè)位置插入一個(gè)新的數(shù)據(jù)。

注意:這一種方法種的指向關(guān)系不能隨意顛倒,否則就會(huì)出錯(cuò)。

void ListPushFront(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新結(jié)點(diǎn)
	newnode->next = phead->next;//新結(jié)點(diǎn)的next指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
	phead->next->prev = newnode;//頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn)
	phead->next = newnode;//頭結(jié)點(diǎn)指向新結(jié)點(diǎn)
	newnode->prev = phead;//新結(jié)點(diǎn)prev指向頭結(jié)點(diǎn)
}

我們可以對上一種情況進(jìn)行優(yōu)化,定義一個(gè)next記錄頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的地址。這樣我們就可以不用在意指向順序的問題,可以減少出錯(cuò)的概率。

void ListPushFront(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新結(jié)點(diǎn)
	ListNode* next = phead->next;//定義next記錄頭節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的位置
	phead->next = newnode;//頭結(jié)點(diǎn)next指向新結(jié)點(diǎn)
	newnode->prev = phead;//新結(jié)點(diǎn)的prev指向頭結(jié)點(diǎn)
	next->prev = newnode;//頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的prev指向新階段
	newnode->next = next;//新結(jié)點(diǎn)的next指向原頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
}

雙向鏈表頭刪

我們先找到頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn),然后在把它釋放掉。這里需要注意的是如果鏈表為空,只有哨兵位頭結(jié)點(diǎn)的情況,我們需要對其進(jìn)行特殊的處理。

void ListPopFront(ListNode* phead)
{
	assert(phead);
	if (phead->next == NULL)//只有哨兵位頭結(jié)點(diǎn)的情況
		return;
	ListNode* next = phead->next->next;//定義next指向要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
	free(phead->next);//釋放要?jiǎng)h除的結(jié)點(diǎn)
	phead->next = next;//讓哨兵位頭結(jié)點(diǎn)指向要?jiǎng)h除的下一個(gè)結(jié)點(diǎn)
	next->prev = phead;//讓要?jiǎng)h除的下一個(gè)結(jié)點(diǎn)的prev指向toujied
}

雙向鏈表查找

若我們想要對指定的位置的結(jié)點(diǎn)進(jìn)行相應(yīng)的改變就得先找到對應(yīng)的結(jié)點(diǎn),所以我們將查找指定數(shù)據(jù)封裝成一個(gè)函數(shù)。方便后續(xù)調(diào)用。

ListNode* ListFind(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;//讓cur指向哨兵位頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
	while (cur != phead)//鏈表循環(huán)是否結(jié)束的判斷條件
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;//找不到對于的結(jié)點(diǎn)
}

雙向鏈表pos前插入結(jié)點(diǎn)

推薦使用第二種方法,不容易出錯(cuò)。

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新的結(jié)點(diǎn)
	pos->prev->next = newnode;//pos的前一個(gè)結(jié)點(diǎn)的next指向新結(jié)點(diǎn)
	newnode->prev = pos->prev;//新結(jié)點(diǎn)的prev指向pos的前一個(gè)結(jié)點(diǎn)
	newnode->next = pos;//新結(jié)點(diǎn)的next指向pos結(jié)點(diǎn)
	pos->prev = newnode;//pos的prev指向新結(jié)點(diǎn)
}
void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);//創(chuàng)建一個(gè)新的結(jié)點(diǎn)
	ListNode* posPrev = pos->prev;//定義pos的前一個(gè)結(jié)點(diǎn)
	posPrev->next = newnode;//讓pos的pos前一個(gè)結(jié)點(diǎn)的next指向新結(jié)點(diǎn)
	newnode->prev = posPrev;//新結(jié)點(diǎn)的prev指向pos的前一個(gè)結(jié)點(diǎn)
	newnode->next = pos;//新結(jié)點(diǎn)的next指向pos
	pos->prev = newnode;//pos的prev指向新結(jié)點(diǎn)
}

雙向鏈表刪除pos位置的結(jié)點(diǎn)

void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;//prev為pos的前一個(gè)結(jié)點(diǎn)
	ListNode* next = pos->next;//next為pos的后一個(gè)結(jié)點(diǎn)
	free(pos);//釋放posjied
	prev->next = next;
	next->prev = prev;
}

雙向鏈表的銷毀

void ListDestroy(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;//指向哨兵位結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
	while (cur != phead)//依次循環(huán)找鏈表的每一個(gè)結(jié)點(diǎn)
	{
		ListNode* next = cur->next;//記錄cur的下一個(gè)結(jié)點(diǎn)位置
		free(cur);//釋放cur位置的結(jié)點(diǎn)
		cur = next;//指向下一個(gè)結(jié)點(diǎn)
	}
	free(phead);//釋放哨兵位頭結(jié)點(diǎn)
}

注意:在寫雙向鏈表的頭插,頭刪,尾插,尾刪時(shí)我們可以復(fù)用雙向鏈表的任意位置插入和任意位置刪除那兩個(gè)函數(shù)。那兩個(gè)函數(shù)就可以完成頭插,頭刪,尾插,尾刪這幾個(gè)功能。

順序表和鏈表的區(qū)別

順序表優(yōu)點(diǎn):

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

2.CPU高速緩存命中率會(huì)更高。

順序表缺點(diǎn):

1.由于需要物理空間連續(xù),空間不夠需要擴(kuò)容。擴(kuò)容本身有一定消耗。其次擴(kuò)容機(jī)制還存在一定的空間浪費(fèi)。

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

鏈表優(yōu)點(diǎn):

1.任意位置插入刪除數(shù)據(jù)效率高。O(1)

2.按需申請和釋放空間

鏈表缺點(diǎn):

不支持下標(biāo)的隨機(jī)訪問。有些算法不適合在它上面運(yùn)行。如:二分查找、排序等。

關(guān)于CPU相關(guān)的知識可以參考這一篇文章:CPU緩存知識

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

相關(guān)文章

  • C語言用easyx實(shí)現(xiàn)消磚塊游戲

    C語言用easyx實(shí)現(xiàn)消磚塊游戲

    這篇文章主要為大家詳細(xì)介紹了C語言消磚塊游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-05-05
  • C++程序設(shè)計(jì)-五子棋

    C++程序設(shè)計(jì)-五子棋

    本文將以簡單的存儲(chǔ)結(jié)構(gòu)及簡單的運(yùn)算,條件語句,分支語句,循環(huán)語句結(jié)合,帶來一個(gè)雙人對戰(zhàn)版五子棋,這是一個(gè)簡單的模型,實(shí)現(xiàn)了五子棋最最基本的功能。具有很好的參考價(jià)值,下面跟著小編一起來看下吧
    2017-02-02
  • 怎么鎖定鼠標(biāo)的示例代碼分享

    怎么鎖定鼠標(biāo)的示例代碼分享

    使用代碼怎么才能鎖定鼠標(biāo)?這個(gè)功能很簡單只要一個(gè)ClipCursor()就可以搞定,需要的朋友可以參考下
    2014-01-01
  • Qt使用Json的項(xiàng)目實(shí)踐

    Qt使用Json的項(xiàng)目實(shí)踐

    JSON是一種對源自Javascript的對象數(shù)據(jù)進(jìn)行編碼的格式,但現(xiàn)在被廣泛用作互聯(lián)網(wǎng)上的數(shù)據(jù)交換格式,本文主要介紹了Qt使用Json的項(xiàng)目實(shí)踐,詳細(xì)的介紹了主要使用的類以及Json實(shí)戰(zhàn),感興趣的可以了解一下
    2023-09-09
  • C++淺析類與對象的基礎(chǔ)

    C++淺析類與對象的基礎(chǔ)

    類和對象是兩種以計(jì)算機(jī)為載體的計(jì)算機(jī)語言的合稱。對象是對客觀事物的抽象,類是對對象的抽象。類是一種抽象的數(shù)據(jù)類型;變量就是可以變化的量,存儲(chǔ)在內(nèi)存中—個(gè)可以擁有在某個(gè)范圍內(nèi)的可變存儲(chǔ)區(qū)域
    2022-05-05
  • C++ Thread實(shí)現(xiàn)簡單的socket多線程通信

    C++ Thread實(shí)現(xiàn)簡單的socket多線程通信

    本文主要介紹了C++ Thread實(shí)現(xiàn)簡單的socket多線程通信,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-07-07
  • c語言二進(jìn)制數(shù)按位輸出示例

    c語言二進(jìn)制數(shù)按位輸出示例

    這篇文章主要介紹了c語言二進(jìn)制數(shù)按位輸出示例,需要的朋友可以參考下
    2014-03-03
  • C++子類父類成員函數(shù)的覆蓋和隱藏實(shí)例詳解

    C++子類父類成員函數(shù)的覆蓋和隱藏實(shí)例詳解

    這篇文章主要介紹了C++子類父類成員函數(shù)的覆蓋和隱藏實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-06-06
  • C++中的while循環(huán)和for循環(huán)語句學(xué)習(xí)教程

    C++中的while循環(huán)和for循環(huán)語句學(xué)習(xí)教程

    這篇文章主要介紹了C++中的while循環(huán)和for循環(huán)語句學(xué)習(xí)教程,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下
    2015-09-09
  • 在Visual Studio中用C++語言創(chuàng)建DLL動(dòng)態(tài)鏈接庫圖文教程

    在Visual Studio中用C++語言創(chuàng)建DLL動(dòng)態(tài)鏈接庫圖文教程

    這篇文章主要介紹了在Visual Studio中用C++語言創(chuàng)建DLL動(dòng)態(tài)鏈接庫圖文教程,本文詳細(xì)講解了DLL庫的創(chuàng)建過程,并給出了代碼示例,需要的朋友可以參考下
    2014-09-09

最新評論