快捷導(dǎo)航

C語(yǔ)言單鏈表的圖文示例講解

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

單鏈表是鏈表的其中一種基本結(jié)構(gòu)。一個(gè)最簡(jiǎn)單的結(jié)點(diǎn)結(jié)構(gòu)如圖所示，它是構(gòu)成單鏈表的基本結(jié)點(diǎn)結(jié)構(gòu)。在結(jié)點(diǎn)中數(shù)據(jù)域用來(lái)存儲(chǔ)數(shù)據(jù)元素，指針域用于指向下一個(gè)具有相同結(jié)構(gòu)的結(jié)點(diǎn)。?因?yàn)橹挥幸粋€(gè)指針結(jié)點(diǎn)，稱為單鏈表

一、單鏈表的結(jié)構(gòu)

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

以上便是單鏈表的結(jié)構(gòu)：

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

在習(xí)慣上將申請(qǐng)的一塊一塊的空間稱為結(jié)點(diǎn)，指向第一個(gè)結(jié)點(diǎn)的指針稱為頭指針

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

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

1. 申請(qǐng)結(jié)點(diǎn)及打印單鏈表

在插入時(shí)需要申請(qǐng)結(jié)點(diǎn)，為了避免麻煩重復(fù)的操作，這里將申請(qǐng)結(jié)點(diǎn)封裝為一個(gè)函數(shù)

申請(qǐng)結(jié)點(diǎn)函數(shù)如下：

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

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

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

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

2. 尾插尾刪

尾插：在鏈表的最后一個(gè)結(jié)點(diǎn)之后插入結(jié)點(diǎn)

尾插函數(shù)如下：

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

尾刪：刪除鏈表最后一個(gè)結(jié)點(diǎn)

尾刪函數(shù)如下：

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

3. 頭插頭刪

頭插：在第一個(gè)結(jié)點(diǎn)之前插入新結(jié)點(diǎn)

頭插函數(shù)如下：

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

頭刪：刪除鏈表的第一個(gè)結(jié)點(diǎn)

頭刪函數(shù)如下：

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

4. 中間插入和刪除

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

1. 在 pos 指向的結(jié)點(diǎn)之后插入結(jié)點(diǎn)

在 pos 之后插入結(jié)點(diǎn)函數(shù)如下：

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	//pos 不能為空
	assert(pos);
	//申請(qǐng)結(jié)點(diǎn)
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

2. 在 pos 指向的結(jié)點(diǎn)之前插入結(jié)點(diǎn)

在 pos 之前插入結(jié)點(diǎn)函數(shù)如下：

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

中間刪除：通過(guò)后面介紹的查找函數(shù) SLTFind 獲得指向結(jié)點(diǎn)的指針 pos，刪除 pos 指向的結(jié)點(diǎn) 或后一個(gè)結(jié)點(diǎn)

3. 刪除 pos 指向的結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)

刪除 pos 之后的結(jié)點(diǎn)函數(shù)如下：

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

4. 刪除 pos 指向的結(jié)點(diǎn)

刪除 pos 指向的結(jié)點(diǎn)函數(shù)如下：

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

6. 查找

查找：如果數(shù)據(jù)存在，返回該數(shù)據(jù)結(jié)點(diǎn)的指針，不存在返回 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. 銷毀單鏈表

在單鏈表中，存儲(chǔ)數(shù)據(jù)的結(jié)點(diǎn)是由自己開辟的，當(dāng)不使用單鏈表時(shí)，應(yīng)將其銷毀

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

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

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

您可能感興趣的文章: