首頁 > 軟體

C語言超詳細講解資料結構中雙向帶頭回圈連結串列

2022-04-11 13:00:31

一、概念

前文我們已經學習了單向連結串列,並通過oj題目深入瞭解了帶頭節點的連結串列以及帶環連結串列,來畫張圖總體回顧下:

在我們學習的連結串列中,其實總共有8種,都是單雙向和帶不帶頭以及帶不帶環的任意組合

今兒要學習的是雙向 - 帶頭 - 迴圈連結串列,聽名字就覺著結構很複雜,要比曾經學的單向 - 不帶頭 - 不迴圈 連結串列的結構複雜的多 ,確實也是。先來畫張圖整體感受下:

解釋:

  • 雙向:就要確保每個資料存兩個指標next和prev。next指向下一個節點,prev指向上一個節點
  • 帶頭:帶一個哨兵位的頭節點在資料的最前頭。
  • 迴圈:尾節點的next指向哨兵位頭節點,而哨兵位的上一個節點prev指向尾節點,構成迴圈。

正文開始:

二、必備工作

2.1、建立雙向連結串列結構

因為是雙向連結串列,所以在結構體裡頭必然有兩個指標,一個next指向下一個節點,一個prev指向上一個節點。

List.h 檔案:

//建立雙向連結串列結構
typedef int LTDataType;   //方便後續更改資料型別,本文以int整型為主
typedef struct ListNode
{
	LTDataType data; //儲存資料
	struct ListNode* next; //指向下一個
	struct ListNode* prev; //指向上一個
}LTNode; //方便後續使用,不需要重複些struct

2.2、初始化連結串列

思路:

在初始化的時候要傳地址,因為形參的改變不會影響實參,pphead的改變不會影響pList,要傳pList的地址,用**pphead來接收,此時就要assert斷言了,因為二級指標地址不可能位空。因為是雙向迴圈連結串列,所以要將建立好的哨兵位節點的next和prev均指向自己。

List.h 檔案:(1)

//初始化連結串列(二級指標版)
void ListInit(LTNode* pphead);

List.c 檔案:(1)

//初始化連結串列(二級指標版)
void ListInit(LTNode** pphead)
{
	//傳二級指標,那麼當然要斷言
	assert(pphead);
	*pphead = BuyLTNode(0);//因為是帶哨兵位的頭節點,所以一開始就要給一個節點
	//為了迴圈,要讓哨兵位的next和prev均指向自己
	(*pphead)->next = *pphead; //注意優先順序,*pphead要加括號
	(*pphead)->prev = *pphead;
}

注意:

上一種方法我們傳的是二級指標,那麼可以傳一級指標嗎,其實也是可以的,只需寫個函數返回指標即可

List.h 檔案:(2)

//初始化連結串列(一級指標版本)
LTNode* ListInit();

List.c 檔案:(2)

//初始化連結串列(一級指標版)
LTNode* ListInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

2.3、動態申請節點

List.c 檔案:

//建立新節點
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc failn");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode; //返回新建立的節點
}

2.4、列印連結串列

思路:

既然是列印,首先要搞明白一點,哨兵位不用來存放有效資料,那麼就不需要列印,定義一個cur指標來迭代,那麼應該從phead的next開始列印,當cur走完一遍,重又回到phead的時候停止

List.h 檔案:

//列印連結串列
void ListPrint(LTNode* phead);

List.c 檔案:

//列印連結串列
void ListPrint(LTNode* phead)
{
	assert(phead);//斷言
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("n");
}

2.5、銷燬連結串列

思路:

既然是銷燬連結串列了,那麼自然是要把連結串列的所有元素包括哨兵位都給銷燬掉,但畢竟剛開始傳phead的時候是不能為空的,所以要斷言,在把所有有效資料銷燬後最後再銷燬哨兵位即可。

法一:遍歷

定義一個指標cur,從phead的next第一個有效資料開始free,儲存下一個,再free,依次遍歷下去

法二:附用ListErase函數

此法也可以,不過每次Erase完,都會把前後兩個節點再連結起來,雖說最後都會銷燬,但duck不必多此一舉,所有直接採用法一比較好

List.h 檔案:

//銷燬連結串列
void ListDestory(LTNode* phead);

List.c 檔案:

//銷燬連結串列
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	//銷燬從第一個節點到尾部的資料
	while (cur != phead)
	{
		LTNode* next = cur->next;
		//ListErase(cur);
		free(cur);
		cur = next;
	}
	//置空哨兵位節點phead
	free(phead);
	phead = NULL;
}

Test.c 檔案:

void TestList7()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數位
	}
	ListPrint(pList);//列印
	//銷燬連結串列
	ListDestory(pList);
	pList = NULL;
}

三、主要功能

3.1、在pos節點前插入資料

思路:

假設我們已經進行了尾插4個數位,現在想在數位3的前面插入30,那麼首先就要查詢有無數位3,若有,則插入。注意:這裡需要用到後文才講到的查詢函數,這裡直接參照了,詳解看後文即可,問題不大!

首先,將30放到新建立的節點newnode裡頭,為了實現雙向,要先把3的前一個資料2的next指向新節點newnode,把newnode的prev指向2,newnode的next指向3,3的prev指向newnode。

 List.h 檔案:

//在pos前插入資料
void ListInsert(LTNode* pos, LTDataType x);

List.c 檔案:

//在pos前插入資料
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	//建立插入資料的新節點
	LTNode* newnode = BuyLTNode(x);
	//連結左側
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	//連結右側
	newnode->next = pos;
	pos->prev = newnode;
}

Test.c 檔案:

void TestList3()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個資料
	}
	ListPrint(pList);//列印尾插的7個
	//尋找數位
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListInsert(pos, 30); //找到數位3就插入
	}
	ListPrint(pList);//列印
}

效果如下:

尾插

思路:

首先,因為此連結串列是帶哨兵位的頭節點,所以頭節點必然不為空,剛開始就要assert斷言。其次,單連結串列尾插需要找尾,雙向連結串列雖然也需要,不過非常簡單,不需要再遍歷連結串列了,因為哨兵位頭節點的phead的上一個節點指向的就是尾,這就充分體現了雙向迴圈的好處,找到了尾節點就需要再建立一個節點儲存插入資料,方便尾插。

List.h 檔案:

//尾插
void ListPushBack(LTNode* phead, LTDataType x);

List.c 檔案:1.0

//尾插1.0
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); //斷言,防止頭節點為空
	LTNode* tail = phead->prev; //找到尾節點,便於後續插入資料
	LTNode* newnode = BuyLTNode(x);//建立新節點
	//將此新插入的尾節點與上一個節點連結起來
	tail->next = newnode;
	newnode->prev = tail;
	//將尾節點與哨兵位phead連結起來構成迴圈
	newnode->next = phead;
	phead->prev = newnode;
}

Test.c 檔案:

void TestList1()
{
	//初始化(法一)
	/*LTNode* pList = NULL;
	ListInit(&pList);*/
	//初始化(法二)
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個資料
	}
	ListPrint(pList);//列印尾插的7個
}

效果如下:

注意:

在上文中,我們學習了在pos前插入資料,那麼設想一下,當pos就等於phead的時候,它(phead)的前不就是連結串列的尾部嗎,那麼理所應當,尾插也可以這樣完成:

List.c 檔案:2.0

//尾插2.0
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); 
	ListInsert(phead, x);
}

頭插

思路:

前面我們已經學習了在pos前插入資料,那麼頭插的實現就尤為簡單了,當pos為原第一個資料phead->next時,此時就是在其之前插入資料,那麼實現的不久是頭插嗎,如下:

List.h 檔案:

//頭插
void ListPushFront(LTNode* phead, LTDataType x);

List.c 檔案:

//頭插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

Test.c 檔案:

void TestList4()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數位
	}
	ListPrint(pList);//列印
	for (int i = -2; i <= 0; i++)
	{
		ListPushFront(pList, i); //頭插3個數位
	}
	ListPrint(pList);//列印
}

效果如下:

3.2、刪除pos處節點資料

思路:

刪除pos處資料其實也很簡單,有點類似於把pos處直接忽略的思想,或者說是繞過去。首先,需要找到pos的上一個節點prev和下一個節點next,將prev和next互相連結即可,直接跳過了pos,這樣就實現了刪除pos處節點的資料,記得把pos處給free釋放掉。這裡我們以pos為2範例:

 List.h 檔案:

//刪除pos處資料
void ListErase(LTNode* pos);

List.c 檔案:

//刪除pos處資料
void ListErase(LTNode* pos)
{
	assert(pos);
	//定義兩個指標儲存pos兩邊的節點
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	//將prev和next連結起來
	prev->next = next;
	next->prev = prev;
	//free釋放
	free(pos);
	pos = NULL;
}

Test.c 檔案:

void TestList5()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個資料
	}
	ListPrint(pList);//列印尾插的7個
	//尋找數位
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListErase(pos); //刪除pos處資料
		pos = NULL; //形參的改變不會影響實參,最好在這置空pos
	}
	ListPrint(pList);//列印
}

效果如下:

尾刪

思路:

雙向迴圈連結串列的特點將再次得以體現,根據其特性,我們知道phead的prev指向尾節點,用tail指標儲存,再定義一個指標tailPrev指向tail的prev,現僅需將tailPrev的next指向哨兵位節點phead,再把哨兵位phead的prev重新置成tailPrev即可,但是別忘記把刪掉的尾節點給釋放掉,得free(tail)。記得要斷言連結串列不能為空,因為不能刪除哨兵位節點。

List.H 檔案:

//尾刪
void ListPopBack(LTNode* phead);

List.c 檔案:1.0

//尾刪
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位,不能為空,要斷言
	assert(phead->next != phead); //防止連結串列為空,導致刪除哨兵位節點
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	//釋放尾節點
	free(tail);
	tail = NULL;
	//將連結串列迴圈起來
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

Test.c 檔案:

void TestList2()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個資料
	}
	ListPrint(pList);//列印尾插的7個
	//尾刪兩次
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//再次列印
}

效果如下:

 注意:

前文我們已經學了刪除pos處節點的資料,那麼當pos為phead->prev時,刪除的是不是就是尾節點,所以,尾刪理所應當可以這樣寫:

List.c 檔案:2.0

//尾刪
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位,不能為空,要斷言
	assert(phead->next != phead); //防止連結串列為空,導致刪除哨兵位節點
	ListErase(phead->prev);
}

頭刪

思路:

有了上文之鑑,我們可以直接利用前面寫的刪除pos處資料的函數來完成,當pos為phead->prev時,pos的位置就是尾,此時刪除的就是尾。當然還得注意一點,需要額外assert斷言防止刪除的資料為哨兵位的節點。

List.h 檔案:

//頭刪
void ListPopFront(LTNode* phead);

List.c 檔案:

//頭刪
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); //防止刪除哨兵位節點
	ListErase(phead->next);
}

Test.c 檔案:

void TestList6()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數位
	}
	ListPrint(pList);//列印
	//頭插3個數位
	ListPushFront(pList, 0);
	ListPushFront(pList, -1);
	ListPushFront(pList, -2);
	ListPrint(pList);//列印
	//尾刪3個數位
	ListPopBack(pList);
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//列印
	//頭刪3個數位
	ListPopFront(pList);
	ListPopFront(pList);
	ListPopFront(pList);
	ListPrint(pList);//列印
}

效果如下:

3.3、查詢資料

思路:

查詢資料其實也比較簡單,首先,定義一個指標cur指向哨兵位phead的next,依次遍歷cur看cur->data是否為查詢的資料x,如果是,則返回cur,否則繼續(cur=cur->next),若找不到則返回NULL。

List.h 檔案:

//連結串列查詢
LTNode* ListFind(LTNode* phead, LTDataType x);

List.c 檔案:

//連結串列查詢
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur; //找到就返回cur
		}
		cur = cur->next;
	}
	return NULL; //找不到就返回空
}

四、總程式碼

List.h 檔案

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//建立雙向連結串列結構
typedef int LTDataType;   //方便後續更改資料型別,本文以int整型為主
typedef struct ListNode
{
	LTDataType data; //儲存資料
	struct ListNode* next; //指向下一個
	struct ListNode* prev; //指向上一個
}LTNode; //方便後續使用,不需要重複些struct
 
//初始化連結串列(二級指標版本)
/*void ListInit(LTNode** pphead);*/
//初始化連結串列(一級指標版本)
LTNode* ListInit();
 
//列印連結串列
void ListPrint(LTNode* phead);
//連結串列查詢
LTNode* ListFind(LTNode* phead, LTDataType x);
//銷燬連結串列
void ListDestory(LTNode* phead);
 
//尾插
void ListPushBack(LTNode* phead, LTDataType x);
//尾刪
void ListPopBack(LTNode* phead);
//頭插
void ListPushFront(LTNode* phead, LTDataType x);
//頭刪
void ListPopFront(LTNode* phead);
 
//在pos前插入資料
void ListInsert(LTNode* pos, LTDataType x);
//刪除pos處資料
void ListErase(LTNode* pos);

List.c 檔案

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//建立新節點
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc failn");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode; //返回新建立的節點
}
//初始化連結串列(二級指標版)
/*void ListInit(LTNode** pphead)
{
	//傳二級指標,那麼當然要斷言
	assert(pphead);
	*pphead = BuyLTNode(0);//因為是帶哨兵位的頭節點,所以一開始就要給一個節點
	//為了迴圈,要讓哨兵位的next和prev均指向自己
	(*pphead)->next = *pphead; //注意優先順序,*pphead要加括號
	(*pphead)->prev = *pphead;
}*/
//初始化連結串列(一級指標版)
LTNode* ListInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
 
//列印連結串列
void ListPrint(LTNode* phead)
{
	assert(phead);//斷言
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("n");
}
//連結串列查詢
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur; //找到就返回cur
		}
		cur = cur->next;
	}
	return NULL; //找不到就返回空
}
//銷燬連結串列
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	//銷燬從第一個節點到尾部的資料
	while (cur != phead)
	{
		LTNode* next = cur->next;
		//ListErase(cur);
		free(cur);
		cur = next;
	}
	//置空哨兵位節點phead
	free(phead);
	phead = NULL;
}
 
//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); //斷言,防止頭節點為空
	/*
	法一:
	LTNode* tail = phead->prev; //找到尾節點,便於後續插入資料
	LTNode* newnode = BuyLTNode(x);//建立新節點
	//將此新插入的尾節點與上一個節點連結起來
	tail->next = newnode;
	newnode->prev = tail;
	//將尾節點與哨兵位phead連結起來構成迴圈
	newnode->next = phead;
	phead->prev = newnode;
	*/
	//法二:
	ListInsert(phead, x);
}
//尾刪
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位,不能為空,要斷言
	assert(phead->next != phead); //防止連結串列為空,導致刪除哨兵位節點
	/*
	法一:
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	//釋放尾節點
	free(tail);
	tail = NULL;
	//將連結串列迴圈起來
	tailPrev->next = phead;
	phead->prev = tailPrev;
	*/
	//法二:
	ListErase(phead->prev);
}
 
//頭插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}
//頭刪
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); //防止刪除哨兵位節點
	ListErase(phead->next);
}
 
//在pos前插入資料
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	//建立插入資料的新節點
	LTNode* newnode = BuyLTNode(x);
	//連結左側
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	//連結右側
	newnode->next = pos;
	pos->prev = newnode;
}
//刪除pos處資料
void ListErase(LTNode* pos)
{
	assert(pos);
	//定義兩個指標儲存pos兩邊的節點
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	//將prev和next連結起來
	prev->next = next;
	next->prev = prev;
	//free釋放
	free(pos);
	pos = NULL;
}

Test.c 檔案

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void TestList1()
{
	//初始化(法一)
	/*LTNode* pList = NULL;
	ListInit(&pList);*/
	//初始化(法二)
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個資料
	}
	ListPrint(pList);//列印尾插的7個
}
 
void TestList2()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個資料
	}
	ListPrint(pList);//列印尾插的7個
	//尾刪兩次
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//再次列印
}
 
void TestList3()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個資料
	}
	ListPrint(pList);//列印尾插的7個
	//尋找數位
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListInsert(pos, 30); //找到數位3就插入
	}
	ListPrint(pList);//列印
}
 
void TestList4()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數位
	}
	ListPrint(pList);//列印
	for (int i = -2; i <= 0; i++)
	{
		ListPushFront(pList, i); //頭插3個數位
	}
	ListPrint(pList);//列印
}
 
void TestList5()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個資料
	}
	ListPrint(pList);//列印尾插的7個
	//尋找數位
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListErase(pos); //刪除pos處資料
		pos = NULL; //形參的改變不會影響實參,最好在這置空pos
	}
	ListPrint(pList);//列印
}
 
void TestList6()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數位
	}
	ListPrint(pList);//列印
	//頭插3個數位
	ListPushFront(pList, 0);
	ListPushFront(pList, -1);
	ListPushFront(pList, -2);
	ListPrint(pList);//列印
	//尾刪3個數位
	ListPopBack(pList);
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//列印
	//頭刪3個數位
	ListPopFront(pList);
	ListPopFront(pList);
	ListPopFront(pList);
	ListPrint(pList);//列印
	//銷燬連結串列
	ListDestory(pList);
	pList = NULL;
}
 
void TestList7()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7個數位
	}
	ListPrint(pList);//列印
	//銷燬連結串列
	ListDestory(pList);
	pList = NULL;
}
int main()
{
	//TestList1();
	//TestList2();
	//TestList3();
	//TestList4();
	//TestList5();
	//TestList6();
	TestList7();
	return 0;
}

五、拓展

對比順序表和連結串列

不同點順序表連結串列
儲存空間上物理上一定連續邏輯上連續,但物理上不一定連續
隨機存取支援O(1)不支援O(N)
任意位置插入或者刪除元素可能需要搬移元素,效率低O(N)只需修改指標指向
插入動態順序表,空間不夠時需要擴容沒有容量的概念
應用場景元素高效儲存+頻繁存取任意位置插入和刪除資料
快取利用率

優缺點對比:

 順序表連結串列
優點

1、物理空間是連續的,方便用下標隨機存取。

2、CPU快取記憶體命中率會更高。(補充)

1、按需申請釋放空間。

2、任意位置可以O(1)插入刪除資料。

缺點

1、正因為物理空間連續,空間不夠需要擴容,擴容本身又一定消耗,其次擴容機制還存在一定的空間浪費。

2、頭部或者中部插入刪除,挪動資料,效率低,O(N)。

1、不支援下標的隨機存取。

2、有些演演算法不適合在它上面進行,如:二分查詢、排序等。

到此這篇關於C語言超詳細講解資料結構中雙向帶頭回圈連結串列的文章就介紹到這了,更多相關C語言 雙向帶頭回圈連結串列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!


IT145.com E-mail:sddin#qq.com