前言

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

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

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

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

1.概念

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

（圖片來自比特就業(yè)課）

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

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

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

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

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

二、鏈表的使用

1.遍歷整個鏈表

代碼如下（示例）：

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

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

2.尾插

（圖片來自比特就業(yè)課）

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

void SListPushBack(SLTNode**pphead, SLTDataType x)
{
	SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//開辟一塊大小為一個SLTNode類型的空間出來，并強(qiáng)制轉(zhuǎn)換成結(jié)構(gòu)體指針賦給newnode
	newnode->data = x;
	newnode->next = NULL;
	if (*pphead == NULL)//防止一開始鏈表里面什么也沒有，
	{//由于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)存儲
	}
}

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

3.頭插

（圖片來自比特就業(yè)課）

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

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

void SListPushFront(SLTNode**pphead, SLTDataType x)
{
	SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//開辟一塊大小為一個SLTNode類型的空間出來，并強(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（對動態(tài)分配的內(nèi)存進(jìn)行釋放）掉，剩下的就是我們需要的鏈表。但這里會有一個問題，就是你把頭節(jié)點(diǎn)去了，因為鏈表是用地址連接的，我們原本是用頭節(jié)點(diǎn)地址找到該鏈表，現(xiàn)在頭節(jié)點(diǎn)去掉了，我們怎么知道剩下的鏈表在哪里。所以這里的解決方案是，先把第二個節(jié)點(diǎn)地址保存起來然后再釋放掉頭節(jié)點(diǎn)
代碼如下（示例）：

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

5.尾刪

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

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

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

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

上圖紅色是原有鏈表，我們要在2和3直接插入一個30怎么做？首先我們要把2、30、3這3個節(jié)點(diǎn)連接起來，也就是說，2節(jié)點(diǎn)要指向30這個節(jié)點(diǎn)，30這個節(jié)點(diǎn)要指向3這個節(jié)點(diǎn)。這里如何操作呢？我們需要設(shè)計一個函數(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)//給定鏈表中一個數(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個節(jié)點(diǎn)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode));
		//開辟一塊大小為一個SLTNode類型的空間出來，并強(qiáng)制轉(zhuǎn)換成結(jié)構(gòu)體指針賦給newnode
		newnode->data = x;
		newnode->next = NULL;//開辟1個新節(jié)點(diǎn)
		SLTNode*prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;//把新節(jié)點(diǎn)連接上去
	}
}

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

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

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

比如說我們現(xiàn)在要把3刪除，那這里就會出現(xiàn)一個需要：3刪除了，要把2和4連接起來，然后把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)用的時候，依然需要進(jìn)行find定位一下需要刪除位置地址

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

后記

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

最新評論