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

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)單鏈表接口函數(shù)全面講解教程

 更新時(shí)間:2021年10月22日 14:49:43   作者:高郵吳少  
這篇文章主要為大家介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)單鏈表所有接口函數(shù)的全面講解教程,有需要朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

前言

上一期數(shù)據(jù)結(jié)構(gòu)專欄我們學(xué)習(xí)了順序表后:C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)順序表

在運(yùn)用時(shí),細(xì)心的同學(xué)可能會(huì)發(fā)現(xiàn),如果要頭插、尾插或者任意位置。如果原先的空間已經(jīng)被占滿了,你是需要擴(kuò)容的,動(dòng)態(tài)鏈表擴(kuò)容往往是2倍,但是擴(kuò)容后,如果后面沒(méi)有使用完全擴(kuò)容后空間就會(huì)造成空間浪費(fèi),為了解決這個(gè)問(wèn)題,我們今天將學(xué)習(xí)鏈表。

提示:以下是本篇文章正文內(nèi)容,下面案例可供參考

一、鏈表的概念及結(jié)構(gòu)

1.概念

鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上的非連續(xù)。非順序的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

在這里插入圖片描述

(圖片來(lái)自比特就業(yè)課)

上圖是一個(gè)普通鏈表,它物理上是不連續(xù)的,那怎么讓這些數(shù)據(jù)建立聯(lián)系呢?鏈表每個(gè)位置會(huì)存放兩個(gè)數(shù)據(jù)——1個(gè)是數(shù)據(jù),另1個(gè)是指針

typedef int SLTDataType;//這里是方便將來(lái)改數(shù)據(jù)類型,在這里把int修改一下即可
typedef struct SlistNode//一個(gè)位置放多個(gè)數(shù)據(jù)用結(jié)構(gòu)體
{
	int data;
	struct SlistNode*next;//指針是指向下一個(gè)節(jié)點(diǎn),下一個(gè)節(jié)點(diǎn)也是結(jié)構(gòu)體,所以這里是結(jié)構(gòu)體指針

}SLTNode;//將結(jié)構(gòu)體類型名用SLTNode重命名

我們用一張圖來(lái)深入了解一下它的邏輯結(jié)構(gòu):

在這里插入圖片描述

圖示是鏈表的三個(gè)相連元素,第一個(gè)元素存放數(shù)據(jù)1和第二個(gè)元素的地址,然后以此類推。那到這里可能有同學(xué)會(huì)問(wèn):“那每個(gè)都是有存放下一個(gè)地址,最后一個(gè)節(jié)點(diǎn)存放誰(shuí)的地址?”是這樣的,最后一個(gè)節(jié)點(diǎn)存放的是NULL空指針,空指針也是作為鏈表結(jié)尾的標(biāo)記
到這里,我們知道,鏈表的每個(gè)節(jié)點(diǎn)放的是當(dāng)前節(jié)點(diǎn)內(nèi)容和下一個(gè)節(jié)點(diǎn)的指針,那我們?cè)趺凑业竭@條鏈表呢?畢竟你第一個(gè)節(jié)點(diǎn)放的是第二個(gè)節(jié)點(diǎn)的指針,事實(shí)上,我們會(huì)定義一個(gè)指針指向第一個(gè)節(jié)點(diǎn),以此來(lái)確定該鏈表

二、鏈表的使用

1.遍歷整個(gè)鏈表

代碼如下(示例):

void SListPrint(SLTNode*phead)
{
	SLTNode*cur = phead;
	while (cur != NULL)
	{
		printf("%d", cur->data);
		cur = cur->next;
	}
}

在這里插入圖片描述

我們以這張圖來(lái)理解一下這段代碼,我們創(chuàng)建一個(gè)結(jié)構(gòu)體指針cur,并把鏈表首元素地址賦給cur,也就是說(shuō),cur指向了鏈表的首節(jié)點(diǎn),我們知道首節(jié)點(diǎn)里是有第二個(gè)節(jié)點(diǎn)的地址的,我們通過(guò)cur = cur->next;可以找到第二段節(jié)點(diǎn),以此類推。

2.尾插

在這里插入圖片描述

(圖片來(lái)自比特就業(yè)課)

想要尾插一個(gè)節(jié)點(diǎn),我們首先要malloc(擴(kuò)容函數(shù))一塊空間出來(lái),開(kāi)辟出那塊空間之后,要把新節(jié)點(diǎn)與鏈表連接起來(lái),就需要鏈表尾部節(jié)點(diǎn)的地址,我們用循環(huán)遍歷得到,然后把新節(jié)點(diǎn)地址賦給之前鏈表的尾部節(jié)點(diǎn)即可
代碼如下(示例):

void SListPushBack(SLTNode**pphead, SLTDataType x)
{
	SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//開(kāi)辟一塊大小為一個(gè)SLTNode類型的空間出來(lái),并強(qiáng)制轉(zhuǎn)換成結(jié)構(gòu)體指針賦給newnode
	newnode->data = x;
	newnode->next = NULL;
	if (*pphead == NULL)//防止一開(kāi)始鏈表里面什么也沒(méi)有,
	{//由于pphead是頭節(jié)點(diǎn)的地址的地址,*解引用一下得到頭結(jié)點(diǎn)的地址
		*pphead = newnode;
	}
	else
	{
		SLTNode*tail = *pphead;
		while (tail->next != NULL)//尋找尾節(jié)點(diǎn)的指針
		{
			tail = tail->next;
		}
		tail->next = newnode;//新增的節(jié)點(diǎn)地址賦給尾結(jié)點(diǎn)存儲(chǔ)
	}
}

這里為什么用二級(jí)指針傳參?解釋如下:
我們進(jìn)行尾插時(shí),要先找到鏈表所在嘛,然后這個(gè)是靠鏈表頭節(jié)點(diǎn)地址確定的,你傳了一個(gè)地址過(guò)去,注意這個(gè)地址是實(shí)參,你實(shí)參過(guò)去函數(shù)里會(huì)再創(chuàng)建一個(gè)形參也是這個(gè)地址,然后進(jìn)行操作,改變的是形參里的東西,實(shí)參不會(huì)受影響。這里也就是傳值調(diào)用和傳址調(diào)用的區(qū)別,為了形參可以影響到實(shí)參,我們用傳址調(diào)用,也就是傳地址的地址

3.頭插

在這里插入圖片描述

(圖片來(lái)自比特就業(yè)課)

我們假設(shè)現(xiàn)在要在一個(gè)鏈表前面插入0這個(gè)數(shù)據(jù)(如上圖所示),0所在地址為0x0006708,那是不是要把原鏈表首節(jié)點(diǎn)地址放到0這個(gè)節(jié)點(diǎn)里面,然后頭節(jié)點(diǎn)地址更新為0這個(gè)新節(jié)點(diǎn)的地址。如下圖:

在這里插入圖片描述

ps:plist/phead表示鏈表首節(jié)點(diǎn)地址
代碼如下(示例):

void SListPushFront(SLTNode**pphead, SLTDataType x)
{
	SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//開(kāi)辟一塊大小為一個(gè)SLTNode類型的空間出來(lái),并強(qiáng)制轉(zhuǎn)換成結(jié)構(gòu)體指針賦給newnode
	newnode->data = x;//插入節(jié)點(diǎn)的數(shù)據(jù)
	newnode->next = *pphead;//把原先節(jié)點(diǎn)首元素地址賦給新節(jié)點(diǎn)
	*pphead = newnode;//新節(jié)點(diǎn)首元素地址用新插入的節(jié)點(diǎn)地址賦值
}

4.頭刪

關(guān)于頭刪,很多同學(xué)可能有一種想法,就是直接把頭結(jié)點(diǎn)free(對(duì)動(dòng)態(tài)分配的內(nèi)存進(jìn)行釋放)掉,剩下的就是我們需要的鏈表。但這里會(huì)有一個(gè)問(wèn)題,就是你把頭節(jié)點(diǎn)去了,因?yàn)殒湵硎怯玫刂愤B接的,我們?cè)臼怯妙^節(jié)點(diǎn)地址找到該鏈表,現(xiàn)在頭節(jié)點(diǎn)去掉了,我們?cè)趺粗朗O碌逆湵碓谀睦?。所以這里的解決方案是,先把第二個(gè)節(jié)點(diǎn)地址保存起來(lái)然后再釋放掉頭節(jié)點(diǎn)
代碼如下(示例):

void SListPopFront(SLTNode**pphead)
{
	SLTNode*next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

5.尾刪

尾刪和頭刪有同樣的問(wèn)題,我們能不能直接把尾部節(jié)點(diǎn)給free掉?答案也是不可以的,同學(xué)你細(xì)想一下,尾部節(jié)點(diǎn)是不是連接著倒數(shù)第二個(gè)節(jié)點(diǎn),而倒數(shù)第二個(gè)節(jié)點(diǎn)保存著尾結(jié)點(diǎn)地址,你把尾結(jié)點(diǎn)free掉了,那倒數(shù)第二個(gè)節(jié)點(diǎn)保存的就是野指針了,這顯然是不行的,所以我們需要把倒數(shù)第二個(gè)節(jié)點(diǎn)存儲(chǔ)的指針變成空指針,然后free掉尾結(jié)點(diǎn)

void SListPopBack(SLTNode**pphead)
{
	if (*pphead == NULL)//如果節(jié)點(diǎn)本來(lái)就沒(méi)有,那就沒(méi)有刪除的說(shuō)法了
	{
		return;
	}
	else if ((*pphead)->next == NULL)//如果本來(lái)鏈表只有一個(gè)節(jié)點(diǎn),你刪除一個(gè),之前會(huì)有一個(gè)指針指向首節(jié)點(diǎn)來(lái)記錄這個(gè)鏈表,你現(xiàn)在把唯一的節(jié)點(diǎn)刪除了,那個(gè)記錄鏈表的指針就成野指針了
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode*prev = NULL;//prev為tail前個(gè)節(jié)點(diǎn)指針
		SLTNode*tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

這里還是有注意的點(diǎn)的,比如你要?jiǎng)h除的鏈表本來(lái)就是空鏈表,刪除就無(wú)從談起了,還有就是原先鏈表只有一個(gè)節(jié)點(diǎn),你刪除一個(gè),之前會(huì)有一個(gè)指針指向首節(jié)點(diǎn)來(lái)記錄這個(gè)鏈表,你現(xiàn)在把唯一的節(jié)點(diǎn)刪除了,那個(gè)記錄鏈表的指針就成野指針了

6.任意位置插入數(shù)據(jù)

在這里插入圖片描述

上圖紅色是原有鏈表,我們要在2和3直接插入一個(gè)30怎么做?首先我們要把2、30、3這3個(gè)節(jié)點(diǎn)連接起來(lái),也就是說(shuō),2節(jié)點(diǎn)要指向30這個(gè)節(jié)點(diǎn),30這個(gè)節(jié)點(diǎn)要指向3這個(gè)節(jié)點(diǎn)。這里如何操作呢?我們需要設(shè)計(jì)一個(gè)函數(shù)先找到2節(jié)點(diǎn)和3節(jié)點(diǎn)的地址,然后進(jìn)行插入操作
查找函數(shù)和插入函數(shù)如下

SLTNode* SListFind(SLTNode*phead, SLTDataType x)//查找鏈表
{
	SLTNode*cur = phead;
	while (cur)//非空指針則進(jìn)行循環(huán)
	{
		if (cur->data == x)//給定鏈表中一個(gè)數(shù)據(jù)進(jìn)行查找
		{
			return cur;//返回所查找位置指針
		}
		cur = cur->next;
	}
	return NULL;
}
void SListInsert(SLTNode**pphead,SLTNode*pos, SLTDataType x)//在pos前插入x,x是要插入的數(shù)
{
	if (pos == *pphead)//原鏈表只有1個(gè)節(jié)點(diǎn)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode));
		//開(kāi)辟一塊大小為一個(gè)SLTNode類型的空間出來(lái),并強(qiáng)制轉(zhuǎn)換成結(jié)構(gòu)體指針賦給newnode
		newnode->data = x;
		newnode->next = NULL;//開(kāi)辟1個(gè)新節(jié)點(diǎn)
		SLTNode*prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;//把新節(jié)點(diǎn)連接上去
	}
}

兩個(gè)函數(shù)一起調(diào)用是這樣的

if (pos)//防止該位置是空指針
	{
		SlistInsert(&plist, pos, 30);
	}
	SListPrint(&plist);
}

7.任意位置刪除數(shù)據(jù)

在這里插入圖片描述

比如說(shuō)我們現(xiàn)在要把3刪除,那這里就會(huì)出現(xiàn)一個(gè)需要:3刪除了,要把2和4連接起來(lái),然后把3節(jié)點(diǎn)釋放掉

void SListErase(SLTNode**pphead, SLTNode*pos)//刪除pos位置的值
{
	SLTNode*prev = *pphead;
	while (prev->next != pos)//找到3節(jié)點(diǎn)的位置
	{
		prev = prev->next;
	}
	prev->next = pos->next;//prev是2,pos是3,pos->next是4,要把4接上2
	free(pos);//2和4接上之后就可以free掉3了
}

ps:上述prev是2,pos是3這種是方便同學(xué)你理解,并不特指它真的是2和3

然后這里進(jìn)行函數(shù)調(diào)用的時(shí)候,依然需要進(jìn)行find定位一下需要?jiǎng)h除位置地址

SLTNode*pos = SListFind(plist, 3);
	if (pos)//防止該位置是空指針
	{
		SListErase(&plist, pos);
	}

后記

鏈表是數(shù)據(jù)結(jié)構(gòu)非常重要的一塊知識(shí),本文著重介紹了鏈表的接口函數(shù),下一期筆者會(huì)更新特殊鏈表的使用,點(diǎn)贊三連可以加快更新速度哦~更多關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)單鏈表接口函數(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • 深入理解C語(yǔ)言指針

    深入理解C語(yǔ)言指針

    關(guān)于指針,其是C語(yǔ)言的重點(diǎn),C語(yǔ)言學(xué)的好壞,其實(shí)就是指針學(xué)的好壞。其實(shí)指針并不復(fù)雜,學(xué)習(xí)指針,要正確的理解指針
    2020-02-02
  • C語(yǔ)言strlen,strcpy,strcmp,strcat,strstr字符串操作函數(shù)實(shí)現(xiàn)

    C語(yǔ)言strlen,strcpy,strcmp,strcat,strstr字符串操作函數(shù)實(shí)現(xiàn)

    這篇文章主要介紹了C語(yǔ)言strlen,strcpy,strcmp,strcat,strstr字符串操作函數(shù)實(shí)現(xiàn),,文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,需要的朋友可以參考一下
    2022-09-09
  • C語(yǔ)言實(shí)現(xiàn)猜拳游戲

    C語(yǔ)言實(shí)現(xiàn)猜拳游戲

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)猜拳游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-02-02
  • OpenCV實(shí)現(xiàn)低對(duì)比度圖像臟污區(qū)域檢測(cè)

    OpenCV實(shí)現(xiàn)低對(duì)比度圖像臟污區(qū)域檢測(cè)

    本文主要介紹了OpenCV實(shí)現(xiàn)低對(duì)比度圖像臟污區(qū)域檢測(cè),文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-09-09
  • C語(yǔ)言進(jìn)階之文件操作詳解

    C語(yǔ)言進(jìn)階之文件操作詳解

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言進(jìn)階之文件操作,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助
    2022-02-02
  • C++20 新特性 協(xié)程 Coroutines(2)

    C++20 新特性 協(xié)程 Coroutines(2)

    上篇文章簡(jiǎn)單給大介紹了 C++20 特性 協(xié)程 Coroutines co_yield 和 co_return 那么這篇文章繼續(xù)給大家介紹C++20 的新特性協(xié)程 Coroutines co_await,需要的朋友可以參考一下
    2021-10-10
  • 詳解C語(yǔ)言處理算經(jīng)中著名問(wèn)題百錢(qián)百雞

    詳解C語(yǔ)言處理算經(jīng)中著名問(wèn)題百錢(qián)百雞

    古代的很多數(shù)學(xué)問(wèn)題都可以用現(xiàn)代的編程語(yǔ)言去嘗試解決,就如本篇,將會(huì)帶你通過(guò)C語(yǔ)言來(lái)解決算經(jīng)中百錢(qián)百雞問(wèn)題,感興趣的朋友來(lái)看看吧
    2022-02-02
  • 最新VScode C/C++ 環(huán)境配置的詳細(xì)教程

    最新VScode C/C++ 環(huán)境配置的詳細(xì)教程

    這篇文章主要介紹了最新VScode C/C++ 環(huán)境配置的詳細(xì)教程,本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-11-11
  • 一文帶你掌握C++中的繼承

    一文帶你掌握C++中的繼承

    繼承機(jī)制是面向?qū)ο蟪绦蛟O(shè)計(jì)使代碼可以復(fù)用的最重要的手段,它允許程序員在保持原有類特性的基礎(chǔ)上進(jìn)行擴(kuò)展,增加功能,本文詳解介紹了C++中的繼承,感興趣的同學(xué)可以借鑒一下
    2023-05-05
  • C語(yǔ)言實(shí)現(xiàn)頁(yè)面置換算法(FIFO、LRU)

    C語(yǔ)言實(shí)現(xiàn)頁(yè)面置換算法(FIFO、LRU)

    這篇文章主要介紹了通過(guò)C語(yǔ)言實(shí)現(xiàn)的兩種頁(yè)面置換算法:先進(jìn)先出(FIFO)頁(yè)面置換算法和最近最久未使用(LRU)頁(yè)面置換算法。文中的代碼具有一定的學(xué)習(xí)或工作價(jià)值,快來(lái)跟隨小編學(xué)習(xí)一下吧
    2021-12-12

最新評(píng)論