🎉🎉想快速入門資料結構，推薦訂閱作者的初階資料結構專欄！此專欄預計更新：順序表，鏈表，堆疊，佇列，二叉樹，排序演算法等等

🎉🎉初階資料結構我們通過c語言實作，所以此專欄也可以幫助大家鞏固大家的c語言知識

知識回顧

在前一章中我們已經介紹了順序表，相信大家對順序表的實作已經有所了解了吧！

但是，這種資料結構，難免會有以下的缺陷

1. 我們在中間位置插入或洗掉資料的話，可能需要挪動后面的所有資料，時間復雜度較高==(O(n))==
2. 我們的空間是按照2倍的常數開辟的，可能會造成空間的浪費，比如我們的順序表從100擴容到200，但我們只需要插入5個資料，剩下的195單位空間就被浪費了
3. 增容程序也會造成資源的消耗

為了克服以上的缺陷，我們設計出了另外一種線性資料結構——鏈表

之所以叫它線性表，是因為它的邏輯結構是連續的，仍然滿足線性表的特征

但它在物理結構上未必是關聯的，連續的

在物理結構上非連續的話，我們可以利用地址，形成元素之間的相互聯系

它的定義仍然是一個結構體,每個結構體，就是鏈表中的一個結點

struct ListNode
{
	int data;//存放元素
	struct ListNode* next;//存放下一個元素的地址，以此來鏈接元素
};

這種資料結構，它的空間就是按需申請的，沒有任何空間的浪費，用多少申請多少

直接申請一個結點就行了

但卻仍然不可避免的有缺陷：不支持隨機訪問(下標訪問)

查找的時間復雜度為O(n)

實際中鏈表的實作方式有很多種，今天為大家介紹其中的一種，不帶頭的單向鏈表

后面會更新帶頭回圈鏈表，敬請期待！

還是從增刪查改來介紹鏈表怎么定義

單鏈表定義

頭檔案定義

定義的方法，以及至于為什么這樣定義已經在前一期說過了，不懂的小伙伴可以看我這篇 關于順序表的文章.里面關于順序表的定義，很多都是相通的

//Slist.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLTDataType;//方便存盤各種各樣的資料

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;//重命名，簡化后面代碼的撰寫

初始化

鏈表的初始化比較簡單，在main函式中可以直接這樣初始化

SLTNode* plist=NULL;

單鏈表插入

開辟結點

我們同樣利用動態記憶體管理開辟空間

初始化方式:data為你需要插入的資料，next指向NULL

函式回傳一個結構體型別

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

尾部插入

假設我們有下面的鏈表

由于我們的鏈表不支持隨機訪問，所以不能直接找到尾部元素

我們也只能定義一個變數來遍歷，然后直到某一個結點的next指向NULL

所以我們可以寫出以下的代碼

void SListPushBack(SLTNode* phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	SLTNode* cur = phead;
	while (cur->next)
	{
		cur = cur->next;
	}
	cur->next = newnode;
}

這里的cur=cur->next需要另外解釋一下

可以直接用物理圖來解釋

但是，這個代碼卻有一個問題,我們可以嘗試使用一下

使用示例：

SLTNode* plist=NULL;
SListPushBack(plist,1);

但是程式卻崩潰了

原因其實是這樣：
在我們初始化的時候plist設定的為空

所以當我們在空鏈表尾插的時候，將會崩潰，因為函式的引數是相對于指標變數的傳值呼叫，并不會改變外部的鏈表仍然為空

而我們對地址進行傳址呼叫時，就需要傳一個二級指標進去

所以，最終代碼如下

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (!(*pphead))
	{
		*pphead = newnode;
	}//加上一個空指標判斷
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

正確使用示例

void Test1()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);
}

效果圖

頭部插入

與尾部插入相似，這里不再做詳細闡述，解釋在代碼里面

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;//將新結點鏈接到原來的頭結點
	*pphead = newnode;//將新結點作為新的頭結點
}

任意位置插入(前面)

這里需要的查找函式在本文的偏后位置，大家也可以點擊目錄直接定位

這里我們需要三個引數，分別是：

頭結點的地址，插入位置**（需要查找函式定位）**，插入數字

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

以下是查找的思路，(假如在3的前面插入)

同樣需要cur變數來尋找你傳入的位置

我們需要檢查cur->next是不是我們需要的位置

下圖中，cur->next就是pos位置

然后開始malloc新結點，開始鏈接

同理，這里如果為空指標會出現問題

但在這里，1個結點也會出現問題！

因為這里的cur和pos會指向相同位置

代碼處理完將會這樣

所以我們仍然要加入特殊情況的處理方式

void SListInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = BuySListNode(x);
		SLTNode* cur = *pphead;

		while (cur->next != pos)
		{
			cur = cur->next;
		}
		newnode->next = pos;
		cur->next = newnode;
	}

}

任意位置插入(后面)

任意位置后面的插入要簡單的多，從引數都能看出來，少了一個

void SListInsertAfter(SLTNode* pos, SLTDataType x);

主要原因是因為我們的鏈表，在知道一個結點后，是可以找到下一個元素的

而前面的元素卻找不到(只針對單鏈表)

程序（還是以3舉例）

特別宣告！！！

這里的操作順序不能顛倒，因為如果先改變pos->next的話，真正的next結點就不能夠找到了

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

單鏈表洗掉

洗掉的實作，有一種情況就是對空鏈表進行洗掉操作

在這里我們不用這么墨跡，直接用粗暴的方法，直接assert斷言！

尾部洗掉

同樣，需要一個tail指標，尋找鏈表的尾部元素
我們這里的結束條件是tail->next->next,也就是找到倒數第二個元素

但是有一個只有一個元素尾刪的問題

這里的tail->next->next就是對空指標的解參考，就會報錯

我們同樣需要加入特殊情況的討論

void SListPopBack(SLTNode** pphead)
{
	assert(*pphead);

	if (!((*pphead)->next))
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

頭刪

頭刪就沒那么多講究了，直接上代碼

void SListPopFront(SLTNode** pphead)
{
	assert(*pphead);

	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

任意位置洗掉(當前位置)

這些函式直接開始上圖

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(*pphead);
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

任意位置洗掉(后面)

void SListEraseAfter(SLTNode* pos)
{
	assert(pos->next);
	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

查找函式

這里有兩種實作方式，它們的回傳值不同

一個回傳鏈表的位置int型

一個直接回傳此鏈表結點

本文采用后者實作

仍然使用暴力求解法

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

使用方法

為插入，洗掉函式指示位置

使用示例：

void Test5()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);
	SListPrint(plist);
	SLTNode* pos1 = SListFind(plist, 3);
	SListInsertAfter(pos1, 6);
}//在3的后面插入一個6

如果有重復元素的鏈表怎么辦？例如

1 1 1 1 1 2 3 4

使用方法先進行初始化，找到第一個結點的位置，利用回圈，去訪問

pos=SListFind(plist,1);//初始化
while(pos)
{
	pos=SListFind(plist,1);//迭代程序
	//你需要的其它操作
}

其它函式

列印函式

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

銷毀函式

void SListDestory(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* cur = *pphead;
	SLTNode* next = NULL;
	while (cur)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}