C語言單鏈表的圖文示例講解

更新時間：2023年02月14日 14:42:05 作者：[Pokemon]大貓貓

單鏈表是鏈表的其中一種基本結構。一個最簡單的結點結構如圖所示，它是構成單鏈表的基本結點結構。在結點中數(shù)據(jù)域用來存儲數(shù)據(jù)元素，指針域用于指向下一個具有相同結構的結點。?因為只有一個指針結點，稱為單鏈表

一、單鏈表的結構

空鏈表: 此時沒有存儲數(shù)據(jù)，只有一個指針指向 NULL

以上便是單鏈表的結構：

每一塊空間可以按需申請釋放
插入和刪除不需要移動數(shù)據(jù)，修改每塊空間的指針指向即可

在習慣上將申請的一塊一塊的空間稱為結點，指向第一個結點的指針稱為頭指針

//數(shù)據(jù)的類型：這里以 int 來舉例
typedef int SLTDataType;
//結點的類型
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

二、單鏈表的函數(shù)接口

1. 申請結點及打印單鏈表

在插入時需要申請結點，為了避免麻煩重復的操作，這里將申請結點封裝為一個函數(shù)

申請結點函數(shù)如下：

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if(newnode == NULL)
	{
		//開辟空間失敗，打印錯誤信息
		perror("malloc");
		//結束程序
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

為了驗證插入、刪除等得到的結果是否正確，提供打印單鏈表的函數(shù)，這里數(shù)據(jù)類型以 int 為例，當讀者采用的類型不同時，自行更改函數(shù)即可

打印單鏈表函數(shù)如下：

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	//打印數(shù)據(jù)
	while(cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

2. 尾插尾刪

尾插：在鏈表的最后一個結點之后插入結點

尾插函數(shù)如下：

//在鏈表為空時，需要改變頭指針，這里采用傳二級指針的方式
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	//申請結點
	SLTNode* newnode = BuySLTNode(x);
	//鏈表為空時
	if(*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找到最后一個結點
		SLTNode* ptail = *pphead;
		while(ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}

尾刪：刪除鏈表最后一個結點

尾刪函數(shù)如下：

//鏈表只有一個結點時，需要改變頭指針，這里采用傳二級指針的方式
void SLTPopBack(SLTNode** pphead)
{
	//鏈表為空時，無法刪除
	assert(*pphead);
	//鏈表只有一個結點時
	if((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找到倒數(shù)第二個結點
		SLTNode* ptail = *pphead;
		while(ptail->next->next)
		{
			ptail = ptail->next;
		}
		free(ptail->next);
		ptail->next = NULL;
	}
}

3. 頭插頭刪

頭插：在第一個結點之前插入新結點

頭插函數(shù)如下：

//需要改變頭指針，這里采用傳二級指針的方式
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	//申請結點
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

頭刪：刪除鏈表的第一個結點

頭刪函數(shù)如下：

//需要改變頭指針，這里采用傳二級指針的方式
void SLTPopFront(SLTNode** pphead)
{
	//鏈表為空時，無法刪除
	assert(*pphead);
	//保存第二個結點
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

4. 中間插入和刪除

中間插入：通過后面介紹的查找函數(shù) SLTFind 獲得指向結點的指針 pos，在 pos 指向的結點之前或之后插入結點

1. 在 pos 指向的結點之后插入結點

在 pos 之后插入結點函數(shù)如下：

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	//pos 不能為空
	assert(pos);
	//申請結點
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

2. 在 pos 指向的結點之前插入結點

在 pos 之前插入結點函數(shù)如下：

//pos 指向頭結點時，需要改變頭指針，這里采用傳二級指針的方式
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//pos 不能為空
	assert(pos);
	//頭插
	if(*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		//找到 pos 的前一個結點
		SLTNode* prev = *pphead;
		while(prev->next != pos)
		{
			prev = prev->next;
		}
		//申請結點
		SLTNode* newnode = BuySLTNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}

中間刪除：通過后面介紹的查找函數(shù) SLTFind 獲得指向結點的指針 pos，刪除 pos 指向的結點或后一個結點

3. 刪除 pos 指向的結點的后一個結點

刪除 pos 之后的結點函數(shù)如下：

void SLTEraseAfter(SLTNode* pos)
{
	//pos 不能為空
	assert(pos);
	//指向最后一個結點時，不做處理
	if(pos->next == NULL)
	{
		return;
	}
	else
	{
		//保存后一個結點
		SLTNode* next = pos->next;
		pos->next = next->next;
		free(next);
	}
}

4. 刪除 pos 指向的結點

刪除 pos 指向的結點函數(shù)如下：

//pos 指向頭結點時，需要改變頭指針，這里采用傳二級指針的方式
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	//pos 不能為空
	assert(pos);
	//頭刪
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		//找到 pos 的前一個結點
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

6. 查找

查找：如果數(shù)據(jù)存在，返回該數(shù)據(jù)結點的指針，不存在返回 NULL

查找函數(shù)如下：

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

7. 銷毀單鏈表

在單鏈表中，存儲數(shù)據(jù)的結點是由自己開辟的，當不使用單鏈表時，應將其銷毀

銷毀單鏈表函數(shù)如下：

需要將頭指針置空，這里采用傳二級指針的方式
void SLTDestroy(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur)
	{
		//保存下一個結點
		SLTNode* nextnode = cur->next;
		free(cur);
		cur = nextnode;
	}
	//將頭指針置空
	*pphead = NULL;
}

到此這篇關于C語言單鏈表的圖文示例講解的文章就介紹到這了,更多相關C語言單鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

C++線程間的互斥和通信場景分析
很多朋友對C++線程間的互斥和通信知識掌握不是多牢靠，今天小編通過模擬車站賣票應用場景給大家詳細解析C++線程間的互斥和通信知識，感興趣的朋友跟隨小編一起看看吧
2021-05-05
strings命令分析淺談Go和C++編譯時的一點小區(qū)別
今天小編就為大家分享一篇關于strings命令分析淺談Go和C++編譯時的一點小區(qū)別，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧
2019-04-04
OpenCV使用BSM統(tǒng)計視頻中移動的對象
這篇文章主要為大家詳細介紹了OpenCV如何使用BackgroundSubstractor(BSM)實現(xiàn)視頻中移動對象統(tǒng)計功能，文中的示例代碼講解詳細，需要的可以參考一下
2023-02-02
C語言kmp算法簡單示例和實現(xiàn)原理探究
這篇文章主要介紹了C語言kmp算法簡單示例和實現(xiàn)原理探究,本文用簡潔的語言說明KMP算法的原理,并給出了示例,需要的朋友可以參考下
2014-09-09
C語言實現(xiàn)的學生選課系統(tǒng)代碼分享
這篇文章主要介紹了C語言實現(xiàn)的學生選課系統(tǒng)代碼分享，具有一定參考價值，需要的朋友可以了解下。
2017-10-10
淺析C語言位域和位段
以下是對C語言中的位域和位段進行了詳細的分析介紹，需要的朋友可以過來參考下
2013-08-08
Qt?TCP網(wǎng)絡通信學習
用于數(shù)據(jù)傳輸?shù)牡蛯泳W(wǎng)絡協(xié)議，多個物聯(lián)網(wǎng)協(xié)議都是基于TCP協(xié)議的，這篇文章為大家介紹了Qt?TCP網(wǎng)絡通信，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2022-08-08
C語言中組成不重復的三位數(shù)問題
這篇文章主要介紹了C語言中組成不重復的三位數(shù)問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2022-11-11
opencv提取外部輪廓并在外部加矩形框
這篇文章主要為大家詳細介紹了opencv提取外部輪廓并在外部加矩形框，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2018-10-10
一文讀懂c++之static關鍵字
這篇文章主要介紹了c++之static關鍵字的的相關資料，文中示例代碼非常詳細，供大家參考和學習，感興趣的朋友可以了解下
2020-06-06