前言

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

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

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

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

一、鏈表的介紹

1.什么是鏈表

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

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

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

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

2.鏈表的分類

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

2.1.根據(jù)方向

單向/雙向鏈表

2.2.頭結(jié)點

帶頭結(jié)點/不帶頭結(jié)點

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

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

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

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

鏈表我們該如何去表示呢？其實，通過上面的例子，我們大致已經(jīng)知道，需要一個地方來存放數(shù)據(jù)，另一個地方存放下一個結(jié)點的地址。我們可以通過結(jié)構(gòu)體來定義，具體代碼如下：

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

2.開辟結(jié)點

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

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

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

3.打印

先別急，我們先來試試水，先嘗試自己動手寫一下打印的函數(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é)點插入到到鏈表的尾部。

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

 每一次插入一個數(shù)都放在最后一個位置，同時，最后一個結(jié)點的指針域置為空，關(guān)鍵的就是，我們?nèi)绾握业疆?dāng)前鏈表的尾結(jié)點呢？前面已經(jīng)說了，最后一個結(jié)點的指針域為空，我們可以以此為突破點。注意：當(dāng)鏈表為空時，你會怎么處理？想想。這里先不說了，直接看看我們的代碼。

//尾插
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)該注意到了，這里我們使用的都是二級指針pphead

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

5.頭插

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

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

6.測試

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

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();
}

運行結(jié)果如下：

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

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

7.頭刪/尾刪

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

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

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

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

尾刪的關(guān)鍵點在于找到最后一個結(jié)點，最后一個結(jié)點的指針域為空。

1.鏈表為空時，不需要刪，

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

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

8.查找

查找這個操作其實是比較簡單的，在這里說是為了后面的使用，想要找到摸個元素，直接去調(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

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

兩個核心點：

1.pos 的位置

2.插入的操作（這里可能有的同學(xué)會有一些疑惑，其實只要知道一點，插入的位置是已經(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)鍵的一點，如何找到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

這個沒啥好說的，自己可以去試試

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

結(jié)束語

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

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

最新評論