C語言數據結構單鏈表接口函數全面講解教程

Posted on by

前言

上一期數據結構專欄我們學習瞭順序表後，在運用時，細心的同學可能會發現，如果要頭插、尾插或者任意位置。如果原先的空間已經被占滿瞭，你是需要擴容的，動態鏈表擴容往往是2倍，但是擴容後，如果後面沒有使用完全擴容後空間就會造成空間浪費，為瞭解決這個問題，我們今天將學習鏈表。

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

一、鏈表的概念及結構

1.概念

鏈表是一種物理存儲結構上的非連續。非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。

在這裡插入圖片描述

（圖片來自比特就業課）

上圖是一個普通鏈表，它物理上是不連續的，那怎麼讓這些數據建立聯系呢？鏈表每個位置會存放兩個數據——1個是數據，另1個是指針

typedef int SLTDataType;//這裡是方便將來改數據類型，在這裡把int修改一下即可
typedef struct SlistNode//一個位置放多個數據用結構體
{
	int data;
	struct SlistNode*next;//指針是指向下一個節點，下一個節點也是結構體，所以這裡是結構體指針

}SLTNode;//將結構體類型名用SLTNode重命名

我們用一張圖來深入瞭解一下它的邏輯結構：

在這裡插入圖片描述

圖示是鏈表的三個相連元素，第一個元素存放數據1和第二個元素的地址，然後以此類推。那到這裡可能有同學會問：“那每個都是有存放下一個地址，最後一個節點存放誰的地址？”是這樣的，最後一個節點存放的是NULL空指針，空指針也是作為鏈表結尾的標記
到這裡，我們知道，鏈表的每個節點放的是當前節點內容和下一個節點的指針，那我們怎麼找到這條鏈表呢？畢竟你第一個節點放的是第二個節點的指針，事實上，我們會定義一個指針指向第一個節點，以此來確定該鏈表

二、鏈表的使用

1.遍歷整個鏈表

代碼如下（示例）：

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

在這裡插入圖片描述

我們以這張圖來理解一下這段代碼，我們創建一個結構體指針cur，並把鏈表首元素地址賦給cur，也就是說，cur指向瞭鏈表的首節點，我們知道首節點裡是有第二個節點的地址的，我們通過cur = cur->next;可以找到第二段節點，以此類推。

2.尾插

在這裡插入圖片描述

（圖片來自比特就業課）

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

void SListPushBack(SLTNode**pphead, SLTDataType x)
{
	SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//開辟一塊大小為一個SLTNode類型的空間出來，並強制轉換成結構體指針賦給newnode
	newnode->data = x;
	newnode->next = NULL;
	if (*pphead == NULL)//防止一開始鏈表裡面什麼也沒有，
	{//由於pphead是頭節點的地址的地址，*解引用一下得到頭結點的地址
		*pphead = newnode;
	}
	else
	{
		SLTNode*tail = *pphead;
		while (tail->next != NULL)//尋找尾節點的指針
		{
			tail = tail->next;
		}
		tail->next = newnode;//新增的節點地址賦給尾結點存儲
	}
}

這裡為什麼用二級指針傳參？解釋如下：
我們進行尾插時，要先找到鏈表所在嘛，然後這個是靠鏈表頭節點地址確定的，你傳瞭一個地址過去，註意這個地址是實參，你實參過去函數裡會再創建一個形參也是這個地址，然後進行操作，改變的是形參裡的東西，實參不會受影響。這裡也就是傳值調用和傳址調用的區別，為瞭形參可以影響到實參，我們用傳址調用，也就是傳地址的地址

3.頭插

在這裡插入圖片描述

（圖片來自比特就業課）

我們假設現在要在一個鏈表前面插入0這個數據（如上圖所示），0所在地址為0x0006708，那是不是要把原鏈表首節點地址放到0這個節點裡面，然後頭節點地址更新為0這個新節點的地址。如下圖：

在這裡插入圖片描述

ps:plist/phead表示鏈表首節點地址
代碼如下（示例）：

void SListPushFront(SLTNode**pphead, SLTDataType x)
{
	SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//開辟一塊大小為一個SLTNode類型的空間出來，並強制轉換成結構體指針賦給newnode
	newnode->data = x;//插入節點的數據
	newnode->next = *pphead;//把原先節點首元素地址賦給新節點
	*pphead = newnode;//新節點首元素地址用新插入的節點地址賦值
}

4.頭刪

關於頭刪，很多同學可能有一種想法，就是直接把頭結點free（對動態分配的內存進行釋放）掉，剩下的就是我們需要的鏈表。但這裡會有一個問題，就是你把頭節點去瞭，因為鏈表是用地址連接的，我們原本是用頭節點地址找到該鏈表，現在頭節點去掉瞭，我們怎麼知道剩下的鏈表在哪裡。所以這裡的解決方案是，先把第二個節點地址保存起來然後再釋放掉頭節點
代碼如下（示例）：

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

5.尾刪

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

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

這裡還是有註意的點的，比如你要刪除的鏈表本來就是空鏈表，刪除就無從談起瞭，還有就是原先鏈表隻有一個節點，你刪除一個，之前會有一個指針指向首節點來記錄這個鏈表，你現在把唯一的節點刪除瞭，那個記錄鏈表的指針就成野指針瞭

6.任意位置插入數據

在這裡插入圖片描述

上圖紅色是原有鏈表，我們要在2和3直接插入一個30怎麼做？首先我們要把2、30、3這3個節點連接起來，也就是說，2節點要指向30這個節點，30這個節點要指向3這個節點。這裡如何操作呢？我們需要設計一個函數先找到2節點和3節點的地址，然後進行插入操作
查找函數和插入函數如下

SLTNode* SListFind(SLTNode*phead, SLTDataType x)//查找鏈表
{
	SLTNode*cur = phead;
	while (cur)//非空指針則進行循環
	{
		if (cur->data == x)//給定鏈表中一個數據進行查找
		{
			return cur;//返回所查找位置指針
		}
		cur = cur->next;
	}
	return NULL;
}
void SListInsert(SLTNode**pphead,SLTNode*pos, SLTDataType x)//在pos前插入x，x是要插入的數
{
	if (pos == *pphead)//原鏈表隻有1個節點
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode));
		//開辟一塊大小為一個SLTNode類型的空間出來，並強制轉換成結構體指針賦給newnode
		newnode->data = x;
		newnode->next = NULL;//開辟1個新節點
		SLTNode*prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;//把新節點連接上去
	}
}

兩個函數一起調用是這樣的

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

7.任意位置刪除數據

在這裡插入圖片描述

比如說我們現在要把3刪除，那這裡就會出現一個需要：3刪除瞭，要把2和4連接起來，然後把3節點釋放掉

void SListErase(SLTNode**pphead, SLTNode*pos)//刪除pos位置的值
{
	SLTNode*prev = *pphead;
	while (prev->next != pos)//找到3節點的位置
	{
		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這種是方便同學你理解，並不特指它真的是2和3

然後這裡進行函數調用的時候，依然需要進行find定位一下需要刪除位置地址

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

後記

鏈表是數據結構非常重要的一塊知識，本文著重介紹瞭鏈表的接口函數，下一期筆者會更新特殊鏈表的使用，點贊三連可以加快更新速度哦~更多關於C語言數據結構單鏈表接口函數的資料請關註WalkonNet其它相關文章！

推薦閱讀：