前言

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

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

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

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

一、鏈表的介紹

1.什么是鏈表

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

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

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

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

2.鏈表的分類

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

2.1.根據方向

單向/雙向鏈表

2.2.頭結點

帶頭結點/不帶頭結點

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

 二、鏈表的實現

鏈表的實現當然離不開我們自己動手去敲代碼了，這首先需要準備好我們的編譯環(huán)境，vs2019,同時，每次寫完一塊模板，我們要去測試一下有沒有bug，方便我們去找錯誤，進行調試，這樣會大大減少我們的工作量。

1.結構體

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

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

2.開辟結點

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

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

注意點：新結點的指針域置為空！

3.打印

先別急，我們先來試試水，先嘗試自己動手寫一下打印的函數。

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

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

4.尾插

什么是尾插？根據字面意思，就是將新結點插入到到鏈表的尾部。

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

 每一次插入一個數都放在最后一個位置，同時，最后一個結點的指針域置為空，關鍵的就是，我們如何找到當前鏈表的尾結點呢？前面已經說了，最后一個結點的指針域為空，我們可以以此為突破點。注意：當鏈表為空時，你會怎么處理？想想。這里先不說了，直接看看我們的代碼。

//尾插
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;
	}
}

細心的你應該注意到了，這里我們使用的都是二級指針pphead

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

5.頭插

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

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

6.測試

好了，到這里，我們已經有一些函數了，不急，我們先來測試測試效果如何

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ǎng)成邊寫代碼邊測試的習慣，這有利于我們及時發(fā)現自己的錯誤，不易導致后面出現一大堆bug而自己卻不知道錯在哪。當然，除此之外，我們還可以通過調試的方法，快速準確發(fā)現自己的bug，這也是我們需要養(yǎng)成的。這些都是需要我們去關注的點。

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

7.頭刪/尾刪

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

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

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

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

尾刪的關鍵點在于找到最后一個結點，最后一個結點的指針域為空。

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

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

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

8.查找

查找這個操作其實是比較簡單的，在這里說是為了后面的使用，想要找到摸個元素，直接去調用函數即可，不用自己一次次去遍歷。

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é)點前后進行插入，這就需要我們玩轉起來了，變得更加靈活。

兩個核心點：

1.pos 的位置

2.插入的操作（這里可能有的同學會有一些疑惑，其實只要知道一點，插入的位置是已經知道的了）

//在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位置的值

關鍵的一點，如何找到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);
	}
}

三、主函數Test

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

這只是單純的試試函數能不能調用起來，自己可以動氣手來試一試

結束語

好啦，這次想說的主要都講完了，其實學數據結構除了實現之外，我們還需要及時去刷一些OJ題，提高我們的能力，使自己的知識融會貫通起來??

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