一、雙向帶頭回圈鏈表的優劣勢

結構復雜，但由于結點資訊中多包含了一個指向上一個結點的指標，這樣操作起來就特別方便，它彌補了單鏈表的缺點，使得鏈表更加靈活、實用，
在這里插入圖片描述

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

一、定義結構體

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

二、創建節點函式

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

三、初始化鏈表

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

四、鏈表的尾插

這點就可以體現出雙向回圈帶頭鏈表的好處了，不需要進行遍歷，只需要改變指標的位置即可，

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

五、鏈表的頭插

頭插從第二個節點開始，也就是第一個保存有效資料的節點，

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

六、鏈表的尾刪

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

七、鏈表的頭刪

頭刪仍然不改變第一個節點，從第二個節點開始，

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

八、鏈表的查找

遍歷找，與單鏈表類似，

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

九、鏈表的插入

與頭插的方法類似，

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

十、鏈表的列印

這里我們要注意結束條件，是等于第一個節點，

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299669.html

標籤：其他

上一篇：關于linux新手快速入門的幾個重要概念及指令

下一篇：關于指標的一些經典例題詳解

資料結構之雙向帶頭回圈鏈表

雙向帶頭回圈鏈表