日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網(wǎng)站首頁 編程語言 正文

C語言?超詳細介紹與實現(xiàn)線性表中的帶頭雙向循環(huán)鏈表_C 語言

作者：李逢溪 ? 更新時間： 2022-06-01 編程語言

一、本章重點

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

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

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

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

圖解?

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

  • 更具有無頭，單雙向，是否循環(huán)組合起來有8種結(jié)構(gòu)，但最長用的還是無頭單向非循環(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)了就知道了。

三、帶頭雙向循環(huán)鏈表常用接口實現(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é)點的方法也能實現(xiàn)初始化

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

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

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é)點地址）

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é)點

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é)點

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

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

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

五、在線oj訓練與詳解

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

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

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

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

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

返回的結(jié)點值為 3 。 (測評系統(tǒng)對該結(jié)點序列化表述是 [3,4,5])。

注意，我們返回了一個 ListNode 類型的對象 ans，

這樣：

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

來源：力扣（LeetCode）

?思路：快慢指針

取兩個指針，初始時均指向head，一個為快指針（fast）一次走兩步，另一個為慢指針（slow）一次走一步，當快指針滿足fast==NULL（偶數(shù)個節(jié)點）或者fast->next==NULL（奇數(shù)個節(jié)點）時，slow指向中間節(jié)點，返回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;
}

原文鏈接：https://blog.csdn.net/m0_62171658/article/details/123315681

欄目分類
最近更新