系列文章目錄

前言

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

一、鏈表的概念及結構

1.鏈表的概念

鏈表是一種物理存盤結構上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的 ，

2.雙向帶頭回圈鏈表結構

二、雙向帶頭回圈鏈表實作

1.定義鏈表節點struct ListNode

資料域data,指標域中包括指向前面節點的前驅指標prev，指向后面的后驅指標next
代碼如下：

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}; 

2.創建鏈表節點BuyListNode函式

代碼如下：

struct ListNode* BuyListNode(LTDataType x)
{
	struct ListNode* Node = (struct ListNode*)malloc(sizeof(struct ListNode));
	Node->next = NULL;
	Node->prev = NULL;
	Node->data = x;
	return Node;
}

3.鏈表初始化ListInit函式

代碼如下：

struct ListNode* ListInit()
{
	struct ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

4.鏈表尾部插入資料ListPushBack函式

代碼如下：

void  ListPushBack(struct ListNode* phead, LTDataType x)
{
	assert(phead);
	struct ListNode* tail = phead->prev;
	struct ListNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

5.鏈表頭部插入資料ListPushFront函式

代碼如下：

void ListPushFront(struct ListNode* phead, LTDataType x)
{
	assert(phead);
	struct ListNode* newnode = BuyListNode(x);
	struct ListNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

6.鏈表尾部洗掉資料ListPopBack函式

代碼如下：

void ListPopBack(struct ListNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	struct ListNode* tail = phead->prev;
	struct ListNode* second = tail->prev;
	free(tail);
	tail = NULL;
	second->next = phead;
	phead->prev = second;
}

7.鏈表頭部洗掉資料ListPopFront函式

代碼如下：

void ListPopFront(struct ListNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	struct ListNode* first = phead->next;
	struct ListNode* firstNext = first->next;
	free(first);
	first = NULL;
	phead->next = firstNext;
	first->prev = phead;
}

8.鏈表查找資料ListFind函式

代碼如下：

struct ListNode* ListFind(struct ListNode* phead, LTDataType x)
{
	assert(phead);
	struct ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

9.鏈表插入資料ListInsert函式

代碼如下：

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

10.鏈表洗掉資料ListEarse函式

代碼如下：

void ListEarse(struct ListNode* pos)
{
	assert(pos);
	struct ListNode* prev = pos->prev;
	struct ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}

12.鏈表清空資料ListEmpty函式

代碼如下：

int ListEmpty(struct ListNode* phead)
{
	assert(phead);
	return phead->next == phead ? 1 : 0;
}

13.鏈表求解長度ListSize函式

代碼如下：

int ListSize(struct ListNode* phead)
{
	assert(phead);
	int size = 0;
	struct ListNode* cur = phead->next;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

14.鏈表銷毀ListDestory函式

代碼如下：

void ListDestory(struct ListNode* phead)
{
	assert(phead);
	struct ListNode* cur = phead->next;
	while (cur != phead)
	{
		struct ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

15.鏈表列印資料ListPrint函式

代碼如下：

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

總結

以上就是今天要講的內容，本文僅僅簡單介紹了雙向帶頭回圈鏈表的使用，帶頭雙向回圈鏈表：結構最復雜，一般用在單獨存盤資料，實際中使用的鏈表資料結構，都是帶頭雙向回圈鏈表，另外這個結構雖然結構復雜，但是使用代碼實作以后會發現結構會帶來很多優勢，我們務必掌握，另外，如果有需要原始碼的私信我即可，還有，，如果上述有任何問題，請懂哥指教，不過沒關系，主要是自己能堅持，更希望有一起學習的同學可以幫我指正，但是如果可以請溫柔一點跟我講，愛與和平是永遠的主題，愛各位了，