一、本章重點(diǎn)

• 帶頭雙向循環(huán)鏈表介紹
• 帶頭雙向循環(huán)鏈表常用接口實(shí)現(xiàn)
• 實(shí)現(xiàn)接口總結(jié)
• 在線oj訓(xùn)練與詳解

二、帶頭雙向循環(huán)鏈表介紹

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

• 帶頭：存在一個(gè)哨兵位的頭節(jié)點(diǎn)，該節(jié)點(diǎn)是個(gè)無(wú)效節(jié)點(diǎn)，不存儲(chǔ)任何有效信息，但使用它可以方便我們頭尾插和頭尾刪時(shí)不用判斷頭節(jié)點(diǎn)指向NULL的情況，同時(shí)也不需要改變頭指針的指向，也就不需要傳二級(jí)指針了。?
• 雙向：每個(gè)結(jié)構(gòu)體有兩個(gè)指針，分別指向前一個(gè)結(jié)構(gòu)體和后一個(gè)結(jié)構(gòu)體。
• 循環(huán)：最后一個(gè)結(jié)構(gòu)體的指針不再指向NULL，而是指向第一個(gè)結(jié)構(gòu)體。（單向）
• 第一個(gè)結(jié)構(gòu)體的前指針指向最后一個(gè)結(jié)構(gòu)體，最后一個(gè)結(jié)構(gòu)體的后指針指向第一個(gè)結(jié)構(gòu)體（雙向）。

圖解?

2.2最常用的兩種鏈表結(jié)構(gòu)

• 更具有無(wú)頭，單雙向，是否循環(huán)組合起來(lái)有8種結(jié)構(gòu)，但最長(zhǎng)用的還是無(wú)頭單向非循環(huán)鏈表和帶頭雙向循環(huán)鏈表
• 無(wú)頭單向非循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存數(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ì)帶來(lái)很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡(jiǎn)單了，后面我們代碼實(shí)現(xiàn)了就知道了。

三、帶頭雙向循環(huán)鏈表常用接口實(shí)現(xiàn)?

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

typedef int DataType;
typedef struct DListNode
{
	DataType data;
	DListNode* prev;
	DListNode* next;
}DListNode;

3.2帶頭雙向循環(huán)鏈表的初始化?

void DListInint(DListNode** pphead)
{
	*pphead = (DListNode*)malloc(sizeof(DListNode));
	(*pphead)->next = (*pphead);
	(*pphead)->prev = (*pphead);
}

?或者使用返回節(jié)點(diǎn)的方法也能實(shí)現(xiàn)初始化

DListNode* DListInit()
	{
		DListNode* phead = (DListNode*)malloc(sizeof(DListNode));
		phead->next = phead;
		phead->prev = phead;
		return phead;
	}

3.3創(chuàng)建新節(jié)點(diǎn)

DListNode* BuyDListNode(DataType x)
{
	DListNode* temp = (DListNode*)malloc(sizeof(DListNode));
	if (temp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	temp->prev = NULL;
	temp->next = NULL;
	temp->data = x;
	return temp;
}

3.4尾插

void DListPushBack(DListNode* phead,DataType x)
{
	DListNode* newnode = BuyDListNode(x);
	DListNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

3.5打印鏈表

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

3.6頭插

void DListNodePushFront(DListNode* phead, DataType x)
{
	DListNode* next = phead->next;
	DListNode* newnode = BuyDListNode(x);
	next->prev = newnode;
	newnode->next = next;
	newnode->prev = phead;
	phead->next = newnode;
}

3.7尾刪

void DListNodePopBack(DListNode* phead)
{
	if (phead->next == phead)
	{
		return;
	}
	DListNode* tail = phead->prev;
	DListNode* prev = tail->prev;
	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;
}

3.8頭刪

void DListNodePopFront(DListNode* phead)
{
	if (phead->next == phead)
	{
		return;
	}
	DListNode* firstnode = phead->next;
	DListNode* secondnode = firstnode->next;
	secondnode->prev = phead;
	phead->next = secondnode;
	free(firstnode);
	firstnode = NULL;
}

3.9查找data（返回data的節(jié)點(diǎn)地址）

DListNode* DListNodeFind(DListNode* phead, DataType x)
{
	DListNode* firstnode = phead->next;
	while (firstnode != phead)
	{
		if (firstnode->data == x)
		{
			return firstnode;
		}
		firstnode = firstnode->next;
	}
	return NULL;
}

3.10在pos位置之前插入節(jié)點(diǎn)

void DListNodeInsert(DListNode* pos, DataType x)
{
	DListNode* prev = pos->prev;
	DListNode* newnode = BuyDListNode(x);
	newnode->next = pos;
	newnode->prev = prev;
	prev->next = newnode;
	pos->prev = newnode;
}

3.11刪除pos位置的節(jié)點(diǎn)

void DListNodeErase(DListNode* pos)
{
	DListNode* prev = pos->prev;
	DListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}

四、實(shí)現(xiàn)接口總結(jié)

• 多畫圖：能給清晰展示變化的過(guò)程，有利于實(shí)現(xiàn)編程。
• 小知識(shí)：head->next既可表示前一個(gè)結(jié)構(gòu)體的成員變量，有可表示后一個(gè)結(jié)構(gòu)體的地址。當(dāng)head->next作為左值時(shí)代表的是成員變量，作右值時(shí)代表的是后一個(gè)結(jié)構(gòu)體的地址。對(duì)于鏈表來(lái)說(shuō)理解這一點(diǎn)非常重要。
• 實(shí)踐：實(shí)踐出真知
• 帶頭雙向循環(huán)鏈表：相比于單鏈表，它實(shí)現(xiàn)起來(lái)更簡(jiǎn)單，不用向單鏈表一樣分情況討論鏈表的長(zhǎng)度。雖然結(jié)構(gòu)較復(fù)雜，但使用起來(lái)更簡(jiǎn)單，更方便。 ?

五、在線oj訓(xùn)練與詳解

鏈表的中間節(jié)點(diǎn)（力扣）

給定一個(gè)頭結(jié)點(diǎn)為?head?的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。

如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)中間結(jié)點(diǎn)。

輸入：[1,2,3,4,5]

輸出：此列表中的結(jié)點(diǎn) 3 (序列化形式：[3,4,5])

返回的結(jié)點(diǎn)值為 3 。 (測(cè)評(píng)系統(tǒng)對(duì)該結(jié)點(diǎn)序列化表述是 [3,4,5])。

注意，我們返回了一個(gè) ListNode 類型的對(duì)象 ans，

這樣：

ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

來(lái)源：力扣（LeetCode）

?思路：快慢指針

取兩個(gè)指針，初始時(shí)均指向head，一個(gè)為快指針（fast）一次走兩步，另一個(gè)為慢指針（slow）一次走一步，當(dāng)快指針滿足fast==NULL（偶數(shù)個(gè)節(jié)點(diǎn)）或者fast->next==NULL（奇數(shù)個(gè)節(jié)點(diǎn)）時(shí)，slow指向中間節(jié)點(diǎn)，返回slow即可。

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast=head;
    struct ListNode* slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

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

最新評(píng)論