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

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

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

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

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

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

注意：

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

2. 現(xiàn)實中的節(jié)點一般是從堆上申請出來的

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

2 鏈表的分類

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

1、單向或者雙向鏈表

2、帶頭或者不帶頭鏈表

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

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

無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié) 構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而簡單了，后面我們代碼實現(xiàn)了就知道了。

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

3.1 鏈表的定義

typedef int SLTDataType;//
typedef struct SListNode
{
	int data;//val，存儲的數(shù)據(jù)，此處假設(shè)存儲的數(shù)據(jù)為int型
	struct SListNode* next;//存儲下一個節(jié)點的位置
}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;
	}
}

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

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

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

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

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

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

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

3.4 鏈表空間的動態(tài)申請

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 鏈表的尾刪

需要考慮三種情況：

空
一個節(jié)點
多個節(jié)點

兩種寫法：

第一種：

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

這種方式在面對只有一個節(jié)點時也不會出現(xiàn)問題。

第二種：

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

3.7 鏈表的頭刪

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

3.8 鏈表任意位置的前插入

void SListInsertBefore(SListNode** pphead, SListNode* pos,SLTDataType x)
{
	assert(pphead);
	if (*pphead == pos)//pos是第一個節(jié)點，相當(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 鏈表任意位置的后插入

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

方式一：

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

圖示：

方式二：

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

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

圖示：

3.10 鏈表的任意位置的刪除

void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)//當(dāng)pos為頭節(jié)點的時候
	{
		SListPopFront(pphead);
	}
	else//當(dāng)pos為非頭節(jié)點的時候
	{
		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用來存儲pos的前一個位置的前一個位置
		while (prev->next->next != pos)
		{
			prev = prev->next;
		}
		SListNode* next = prev->next;//保存pos前一個節(jié)點的地址
		prev->next = prev->next->next;//將prev和pos的兩個節(jié)點進(jìn)行連接
		free(next);//刪除pos的前一個節(jié)點
	}
}

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

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

圖示：

3.13 鏈表的銷毀

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