前言

上一篇數(shù)據(jù)結(jié)構(gòu)專欄：C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)單鏈表接口函數(shù)全面講解教程

我們介紹了單鏈表的各個(gè)接口函數(shù)，大家可能會(huì)發(fā)現(xiàn)單鏈表存在一些缺陷：比如它一個(gè)節(jié)點(diǎn)要存儲(chǔ)數(shù)據(jù)+下一個(gè)節(jié)點(diǎn)地址，占用的空間要遠(yuǎn)多于順序表；并且由于單鏈表是無(wú)法從后往前找的，如果你想進(jìn)行尾刪這樣的操作，你必須從第一個(gè)節(jié)點(diǎn)往后找，你的時(shí)間復(fù)雜度一定是O（n）。

為了解決上面的一些缺陷，我們今天來(lái)介紹帶頭雙向循環(huán)鏈表

一、什么是帶頭循環(huán)雙向鏈表

這種鏈表會(huì)有一個(gè)哨兵位head節(jié)點(diǎn)指向d1,然后d1指向d2…這和單鏈表非常相似。
但和單鏈表最大的區(qū)別就是：這種鏈表的每個(gè)節(jié)點(diǎn)不僅會(huì)存儲(chǔ)下一個(gè)節(jié)點(diǎn)地址而且會(huì)存儲(chǔ)上一個(gè)節(jié)點(diǎn)的地址，然后尾節(jié)點(diǎn)會(huì)存儲(chǔ)一個(gè)指向哨兵位head的地址，然后哨兵位head會(huì)存儲(chǔ)一個(gè)指向尾結(jié)點(diǎn)的地址。
具體代碼如下：

typedef int LTDataType;//萬(wàn)一以后需要改鏈表數(shù)據(jù)類型，可以直接在這里更改（int）
typedef struct ListNode
{
	struct ListNode*next;
	struct ListNode*prev;
	LTDataType data;
}ListNode;//結(jié)構(gòu)體重命名

示例：pandas 是基于NumPy 的一種工具，該工具是為了解決數(shù)據(jù)分析任務(wù)而創(chuàng)建的。

二、鏈表初始化

類似于上圖的效果，剛開(kāi)始創(chuàng)建只有一個(gè)節(jié)點(diǎn)，它儲(chǔ)存的前地址和后地址都指向自己

代碼如下（示例）：

#include<stdlib.h>//malloc函數(shù)頭文件
ListNode* BuyListNode(LTDataType x)//創(chuàng)建一個(gè)節(jié)點(diǎn)
{
	ListNode*newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
ListNode* ListInit()//鏈表初始化
{
	ListNode*phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

ps：這里L(fēng)istInit函數(shù)用的是返回值的方法，你也可以用二級(jí)指針傳參來(lái)進(jìn)行初始化操作

三、鏈表接口函數(shù)

1.尾插

我們以上圖為例，原先鏈表的head節(jié)點(diǎn)的前驅(qū)指向3，然后3的后驅(qū)指向head節(jié)點(diǎn)，那在3后面怎么進(jìn)行尾插呢？由于head節(jié)點(diǎn)里存放了3節(jié)點(diǎn)的地址，所以我們可以直接找到3節(jié)點(diǎn)，找到之后怎么辦?把head節(jié)點(diǎn)的前驅(qū)改成4節(jié)點(diǎn)地址，3節(jié)點(diǎn)后驅(qū)改為4節(jié)點(diǎn)地址，最后4節(jié)點(diǎn)后驅(qū)指向head節(jié)點(diǎn)。如下圖：

代碼如下（示例）：

#include<assert.h>//assert函數(shù)頭文件
void ListPushBack(ListNode*phead, LTDataType x)//尾插
{
    assert(phead);//對(duì)傳過(guò)來(lái)的指針進(jìn)行斷言,因?yàn)槟阋M(jìn)行尾插至少得有個(gè)頭節(jié)點(diǎn)啊
    //如果傳過(guò)來(lái)的是空指針會(huì)進(jìn)行報(bào)錯(cuò)
	ListNode*tail = phead->prev;
	ListNode*newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->data = phead;
	phead->prev = newnode;
}

2.頭插

如上圖，先要在head和d1之間進(jìn)行頭插，怎么操作？非常簡(jiǎn)單，思路和尾插一模一樣
head的后驅(qū)指向newnode，newnode的前驅(qū)和后驅(qū)分別指向phead和d1，d1前驅(qū)指向newnode如下圖：

代碼如下（示例）：

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;
}

注意?。?！這里是先定義了一個(gè)first來(lái)存放d1這個(gè)地址，如果不事先定義的話，phead->next = newnode;head不再存儲(chǔ)d1地址，你就找不到d1了。當(dāng)然了，如果你就是不想先定義一個(gè)first來(lái)存放d1地址也可以。怎么做呢？“先連后斷”，newnode后驅(qū)先接上d1節(jié)點(diǎn)，然后你head節(jié)點(diǎn)后驅(qū)接上newnode。

3.頭刪

頭刪也是和前面兩個(gè)類似的思想

頭刪也就是把d1節(jié)點(diǎn)刪掉，我們定義2個(gè)指針?lè)謩e指向d1和d2，然后把head節(jié)點(diǎn)后驅(qū)接指向d2，d2前驅(qū)指向head即可，如下圖：

代碼如下（示例）：

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

4.尾刪

現(xiàn)在要?jiǎng)h除d3這個(gè)節(jié)點(diǎn)，我們定義一個(gè)tail和prev指針?lè)謩e指向d3和d2，然后把d2后驅(qū)接上head，head前驅(qū)接上d2即可，如下圖：

代碼如下（示例）：

void ListPopBack(ListNode*phead)
{
	assert(phead);
	assert(phead->next != phead);//要進(jìn)行尾刪至少保證有一個(gè)節(jié)點(diǎn)可刪（非head節(jié)點(diǎn)）
	ListNode*tail = phead->prev;//頭節(jié)點(diǎn)前驅(qū)指向尾部
	ListNode*prev = tail->prev;//通過(guò)尾部得到d2地址
	prev->next = phead;//d2后驅(qū)head節(jié)點(diǎn)
	phead->prev = prev;//head前驅(qū)指向d2節(jié)點(diǎn)
}

5.任意位置插入數(shù)據(jù)

要在某個(gè)位置前插入數(shù)據(jù)，你需要先找到那個(gè)位置在哪里，我們先寫(xiě)一個(gè)查找函數(shù)

怎么個(gè)找法呢？很簡(jiǎn)單，定義一個(gè)cur指針，然后從d1開(kāi)始遍歷看有沒(méi)有我們想要找的數(shù)據(jù)，遍歷到head節(jié)點(diǎn)結(jié)束。
代碼如下（示例）：

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;//遍歷完鏈表都沒(méi)有找到就返回空指針
}

找到所需位置后就是進(jìn)行，插入操作

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

兩個(gè)函數(shù)一起調(diào)用也是很簡(jiǎn)單的，比如我現(xiàn)在要在鏈表里數(shù)據(jù)3的位置前插入300，下面兩行代碼即可完成兩個(gè)函數(shù)的運(yùn)用。

ListNode*pos = ListFind(plist, 3);
ListInsert(pos, 300);

ps:這里找到所需位置指針，你如果需要，也可以通過(guò)該指針對(duì)該位置的值進(jìn)行修改，比如（返回的指針）->data=n

6.任意位置刪除數(shù)據(jù)

現(xiàn)在要?jiǎng)h除pos位置的數(shù)據(jù)，怎么操作？非常簡(jiǎn)單！定義一個(gè)prev指向pos前一個(gè)節(jié)點(diǎn)，定義一個(gè)next指向pos后一個(gè)節(jié)點(diǎn)，然后prev和next連起來(lái)即可，如圖：

代碼如下（示例）：

void ListErase(ListNode*pos)//指定位置刪除
{
	assert(pos);
	ListNode*prev = pos->prev;
	ListNode*next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);//prev和next連起來(lái)了，pos就可以被釋放掉了
}

四、打印鏈表

以上圖為例：要打印一個(gè)鏈表，head節(jié)點(diǎn)是不需要打印的，我們只需要打印存儲(chǔ)實(shí)際數(shù)據(jù)的d1，d2，d3即可，定義一個(gè)變量cur，讓它從d1開(kāi)始遍歷，到head節(jié)點(diǎn)結(jié)束即可。
代碼如下（示例）：

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

總結(jié)

本文介紹了帶頭循環(huán)雙向鏈表，包括其定義、各個(gè)接口函數(shù)、及其遍歷打印。雖然是鏈表中最復(fù)雜的結(jié)構(gòu)，但它的代碼操作卻是最簡(jiǎn)單的，希望通過(guò)今天的學(xué)習(xí)讀者能有所收獲~更多關(guān)于帶頭雙向循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論