C語(yǔ)言?超詳細(xì)模擬實(shí)現(xiàn)單鏈表的基本操作建議收藏

更新時(shí)間：2022年03月30日 16:59:17 作者：鹿九丸

單鏈表是后面要學(xué)的雙鏈表以及循環(huán)鏈表的基礎(chǔ)，要想繼續(xù)深入了解數(shù)據(jù)結(jié)構(gòu)以及C語(yǔ)言，我們就要奠定好這塊基石！接下來(lái)就和我一起學(xué)習(xí)吧

3.1 鏈表的定義
3.2 鏈表數(shù)據(jù)的打印
3.3 鏈表的尾插
3.4 鏈表空間的動(dòng)態(tài)申請(qǐng)
3.5 鏈表的頭插
3.6 鏈表的尾刪
3.7 鏈表的頭刪
3.8 鏈表任意位置的前插入
3.9 鏈表任意位置的后插入
3.10 鏈表的任意位置的刪除
3.11 鏈表的任意位置的前刪除
3.12 鏈表的任意位置的后刪除
3.13 鏈表的銷(xiāo)毀
3.14 鏈表的總結(jié)

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

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

注意：

1. 從上圖可以看出，鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上不一定是連續(xù)

2. 現(xiàn)實(shí)中的節(jié)點(diǎn)一般是從堆上申請(qǐng)出來(lái)的

3. 從對(duì)上申請(qǐng)的空間，是按照一定的策略來(lái)分配的，兩次申請(qǐng)的空間可能連續(xù)，也可能不連續(xù)

2 鏈表的分類(lèi)

實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來(lái)就有8種鏈表結(jié)構(gòu)：

1、單向或者雙向鏈表

2、帶頭或者不帶頭鏈表

3、循環(huán)或非循環(huán)鏈表

最常用的有兩種：無(wú)頭單向非循環(huán)鏈表、帶頭雙向循環(huán)鏈表

無(wú)頭單向非循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié) 構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
帶頭雙向循環(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)單了，后面我們代碼實(shí)現(xiàn)了就知道了。

3 鏈表的實(shí)現(xiàn)無(wú)頭+單向+非循環(huán)鏈表增刪查改實(shí)現(xiàn)

3.1 鏈表的定義

typedef int SLTDataType;//
typedef struct SListNode
{
	int data;//val，存儲(chǔ)的數(shù)據(jù)，此處假設(shè)存儲(chǔ)的數(shù)據(jù)為int型
	struct SListNode* next;//存儲(chǔ)下一個(gè)節(jié)點(diǎn)的位置
}SListNode,SLN;

3.2 鏈表數(shù)據(jù)的打印

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

3.3 鏈表的尾插

void SListPushBack(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

在找尾的過(guò)程中，務(wù)必不能寫(xiě)成下面的代碼：

while(tail!=NULL)
{
	tail = tail->next;
}
tail->next = newnode;

當(dāng)然，上面的介紹的是尾刪的情況。

尾插其實(shí)也是類(lèi)似的，尾插的話像上面的代碼中，當(dāng)tail!=NULL不成立之后，tail等于空，然后執(zhí)行賦值操作，tail->next = newnode這行代碼相當(dāng)于下面的代碼：

(*tail).next，此處相當(dāng)于是對(duì)空指針進(jìn)行解引用，其實(shí)就是非法訪問(wèn)了，并還試圖非法修改未授權(quán)內(nèi)存中的數(shù)據(jù)，這將必然會(huì)引發(fā)程序的崩潰。而且也并沒(méi)有將新節(jié)點(diǎn)的地址存儲(chǔ)到之前為節(jié)點(diǎn)的next中。

這個(gè)地方需要弄明白鏈表進(jìn)行遍歷的根本原理：

鏈表是一個(gè)相對(duì)靜態(tài)的存儲(chǔ)在堆區(qū)中的數(shù)據(jù)空間，我們通過(guò)改變棧區(qū)中的局部變量tail中的數(shù)據(jù)（即每一個(gè)鏈表節(jié)點(diǎn)的地址）來(lái)進(jìn)行遍歷，之所以能夠通過(guò)tail變量能夠進(jìn)行訪問(wèn)并且修改節(jié)點(diǎn)數(shù)據(jù)的原因就是因?yàn)閠ail的數(shù)據(jù)類(lèi)型是SListNode*，即指向節(jié)點(diǎn)的指針，指針的類(lèi)型決定了對(duì)指針解引用能夠訪問(wèn)的數(shù)據(jù)類(lèi)型，所以*tail能夠訪問(wèn)堆區(qū)中的節(jié)點(diǎn)的數(shù)據(jù)并且能夠進(jìn)行修改。

3.4 鏈表空間的動(dòng)態(tài)申請(qǐng)

SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	return newnode;
}

3.5 鏈表的頭插

void SListPushFront(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

3.6 鏈表的尾刪

需要考慮三種情況：

空
一個(gè)節(jié)點(diǎn)
多個(gè)節(jié)點(diǎn)

兩種寫(xiě)法：

第一種：

void SListPopBack(SListNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)//空鏈表
	{
		return;
	}
	else if ((*pphead)->next == NULL)//一個(gè)節(jié)點(diǎn)
	{
		free(*pphead);//*pphead就是plist的值
		*pphead = NULL;
	}
	else//多個(gè)節(jié)點(diǎn)
	{
		SListNode* tail = *pphead;
		SListNode* prev = NULL;//為什么要置為空呢？因?yàn)檫@個(gè)地方相當(dāng)于是指向第一個(gè)節(jié)點(diǎn)之前的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)并不存在，設(shè)為空
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

這種方式在面對(duì)只有一個(gè)節(jié)點(diǎn)時(shí)也不會(huì)出現(xiàn)問(wèn)題。

第二種：

void SListPopBack(SListNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)//空鏈表
	{
		return;
	}
	else if ((*pphead)->next == NULL)//一個(gè)節(jié)點(diǎn)
	{
		free(*pphead);//*pphead就是plist的值
		*pphead = NULL;
	}
	else//多個(gè)節(jié)點(diǎn)
	{
		SListNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);//釋放尾節(jié)點(diǎn)
		tail->next = NULL;//將新尾節(jié)點(diǎn)的next置為NULL
	}
}

3.7 鏈表的頭刪

void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)//空鏈表
	{
		return;
	}
	else//非空鏈表
	{
		SListNode* next = (*pphead)->next;//next作為臨時(shí)變量存放的是被刪除的節(jié)點(diǎn)中next存儲(chǔ)的第二個(gè)節(jié)點(diǎn)的地址
		free(*pphead);
		*pphead = next;
	}
}

3.8 鏈表任意位置的前插入

void SListInsertBefore(SListNode** pphead, SListNode* pos,SLTDataType x)
{
	assert(pphead);
	if (*pphead == pos)//pos是第一個(gè)節(jié)點(diǎn)，相當(dāng)于頭插
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

3.9 鏈表任意位置的后插入

兩種實(shí)現(xiàn)方式：

方式一：

void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	
	newnode->next = pos->next;
	pos->next = newnode;
	//這兩行代碼順序是固定的，只能這個(gè)順序，無(wú)法進(jìn)行改變
}

圖示：

方式二：

void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	SListNode* next = pos->next;
	SListNode* newnode = BuySListNode(x);

	newnode->next = next;
	pos->next = newnode;
	//這兩行代碼可以任意改變順序，誰(shuí)先誰(shuí)后都不影響最后的結(jié)果
}

圖示：

3.10 鏈表的任意位置的刪除

void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)//當(dāng)pos為頭節(jié)點(diǎn)的時(shí)候
	{
		SListPopFront(pphead);
	}
	else//當(dāng)pos為非頭節(jié)點(diǎn)的時(shí)候
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

圖示：

3.11 鏈表的任意位置的前刪除

void SListEraseBefore(SListNode** pphead, SListNode* pos)//pos即為任意位置
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		return;
	}
	else if(pos==(*pphead)->next)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;//prev用來(lái)存儲(chǔ)pos的前一個(gè)位置的前一個(gè)位置
		while (prev->next->next != pos)
		{
			prev = prev->next;
		}
		SListNode* next = prev->next;//保存pos前一個(gè)節(jié)點(diǎn)的地址
		prev->next = prev->next->next;//將prev和pos的兩個(gè)節(jié)點(diǎn)進(jìn)行連接
		free(next);//刪除pos的前一個(gè)節(jié)點(diǎn)
	}
}

3.12 鏈表的任意位置的后刪除

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* next = pos->next;
	if (next == NULL)//當(dāng)pos是最后一個(gè)節(jié)點(diǎn)的時(shí)候
	{
		return;
	}
	else
	{
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

圖示：

3.13 鏈表的銷(xiāo)毀

void SListDestory(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;
	SListNode* next = *pphead;//是為了存儲(chǔ)cur下一個(gè)節(jié)點(diǎn)的地址，因?yàn)閒ree(cur)之后，cur指針指向的內(nèi)存中的數(shù)據(jù)可能已經(jīng)稱(chēng)為亂碼了，即不能再正常的使用
	while (cur)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}