前言

關(guān)于線性表的一些相關(guān)介紹，大家可以看看我們之前寫的點(diǎn)我-鏈表

點(diǎn)我-順序表，里面有一些相關(guān)的知識(shí)介紹，都是比較基礎(chǔ)的，一些比較常見的操作里面也有具體的介紹與實(shí)現(xiàn)到，然后呢，今天我們學(xué)習(xí)的是鏈表，相比于之前的操作實(shí)現(xiàn)更加具有深度，對(duì)于一些比較簡(jiǎn)單的操作這里就不加說明了。而且涉及到之前未說到的一些知識(shí)，對(duì)此我們可以強(qiáng)化對(duì)其認(rèn)識(shí)，這就是寫這篇博客的目的。

編譯工具：vs2019，小伙伴們可以一起跟著來敲敲代碼。

開始之前：很有必要提醒大家注意二級(jí)指針的使用，為什么會(huì)用到二級(jí)指針，我的博客也有一些相關(guān)介紹，簡(jiǎn)單來說，傳值參數(shù)并不改變實(shí)參，傳址參數(shù)改變形參。

一、鏈表的介紹

1.什么是鏈表

簡(jiǎn)單來說，就是一條鏈子連接成的表，上面的鏈接也有比較正式規(guī)矩的介紹。

與順序表相比，鏈表的最大特點(diǎn)就是不要求物理空間連續(xù)，插入不需要移動(dòng)大量的數(shù)據(jù)

 怎么去聯(lián)系各個(gè)結(jié)點(diǎn)呢？

從上圖其實(shí)不難發(fā)現(xiàn)，搞個(gè)指針連接起來就行了。既要有數(shù)據(jù)域和指針域，注意一點(diǎn)：最后一個(gè)元素的指針域?yàn)镹ULL。上面的箭頭實(shí)際并不存在，只是為了看起來比較直接，形象化起來。那要怎么去表示出來了？可以用結(jié)構(gòu)體的自引用。

2.鏈表的分類

之前并沒說到鏈表的類型有哪些，根據(jù)類型的不同，我們實(shí)際上可以對(duì)其進(jìn)行分類，由于都是基于單鏈表實(shí)現(xiàn)操作，因此需要學(xué)好單鏈表，進(jìn)行深化學(xué)習(xí)。

2.1.根據(jù)方向

單向/雙向鏈表

2.2.頭結(jié)點(diǎn)

帶頭結(jié)點(diǎn)/不帶頭結(jié)點(diǎn)

2.3.循環(huán)/非循環(huán)

 二、鏈表的實(shí)現(xiàn)

鏈表的實(shí)現(xiàn)當(dāng)然離不開我們自己動(dòng)手去敲代碼了，這首先需要準(zhǔn)備好我們的編譯環(huán)境，vs2019,同時(shí)，每次寫完一塊模板，我們要去測(cè)試一下有沒有bug，方便我們?nèi)フ义e(cuò)誤，進(jìn)行調(diào)試，這樣會(huì)大大減少我們的工作量。

1.結(jié)構(gòu)體

鏈表我們?cè)撊绾稳ケ硎灸?？其?shí)，通過上面的例子，我們大致已經(jīng)知道，需要一個(gè)地方來存放數(shù)據(jù)，另一個(gè)地方存放下一個(gè)結(jié)點(diǎn)的地址。我們可以通過結(jié)構(gòu)體來定義，具體代碼如下：

#include <stdio.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

2.開辟結(jié)點(diǎn)

后續(xù)操作會(huì)頻繁動(dòng)態(tài)開辟一個(gè)頭結(jié)點(diǎn)，我們不妨把它封裝成一個(gè)函數(shù)，便于后面方便使用。當(dāng)然，你如果覺得自己每次都可以自己寫的話，也不必寫成一個(gè)函數(shù)。

//創(chuàng)建新結(jié)點(diǎn)
SLTNode* BuySListNode(SLTDataType x) {
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

注意點(diǎn)：新結(jié)點(diǎn)的指針域置為空！

3.打印

先別急，我們先來試試水，先嘗試自己動(dòng)手寫一下打印的函數(shù)。

這里為了比較更加形象起來，每次打印的時(shí)候都會(huì)用->來連接，同時(shí)，最后用NULL結(jié)尾

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

4.尾插

什么是尾插？根據(jù)字面意思，就是將新結(jié)點(diǎn)插入到到鏈表的尾部。

為了讓大家更好理解，特地上網(wǎng)找了一張圖片，一起來看看把

 每一次插入一個(gè)數(shù)都放在最后一個(gè)位置，同時(shí)，最后一個(gè)結(jié)點(diǎn)的指針域置為空，關(guān)鍵的就是，我們?nèi)绾握业疆?dāng)前鏈表的尾結(jié)點(diǎn)呢？前面已經(jīng)說了，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭眨覀兛梢砸源藶橥黄泣c(diǎn)。注意：當(dāng)鏈表為空時(shí)，你會(huì)怎么處理？想想。這里先不說了，直接看看我們的代碼。

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

細(xì)心的你應(yīng)該注意到了，這里我們使用的都是二級(jí)指針pphead

因?yàn)榧僭O(shè)我們使用一級(jí)指針，直接傳入頭指針phead時(shí)，頭指針本身就是一級(jí)指針的了，當(dāng)我們需要更改該指針指向的地址時(shí)，改動(dòng)只會(huì)在函數(shù)內(nèi)部生效，main函數(shù)中的phead指針并沒有被改變。要想改變的話，就需要二級(jí)指針來進(jìn)行操作了

5.頭插

有尾插自然就會(huì)有頭插，相比較與尾插而言，頭插顯得更加簡(jiǎn)單了，直接把新的結(jié)點(diǎn)放在頭結(jié)點(diǎn)前不就ok了？

//頭插 
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

6.測(cè)試

好了，到這里，我們已經(jīng)有一些函數(shù)了，不急，我們先來測(cè)試測(cè)試效果如何

void TestSList1()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 0);
	SListPrint(plist);
}
int main()
{
TestSList1();
}

運(yùn)行結(jié)果如下：

 我們必須養(yǎng)成邊寫代碼邊測(cè)試的習(xí)慣，這有利于我們及時(shí)發(fā)現(xiàn)自己的錯(cuò)誤，不易導(dǎo)致后面出現(xiàn)一大堆bug而自己卻不知道錯(cuò)在哪。當(dāng)然，除此之外，我們還可以通過調(diào)試的方法，快速準(zhǔn)確發(fā)現(xiàn)自己的bug，這也是我們需要養(yǎng)成的。這些都是需要我們?nèi)リP(guān)注的點(diǎn)。

好啦，下面我不會(huì)在像上面那么詳細(xì)的說明了，我們直接來個(gè)頭刪尾刪

7.頭刪/尾刪

有頭插尾插，自然有頭刪尾刪，其實(shí)，不知道你們發(fā)現(xiàn)，不管是插還是刪，關(guān)于頭部的操作都是比較簡(jiǎn)單了，我們先來個(gè)開胃菜，頭刪：可不能直接刪哦，我們要記錄頭結(jié)點(diǎn)的下一個(gè)位置，如何直接刪了頭結(jié)點(diǎn)的話，那就麻煩，會(huì)造成野指針的，自己好好捋捋。

//頭刪
void SListpopFront(SLTNode**pphead)
{
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

尾刪：說起尾刪，就要多注意點(diǎn)了，要看具體情況而言了，直接來看代碼把

//尾刪
void SListPopBack(SLTNode** pphead)
{
	//鏈表為空
	if (*pphead == NULL)
	{
		return;
	}
	//只有一個(gè)結(jié)點(diǎn)
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//有一個(gè)以上的結(jié)點(diǎn)
	else {
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

尾刪的關(guān)鍵點(diǎn)在于找到最后一個(gè)結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭铡?/p>

1.鏈表為空時(shí)，不需要?jiǎng)h，

2.鏈表只有一個(gè)結(jié)點(diǎn)，那它自己就是最后一個(gè)結(jié)點(diǎn)了，

3.多個(gè)結(jié)點(diǎn)就按常規(guī)處理就ok了，該說清楚的還是要說清楚的。 

8.查找

查找這個(gè)操作其實(shí)是比較簡(jiǎn)單的，在這里說是為了后面的使用，想要找到摸個(gè)元素，直接去調(diào)用函數(shù)即可，不用自己一次次去遍歷。

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

9.在pos的前面插入x

除了基本的頭尾增加，我們還可能還需要在某一個(gè)特定節(jié)點(diǎn)前后進(jìn)行插入，這就需要我們玩轉(zhuǎn)起來了，變得更加靈活。

兩個(gè)核心點(diǎn)：

1.pos 的位置

2.插入的操作（這里可能有的同學(xué)會(huì)有一些疑惑，其實(shí)只要知道一點(diǎn)，插入的位置是已經(jīng)知道的了）

//在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	if (pos == *pphead) {
		SListPushFront(pphead,x);
	}
	else {
		SLTNode* newnode = BuySListNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

10.刪除pos位置的值

關(guān)鍵的一點(diǎn)，如何找到pos，找到之后鏈表跳過它，然后刪除即可。

//刪除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	if (pos == *pphead)
	{
		SListpopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

三、主函數(shù)Test

這個(gè)沒啥好說的，自己可以去試試

這只是單純的試試函數(shù)能不能調(diào)用起來，自己可以動(dòng)氣手來試一試

結(jié)束語

好啦，這次想說的主要都講完了，其實(shí)學(xué)數(shù)據(jù)結(jié)構(gòu)除了實(shí)現(xiàn)之外，我們還需要及時(shí)去刷一些OJ題，提高我們的能力，使自己的知識(shí)融會(huì)貫通起來??

到此這篇關(guān)于C語言一篇精通鏈表的各種操作的文章就介紹到這了,更多相關(guān)C語言鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論