?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???? ?? ??
??個人主頁 ：阿然成長日記 ??點擊可跳轉(zhuǎn)
?? 個人專欄： ??數(shù)據(jù)結構與算法??C語言進階
?? 不能則學，不知則問，恥于問人，決無長進
?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??

??小伙伴們，又見面了?? ?? ?? ?? 前面我們學習啦順序表，其實順序表的時間復雜度是很高的，尤其是在插入，刪除等問題上，需要移動整個數(shù)組，十分麻煩費時。有沒有更好的辦法呢？？？？當然有呀，就是鏈表，也是本篇博客要詳細講解的。

一、鏈表的概念

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

鏈表就像是一列火車，鏈表中的每一個節(jié)點，就像是火車的一節(jié)節(jié)車廂。

圖1.1
圖1.2

二、特點

1?? 鏈式結構在邏輯上是連續(xù)的,但在物理層上不一定連續(xù)。
2??節(jié)點一般都是從堆上申請出來的一塊空間。
3??從堆上申請的空間，按照它的規(guī)則來進行分配，兩次申請的空間，不一定連續(xù)。

三、鏈表的分類

1.單向或者雙向
2. 帶頭或者不帶頭
3. 循環(huán)或者非循環(huán)

四、單向鏈表的結構體

?誤區(qū)：以下這種結構體定義會報錯，那么是為什么呢？

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	SLTNode* next;//錯誤

}SLTNode;

我們的typedef關鍵字給結構體重新命名為SLTNode，但是他是在結構體最后才生效，如果現(xiàn)在就在結構體中使用新命名，那么就會找不到。

??正解是：

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;

 }SLTNode;

1.node:是存儲的數(shù)據(jù)；
2.next 的類型是一個節(jié)點型的指針變量，它保存的是下一個節(jié)點的地址，即指向下一個節(jié)點

命名規(guī)范：

當我們在給結構體命名或者是函數(shù)的命名我們都應該使用用英文或者英文的簡寫來進行命名這樣有利于人們的理解。例如單鏈表英文名：single List table，所以我給節(jié)點命名為SLTNode.

二級指針

在下面的學習中，會使用二級指針，不太清楚的小伙伴，可以去看我的??C進階專欄中的??高級指針一篇

??注意事項

我們現(xiàn)在定義的頭指針在函數(shù)結束之后都會銷毀，因為它存在棧上。我們的每一個節(jié)點是使用動態(tài)內(nèi)存函數(shù)在堆上進行開辟如果不進行free釋放那么它會持續(xù)保存到程序結束。

五、函數(shù)實現(xiàn)

1.單鏈表的打印

//打印單鏈表
void PrintSlistTable(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");
}

2.單鏈表的頭插

頭插思路分析：

頭插代碼

//頭插
void SLTPusFront(SLTNode** pphead, SLTDataType x)//放入新插入節(jié)點
{
	SLTNode* newnode = CreatNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

這里有很多小伙伴都不知道為什么使用了二級指針。因為在傳參時我們使用的是結構體地址傳參，這樣能節(jié)省空間，提高效率，傳入的是一級指針phead的地址，所以我們需要使用二級指針pphead來接收。

3.單鏈表的尾插

尾插思路分析：

尾插代碼：

//尾插
void SLTPusBack(SLTNode**  pphead, SLTDataType x)
{
	SLTNode* newnode = CreatNode(x);
	if (*pphead == NULL)
	{
		//改變的結構體的指針，所以要用二級指針 
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
		tail = tail->next;
		}
		//改變結構體，用結構體指針即可 
	tail->next = newnode;
	}
}

4.單鏈表的頭刪

思路：
一個節(jié)點和多個節(jié)點處理方式相同

代碼：

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

1?? 定義一個cur臨時指針用來指向頭節(jié)點的下一個節(jié)點.SLTNode* cur = (*pphead)->next;
2?? 釋放 *pphead即（刪除第一個節(jié)點）free(*pphead);
3?? 在將 *pphead指向第二節(jié)點*pphead = cur;

5.單鏈表尾刪

思路：
1.如果沒有節(jié)點,則直接釋放頭指針所指向的內(nèi)容
2.

代碼：

//尾插
void SLTPusBack(SLTNode**  pphead, SLTDataType x)
{
	SLTNode* newnode = CreatNode(x);
	if (*pphead == NULL)
	{
		//改變的結構體的指針，所以要用二級指針 
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
		tail = tail->next;
		}
		//改變結構體，用結構體指針即可 
	tail->next = newnode;
	}
}

6.在pos位置之前插入x

思路：

代碼：

//在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
		//頭插；
		SLTPusFront(pphead, x);
	}
	else
	{
		//定義一個臨時指針cur指向頭指針，為了從頭開始遍歷各個節(jié)點找pos，而不會改變頭指針pphead的指向位置。
		SLTNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		SLTNode* newNode = CreatNode(x);
		newNode->next = cur->next;
		cur->next = newNode;
		free(cur);
		cur = NULL;
	}
}

定義一個臨時指針cur指向頭指針，用來從頭開始遍歷各個節(jié)點找pos，
頭指針pphead的指向位置不能變，不然就找不到頭了。

7.在pos位置之后插入x

思路：

代碼：

在pos位置之后插入x
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(*pphead);
	SLTNode* newNode = CreatNode(x);
	newNode->next = pos->data;
	pos->next = newNode;
}

8.刪除pos位置 節(jié)點

思路：

代碼：

//刪除POS位置 
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
		//頭刪
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next == pos)
		{
			cur = cur->next;

		}
		pos->next = cur->next;
		free(pos);
	}
}

9.刪除pos位置之后的節(jié)點

思路：

代碼：

//刪除POS之后的位置 
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{

		assert(pphead);
		assert(pos);
		assert(pos->next);

		SLTNode* cur = pos->next->next;
		free(pos->next);
		pos->next = cur;

}

10.單鏈表的查找

代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-628750.html

//單鏈表的查找 

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

到了這里，關于【數(shù)據(jù)結構】之十分好用的“鏈表”趕緊學起來！(第一部分單向鏈表）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！