日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

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

作者：[Pokemon]大貓貓 ? 更新時間： 2023-05-08 編程語言

在上一篇所講述的 動態順序表 中存在一些缺陷

1、當空間不夠時需要擴容，擴容是有一定的消耗的

如果每次空間擴大一點，可能會造成空間的浪費，而空間擴小了，又會造成頻繁的擴容2、在順序表中進行頭部和中部的插入時需要移動數據，效率低下

對于順序表的這些缺陷，有如下解決方案

1、需要時申請一塊空間，不需要時將其釋放

2、插入刪除不需要移動數據

而鏈表就符合這兩點，本篇介紹 無頭單向非循環鏈表(單鏈表)

一、單鏈表的結構

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

以上便是單鏈表的結構：

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

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

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

二、單鏈表的函數接口

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

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

申請結點函數如下：

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;
}

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

打印單鏈表函數如下：

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

2. 尾插尾刪

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

尾插函數如下：

//在鏈表為空時，需要改變頭指針，這里采用傳二級指針的方式
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;
	}
}

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

尾刪函數如下：

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

3. 頭插頭刪

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

頭插函數如下：

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

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

頭刪函數如下：

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

4. 中間插入和刪除

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

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

在 pos 之后插入結點函數如下：

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

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

在 pos 之前插入結點函數如下：

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

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

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

刪除 pos 之后的結點函數如下：

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 指向的結點函數如下：

//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. 查找

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

查找函數如下：

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

7. 銷毀單鏈表

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

銷毀單鏈表函數如下：

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

原文鏈接：https://blog.csdn.net/qq_70793373/article/details/127782089

欄目分類
最近更新