序言

帶頭雙向回圈鏈表

1. 概念

2. 效果展示圖

3. 介面實作

3.01. 本文章要實作的介面

?3.02. 雙鏈表的實作

3.03. 雙鏈表的初始化

3.04. 列印鏈表

3.05. 動態申請一個節點

3.06. 頭插

3.07. 尾插

3.08. 頭刪

3.09. 尾刪

3.10. 查某個值，回傳地址

3.11. 某個位置前插入資料

3.12. 洗掉某個位置資料

3.13. 改某個值

3.14. 銷毀

總結

4. 源代碼

test.c

List.h

List.c

誰都不能阻擋你成為更優秀的人，

序言

首先本文是和上一篇單鏈表有關聯哈，上篇文章已經詳細說明了鏈表的概念和分類，這里就不過多贅述了，就簡單說明一下哈，鏈接在下面，一篇解單鏈表（0基礎看）（C語言）《資料結構與演算法》_原來45的博客-CSDN博客

上文我們講到了鏈表最重要的兩個分類，一個是單向不帶頭不回圈，本篇文章就講另一個重要的帶頭雙向回圈鏈表哈，廢話不多說，直接看代碼，

對了，這里附上作者的qq：2777137742，要是有什么問題可以在qq上面問我哈，或者文章有錯誤的地方，期待和大家共同討論，因為csdn的訊息有可能會遺漏哈，最后感謝你的支持，

帶頭雙向回圈鏈表

1. 概念

帶頭雙向回圈鏈表：結構最復雜，一般用在單獨存盤資料，實際中使用的鏈表資料結構，都

是帶頭雙向回圈鏈表，另外這個結構雖然結構復雜，但是使用代碼實作以后會發現結構會帶

來很多優勢，實作反而簡單了，后面我們代碼實作了就知道了，

這里我們來慢慢揭曉上文說到的實作更簡單，以及單鏈表的缺點，缺點就直接說了，我們可以很直觀得發現單鏈表的兩個很大的缺點，一個是尾插尾刪等都是需要遍歷也就是說時間復雜度是O（N），但是雙鏈表對應的都是O（1），效率之高，另一個缺點就是單鏈表不能找到自己的上一個節點，這都是很大的缺陷，然后我們接著看雙鏈表實作的優勢，

2. 效果展示圖

3. 介面實作

還是老話，對于介面的實作我們首先是要知道要實作什么，本文是對于雙鏈表的基本使用，所以就只實作順序表的增刪查改，還有特定位置前插入和洗掉特定位置值等當然代碼也不一定要作者這么寫，這里只是提供一種思路，廢話不多說，看代碼，

3.01. 本文章要實作的介面

3.02. 雙鏈表的實作

這是命名是ListNode是與c++對應的，大家也可以和單鏈表SListNode對應取名DListnode，但是作者為了養成一個好的習慣就取名為了ListNode哈，

3.03. 雙鏈表的初始化

注意這里初始化是自己指向自己，因為是回圈，然后本篇文章不用二級指標（不用傳地址），這里就用了一個回傳值，

3.04. 列印鏈表

3.05. 動態申請一個節點

3.06. 頭插

3.07. 尾插

3.08. 頭刪

3.09. 尾刪

3.10. 查某個值，回傳地址

3.11. 某個位置前插入資料

3.12. 洗掉某個位置資料

3.13. 改某個值

3.14. 銷毀

總結

我們可以發現對于帶頭雙向回圈鏈表的實作不需要像單鏈表那樣要去判斷沒有或者有一個節點的情況，結構非常之完美，可以利用頭結點進行各種變化，實作也非常簡單，而且也不用傳地址，

這里要再解釋一下為什么可以不傳地址，因為我們的頭沒有改變，不需要改變頭，這個改變指的是我們一開始傳的引數plist，他是一直指向我們的頭的，是指向沒有變，內容可以改變，也就是說plist的前驅prev和后繼next的指向和date是可以變的，這個理解很重要！

4. 源代碼

test.c

#include"List.h"


int main()
{
	printf("初始化\n");
	ListNode* plist = ListInit();
	printf("頭插 1 2 3 并列印\n");
	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPrint(plist);
	printf("尾插4 5 6 并列印\n");
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPushBack(plist, 6);
	ListPrint(plist);
	printf("頭刪并列印\n");
	ListPopFront(plist);
	ListPrint(plist);
	printf("尾刪并列印\n");
	ListPopBack(plist);
	ListPrint(plist);
	printf("1前插入3并列印\n");
	ListNode* pos = ListFind(plist, 1);
	ListInsert(plist, pos, 3);
	ListPrint(plist);
	printf("2前插入8并列印\n");
	pos = ListFind(plist, 2);
	ListInsert(plist, pos, 8);
	ListPrint(plist);
	printf("洗掉4并列印\n");
	pos = ListFind(plist, 4);
	ListErase(plist, pos);
	ListPrint(plist);
	printf("把1改成9并列印\n");
	ListChange(plist, 1, 9);
	ListPrint(plist);
	printf("銷毀鏈表\n");
	ListDestory(plist);
	return 0;
}

List.h

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<malloc.h>
#include<assert.h>

typedef int ListDateType;

typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	ListDateType date;
}ListNode;

//增刪查改

//初始化
ListNode* ListInit();
//銷毀
void ListDestory(ListNode* phead);
//得到一個節點
ListNode* BuyListNode(ListDateType x);
//列印
void ListPrint(ListNode* phead);

//頭插
void ListPushFront(ListNode* phead, ListDateType x);
//尾插
void ListPushBack(ListNode* phead, ListDateType x);
//頭刪
void ListPopFront(ListNode* phead);
//尾刪
void ListPopBack(ListNode* phead);

//查某個值，回傳地址
ListNode* ListFind(ListNode* phead, ListDateType x);
//改某個值
void ListChange(ListNode* phead, ListDateType source, ListDateType destination);

//某個位置前插入資料
void ListInsert(ListNode* phead, ListNode* pos, ListDateType x);
//洗掉某個位置資料
void ListErase(ListNode* phead, ListNode* pos);

List.c

#include"List.h"


//初始化
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->prev = phead;
	phead->next = phead;
	phead->date = 0;
	return phead;
}

//得到一個節點
ListNode* BuyListNode(ListDateType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->prev = NULL;
	newnode->next = NULL;
	newnode->date = x;
	return newnode;
}

//頭插
void ListPushFront(ListNode* phead, ListDateType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* first = phead->next;

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

//尾插
void ListPushBack(ListNode* phead, ListDateType x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyListNode(x);

	phead->prev = newnode;
	newnode->next=phead;
	tail->next = newnode;
	newnode->prev = tail;
}

//列印
void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
	printf("\n");
}

//頭刪
void ListPopFront(ListNode* phead)
{
	assert(phead);
	//別把頭刪了
	assert(phead->next != phead);
	ListNode* first = phead->next;
	phead->next = first->next;
	first->next->prev = phead;

	free(first);
	first = NULL;
}

//尾刪
void ListPopBack(ListNode* phead)
{
	assert(phead);
	//別把頭刪了
	assert(phead->next != phead);
	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;

	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;
}

//查某個值，回傳地址
ListNode* ListFind(ListNode* phead, ListDateType x) 
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->date == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

//某個位置前插入資料   
void ListInsert(ListNode* phead, ListNode* pos, ListDateType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* prev = pos->prev;
	
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

//洗掉某個位置資料
void ListErase(ListNode* phead, ListNode* pos)
{
	assert(phead);
	//別把頭刪了
	assert(phead->next != phead);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;

	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}

//改某個值
void ListChange(ListNode* phead, ListDateType source, ListDateType destination)
{
	assert(phead);
	ListNode* pos = ListFind(phead, source);
	pos->date = destination;
}

//銷毀
void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	ListNode* tail = cur->next;
	while (tail != phead)
	{
		free(cur);
		cur = NULL;
		cur = tail;
		tail = tail->next;
	}
	free(cur);
	cur = NULL;
	if (cur != tail)
	{
		free(tail);
		tail = NULL;
	}
}

今天的內容就到這里了哈！！！

要是認為作者有一點幫助你的話！

就來一個點贊加關注吧！！！當然訂閱是更是求之不得！

贈人玫瑰，手有余香=，=！

最后的最后感謝大家的觀看！！！

你們的支持是作者寫作的最大動力！！！

下期見哈！！！

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

標籤：其他

上一篇：《C游記》番外篇（壹）二分查找顯神威猜數游戲趣味生

下一篇：基于Python的這個庫，我實作了“隔空操物“

一篇解雙鏈表（0基礎看）（C語言）《資料結構與演算法》

序言

帶頭雙向回圈鏈表

1. 概念

2. 效果展示圖

3. 介面實作

3.01. 本文章要實作的介面

3.02. 雙鏈表的實作

3.03. 雙鏈表的初始化

3.04. 列印鏈表

3.05. 動態申請一個節點

3.06. 頭插

3.07. 尾插

3.08. 頭刪

3.09. 尾刪

3.10. 查某個值，回傳地址

3.11. 某個位置前插入資料

3.12. 洗掉某個位置資料

3.13. 改某個值

3.14. 銷毀

總結

4. 源代碼

test.c

List.h

List.c