C語言怎么實現線性表中的帶頭雙向循環鏈表

這篇文章主要介紹了C語言怎么實現線性表中的帶頭雙向循環鏈表的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇C語言怎么實現線性表中的帶頭雙向循環鏈表文章都會有所收獲，下面我們一起來看看吧。

一、本章重點

• 帶頭雙向循環鏈表介紹

• 帶頭雙向循環鏈表常用接口實現

• 實現接口總結

• 在線oj訓練與詳解

二、帶頭雙向循環鏈表介紹

2.1什么是帶頭雙向循環鏈表？

• 帶頭：存在一個哨兵位的頭節點，該節點是個無效節點，不存儲任何有效信息，但使用它可以方便我們頭尾插和頭尾刪時不用判斷頭節點指向NULL的情況，同時也不需要改變頭指針的指向，也就不需要傳二級指針了。 

• 雙向：每個結構體有兩個指針，分別指向前一個結構體和后一個結構體。

• 循環：最后一個結構體的指針不再指向NULL，而是指向第一個結構體。（單向）

• 第一個結構體的前指針指向最后一個結構體，最后一個結構體的后指針指向第一個結構體（雙向）。

圖解 

2.2最常用的兩種鏈表結構

• 更具有無頭，單雙向，是否循環組合起來有8種結構，但最長用的還是無頭單向非循環鏈表和帶頭雙向循環鏈表

• 無頭單向非循環鏈表：結構簡單，一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結構，如哈希桶、圖的鄰接表等等。另外這種結構在筆試面試中出現很多。 

• 帶頭雙向循環鏈表：結構最復雜，一般用在單獨存儲數據。實際中使用的鏈表數據結構，都是帶頭雙向循環鏈表。另外這個結構雖然結構復雜，但是使用代碼實現以后會發現結構會帶來很多優勢，實現反而簡單了，后面我們代碼實現了就知道了。

三、帶頭雙向循環鏈表常用接口實現 

3.1結構體創建

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

3.2帶頭雙向循環鏈表的初始化 

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

 或者使用返回節點的方法也能實現初始化

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

3.3創建新節點

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的節點地址）

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位置之前插入節點

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位置的節點

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

四、實現接口總結

• 多畫圖：能給清晰展示變化的過程，有利于實現編程。

• 小知識：head->next既可表示前一個結構體的成員變量，有可表示后一個結構體的地址。當head->next作為左值時代表的是成員變量，作右值時代表的是后一個結構體的地址。對于鏈表來說理解這一點非常重要。

• 實踐：實踐出真知

• 帶頭雙向循環鏈表：相比于單鏈表，它實現起來更簡單，不用向單鏈表一樣分情況討論鏈表的長度。雖然結構較復雜，但使用起來更簡單，更方便。  

五、在線oj訓練與詳解

鏈表的中間節點（力扣）

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

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

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

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

返回的結點值為 3 。 (測評系統對該結點序列化表述是 [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（偶數個節點）或者fast->next==NULL（奇數個節點）時，slow指向中間節點，返回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;
}

關于“C語言怎么實現線性表中的帶頭雙向循環鏈表”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“C語言怎么實現線性表中的帶頭雙向循環鏈表”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。