欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語(yǔ)言超詳細(xì)講解雙向帶頭循環(huán)鏈表

 更新時(shí)間:2023年02月14日 14:04:28   作者:[Pokemon]大貓貓  
帶頭雙向循環(huán)鏈表:結(jié)構(gòu)最復(fù)雜,一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu),都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜,但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來(lái)很多優(yōu)勢(shì),實(shí)現(xiàn)反而簡(jiǎn)單

在上一篇所講述的單鏈表中,存在一些缺陷:

1、在進(jìn)行尾插和尾刪時(shí),需要遍歷鏈表找到尾結(jié)點(diǎn)

2、在進(jìn)行中間插入和刪除時(shí),也需要先遍歷鏈表找到前一個(gè)結(jié)點(diǎn)

對(duì)于這些缺陷,可以采用一種結(jié)構(gòu)更為復(fù)雜的鏈表 雙向帶頭循環(huán)鏈表

雙向帶頭循環(huán)鏈表結(jié)構(gòu)雖然復(fù)雜,但在鏈表的操作上帶來(lái)了很大的優(yōu)勢(shì)

一、雙向帶頭循環(huán)鏈表的結(jié)構(gòu)

//存儲(chǔ)數(shù)據(jù)的類型,這里以 int 來(lái)舉例
typedef int LTDataType;
//結(jié)點(diǎn)的類型
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

二、雙向帶頭循環(huán)鏈表的函數(shù)接口

1. 申請(qǐng)結(jié)點(diǎn)

在插入等操作時(shí)需要申請(qǐng)結(jié)點(diǎn),為了避免麻煩重復(fù)的操作,這里將申請(qǐng)結(jié)點(diǎn)封裝為一個(gè)函數(shù)

申請(qǐng)結(jié)點(diǎn)函數(shù)如下:

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		//開(kāi)辟空間失敗,打印錯(cuò)誤信息
		perror("malloc");

		//結(jié)束程序
		exit(-1);
	}
	newnode->data = x;
	newnode->prev = newnode->next = NULL;
	return newnode;
}

2. 初識(shí)化

在雙向帶頭循環(huán)鏈表中,即使沒(méi)有存儲(chǔ)數(shù)據(jù)也 至少會(huì)包含一個(gè)哨兵位的頭結(jié)點(diǎn)

初始化函數(shù)如下:

LTNode* InitLT()
{
	//申請(qǐng)頭結(jié)點(diǎn),頭結(jié)點(diǎn)的數(shù)據(jù)存什么無(wú)關(guān)緊要
	LTNode* phead = BuyLTNode(-1);
	//改變指針指向,構(gòu)成循環(huán)
	phead->prev = phead->next = phead;
	return phead;
}

3. 打印

為了驗(yàn)證插入、刪除等得到的結(jié)果是否正確,提供打印函數(shù),這里數(shù)據(jù)類型以 int 為例,當(dāng)讀者采用的類型不同時(shí),自行更改函數(shù)即可

打印函數(shù)如下:

void LTPrint(LTNode* phead)
{
	//鏈表不能為空
	assert(phead);
	LTNode* cur = phead->next;
	printf("head->");
	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("head\n");
}

4. 尾插尾刪

尾插:在鏈表的最后一個(gè)結(jié)點(diǎn)之后插入結(jié)點(diǎn)

尾插函數(shù)如下:

void LTPushBack(LTNode* phead, LTDataType x)
{
	//鏈表不能為空
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	//找到尾結(jié)點(diǎn)
	LTNode* tail = phead->prev;
	//改變指針指向
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

尾刪:刪除鏈表最后一個(gè)結(jié)點(diǎn)

尾刪函數(shù)如下:

void LTPopBack(LTNode* phead)
{
	assert(phead);	//鏈表不能為空
	assert(phead->next != phead);	//空鏈表不能刪
	//找尾結(jié)點(diǎn)及尾結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	//改變指針指向
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
}

5. 頭插頭刪

頭插: 在第一個(gè)結(jié)點(diǎn)之前插入新結(jié)點(diǎn)

頭插函數(shù)如下:

void LTPushFront(LTNode* phead, LTDataType x)
{
	//鏈表不能為空
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	//找到頭結(jié)點(diǎn)后的第一個(gè)結(jié)點(diǎn)
	LTNode* first = phead->next;
	//改變指針指向
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

頭刪:刪除鏈表的第一個(gè)結(jié)點(diǎn)

頭刪函數(shù)如下:

void LTPopFront(LTNode* phead)
{
	assert(phead);	//鏈表不能為空
	assert(phead->next != phead);	//空鏈表不能刪
	//找到頭結(jié)點(diǎn)后的第一個(gè)和第二個(gè)結(jié)點(diǎn)
	LTNode* first = phead->next;
	LTNode* second = first->next;
	//改變指針指向
	phead->next = second;
	second->prev = phead;
	free(first);
}

6. 查找

查找:如果數(shù)據(jù)存在,返回該數(shù)據(jù)結(jié)點(diǎn)的指針,不存在返回 NULL

查找函數(shù)如下:

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	//鏈表不能為空
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x) return cur;
		cur = cur->next;
	}
	return NULL;
}

7. 中間插入和刪除

中間插入:通過(guò)查找函數(shù) LTFind 獲得指向結(jié)點(diǎn)的指針 pos,在 pos 指向的 結(jié)點(diǎn)之前 插入結(jié)點(diǎn)

在 pos 之前插入結(jié)點(diǎn)函數(shù)如下:

void LTInsert(LTNode* pos, LTDataType x)
{
	//pos 不能為空
	assert(pos);
	LTNode* newnode = BuyLTNode(x);
	//找到 pos 的前一個(gè)結(jié)點(diǎn)
	LTNode* posPrev = pos->prev;
	//改變指針指向
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

在調(diào)用中間插入函數(shù) LTInsert 時(shí)

  • 如果在鏈表頭結(jié)點(diǎn)之前插入數(shù)據(jù),便和尾插函數(shù)的功能一樣
  • 如果在鏈表頭結(jié)點(diǎn)之后插入數(shù)據(jù),便和頭插函數(shù)的功能一樣

因此在尾插和頭插函數(shù)的實(shí)現(xiàn)中可以直接調(diào)用中間插入函數(shù) LTInsert

尾插和頭插函數(shù)更改如下:

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	//鏈表不能為空
	assert(phead);
	LTInsert(phead, x);
}
//頭插
void LTPushFront(LTNode* phead, LTDataType x)
{
	//鏈表不能為空
	assert(phead);
	LTInsert(phead->next, x);
}

中間刪除:通過(guò)查找函數(shù) LTFind 獲得指向結(jié)點(diǎn)的指針 pos,刪除 pos 指向的結(jié)點(diǎn)

刪除 pos 指向的結(jié)點(diǎn)函數(shù)如下:

void LTErase(LTNode* pos)
{
	//pos 不能為空
	assert(pos);
	//找到 pos 的前一個(gè)和后一個(gè)結(jié)點(diǎn)
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	//改變指針指向
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

在調(diào)用中間刪除函數(shù) LTErase 時(shí)

  • 如果刪除鏈表頭結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn),便和尾刪函數(shù)的功能一樣
  • 如果刪除鏈表頭結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn),便和頭刪函數(shù)的功能一樣

因此在尾刪和頭刪函數(shù)的實(shí)現(xiàn)中可以直接調(diào)用中間刪除函數(shù) LTErase

尾刪和頭刪函數(shù)更改如下:

//尾刪
void LTPopBack(LTNode* phead)
{
	assert(phead);	//鏈表不能為空
	assert(phead->next != phead);	//空鏈表不能刪
	LTErase(phead->prev);
}
//頭刪
void LTPopFront(LTNode* phead)
{
	assert(phead);	//鏈表不能為空
	assert(phead->next != phead);	//空鏈表不能刪
	LTErase(phead->next);
}

8. 判空及求鏈表長(zhǎng)度

判空:判斷鏈表是否為空

判空函數(shù)如下:

bool LTEmpty(LTNode* phead)
{
	//鏈表不能為空
	assert(phead);
	return phead->next == phead;
}

鏈表長(zhǎng)度:鏈表有效數(shù)據(jù)個(gè)數(shù)

鏈表長(zhǎng)度函數(shù)如下:

size_t LTSize(LTNode* phead)
{
	//鏈表不能為空
	assert(phead);
	size_t size = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

9. 銷毀單鏈表

在鏈表中,存儲(chǔ)數(shù)據(jù)的結(jié)點(diǎn)是由自己開(kāi)辟的,當(dāng)不使用鏈表時(shí),應(yīng)將其銷毀

銷毀鏈表函數(shù)如下:

void LTDestroy(LTNode* phead)
{
	//鏈表不能為空
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* curNext = cur->next;
		free(cur);
		cur = curNext;
	}
	free(phead);
}

到此這篇關(guān)于C語(yǔ)言超詳細(xì)講解雙向帶頭循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C語(yǔ)言雙向帶頭循環(huán)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C++入門(mén)教程詳解之命名空間、函數(shù)重載、缺省參數(shù)

    C++入門(mén)教程詳解之命名空間、函數(shù)重載、缺省參數(shù)

    這篇文章主要介紹了C++入門(mén)教程詳解之命名空間、函數(shù)重載、缺省參數(shù),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2023-06-06
  • 求子數(shù)組最大和的實(shí)例代碼

    求子數(shù)組最大和的實(shí)例代碼

    求子數(shù)組最大和的實(shí)例代碼,需要的朋友可以參考一下
    2013-03-03
  • CreateCompatibleDC()函數(shù)案例詳解

    CreateCompatibleDC()函數(shù)案例詳解

    這篇文章主要介紹了CreateCompatibleDC()函數(shù)案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-08-08
  • Matlab計(jì)算變異函數(shù)并繪制經(jīng)驗(yàn)半方差圖詳解

    Matlab計(jì)算變異函數(shù)并繪制經(jīng)驗(yàn)半方差圖詳解

    這篇文章主要為大家詳細(xì)介紹了基于MATLAB求取空間數(shù)據(jù)的變異函數(shù),并繪制經(jīng)驗(yàn)半方差圖的方法。文中的示例代碼講解詳細(xì),感興趣的可以了解一下
    2023-04-04
  • C++與Lua協(xié)程交互的示例詳解

    C++與Lua協(xié)程交互的示例詳解

    Lua 語(yǔ)言不支持真正的多線程,即不支持共享內(nèi)存的搶占式線程,在執(zhí)行協(xié)程體的 Lua 腳本時(shí),Lua 同樣可以調(diào)用 C++ 的函數(shù),本文給大家介紹了C++ 與 Lua 的協(xié)程交互,需要的朋友可以參考下
    2024-02-02
  • C++使用GDAL庫(kù)實(shí)現(xiàn)Tiff文件的讀取

    C++使用GDAL庫(kù)實(shí)現(xiàn)Tiff文件的讀取

    這篇文章主要為大家詳細(xì)介紹了C++使用GDAL庫(kù)實(shí)現(xiàn)Tiff文件的讀取的相關(guān)知識(shí),文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2023-03-03
  • C++設(shè)計(jì)模式之CRTP的使用

    C++設(shè)計(jì)模式之CRTP的使用

    CRTP全稱是curious?recurring?template?pattern,即奇異遞歸模版模式,是一種c++的設(shè)計(jì)模式,精巧地結(jié)合了繼承和模板編程的技術(shù),下面就跟隨小編一起來(lái)學(xué)習(xí)一下CRTP的使用吧
    2023-10-10
  • 內(nèi)部排序之堆排序的實(shí)現(xiàn)詳解

    內(nèi)部排序之堆排序的實(shí)現(xiàn)詳解

    本篇文章是對(duì)堆排序的實(shí)現(xiàn)進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • C++私有繼承(二)

    C++私有繼承(二)

    這篇文章主要介紹了C++私有繼承,在私有繼承時(shí),基類的公有對(duì)象以及保護(hù)對(duì)象會(huì)變成派生類的私有對(duì)象。我們可以在派生類方法當(dāng)中使用它,但無(wú)法通過(guò)派生類對(duì)象直接調(diào)用,但無(wú)法訪問(wèn)基類的私有方法和對(duì)象,下面具體內(nèi)容,需要的朋友可以參考一下
    2022-01-01
  • c++中八大排序算法

    c++中八大排序算法

    本篇文章主要介紹了八大排序算法,詳細(xì)的介紹了八個(gè)算法思想,實(shí)現(xiàn)代碼,穩(wěn)定性,時(shí)間復(fù)雜度等,具有一定的參考價(jià)值,有需要的可以了解一下。
    2016-11-11

最新評(píng)論