C语言＜数据结构-链表＞

发布于：2025-07-11 ⋅ 阅读:(13) ⋅ 点赞:(0)

 

       链表是一种常见且重要的数据结构，在 C 语言中，它通过指针将一系列的节点连接起来，每个节点可以存储不同类型的数据。相比数组，链表在插入和删除元素时不需要移动大量数据，具有更好的灵活性，尤其适合处理动态变化的数据集合。

       当然，既然链表涉及到指针，而且与指针关系密切，所以只有当我们在对于指针有了一定扎实的了解后，才能更好、更轻松的了解链表这一新概念。然而，我认为对于链表这样一类概念来说，增删查改是最好去了解其本质的方法，所以今天，我们来看看链表的增删查改。

       首先，我们来看看比较简单的头插、头删、尾插、尾删这四个：

一.前期准备：

对于前期准备我已经老调重弹了很多遍，这里不再过多赘述，首先最关键的就是链表节点的定义。

1. 链表节点的定义

       链表由一个个节点组成，每个节点包含两部分：数据域和指针域。数据域用来存储数据，指针域指向下一个节点。所以我们选择用结构体去定义节点：

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

代码解释：

1. typedef int SLTDataType：

       这行代码定义了一个类型别名 SLTDataType，它实际上是 int 的同义词。也就说可以选择直接在结构体内部用 int data；之所以这样做的目的是：

  • 提高代码可维护性：如果后续需要存储其他类型（如 float、char*），只需修改这一行，而不必改动整个代码。
  • 增强可读性：SLTDataType 比直接用 int 更直观，表示这是链表节点的数据类型。

2. struct SListNode 结构体定义

这个结构体定义了单链表的节点结构，包含两个成员：

SLTDataType data;

  • 数据域，用于存储具体的数据。
  • 由于 SLTDataType 被 typedef 为 int，因此这里实际上存储的是整数。

struct SListNode* next;

  • 指针域，指向下一个节点的地址。
  • 这是实现链表连接的关键：每个节点通过 next 指针指向下一个节点，直到最后一个节点的 next 为 NULL，表示链表结束。
  • 并非一个结构体，是一个结构体类型的指针

3. SLTNode;

这行代码将 struct SListNode 重命名为 SLTNode，目的是简化类型名。

  • 之后可以直接用 SLTNode 声明变量，而不需要写 struct SListNode。
  • 例如：SLTNode* node = malloc(sizeof(SLTNode));

二.打印函数：

为了更好地在测试文件里测试函数的可行性，我们首先写一个打印函数。

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

代码解释：

1. 定义遍历指针

SLTNode* cur = phead;
  • 创建一个临时指针 cur（current 的缩写，意为 “当前节点”），并将其初始化为头指针 phead。
  • 作用：用 cur 遍历链表，避免直接修改头指针 phead（如果直接移动 phead，会导致链表 “头节点丢失”，无法再访问整个链表）。

2. 遍历链表并打印数据

while (cur)
  • 循环条件 cur 等价于 cur != NULL，表示：只要当前节点 cur 不是空指针（即还没遍历到链表末尾），就继续循环。
printf("%d->", cur->data);
  • 打印当前节点 cur 的数据域 data（%d 对应 SLTDataType 为 int 的情况），并在后面加上 -> 符号，模拟链表的 “指向” 关系。
cur = cur->next;
  • 让 cur 指向当前节点的下一个节点（通过指针域 next），实现遍历的 “移动”。

3. 打印链表末尾标识

printf("NULL\n");

 

  • 当循环结束时（cur 变为 NULL，即遍历到链表末尾），打印 NULL，表示链表的终止。

三.尾插函数：

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->data = x;
	newnode->next = NULL;

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾：
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

代码解释：

函数定义解析：

void SLTPushBack(SLTNode** pphead, SLTDataType x)
  • 参数：
    • SLTNode** pphead：指向头指针的指针（二级指针）。因为尾插可能改变头指针（当链表为空时），必须通过二级指针修改原头指针的值。
    • SLTDataType x：要插入的数据（类型为 int，因为 SLTDataType 被 typedef 为 int）。
  • 返回值：void，只执行插入操作，不返回数据。

函数体详解

1. 断言检查

assert(pphead);
  • 确保传入的二级指针 pphead 不为空（即头指针的地址必须有效）。
  • 若 pphead 为空，程序会触发断言错误并终止（防止野指针）。

2. 创建新节点

SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
    perror("malloc fail");
    return;
}
newnode->data = x;
newnode->next = NULL;
  • 内存分配：用 malloc 动态分配一个节点大小的内存空间。
  • 错误处理：若 malloc 失败（返回 NULL），打印错误信息并提前返回。
  • 初始化节点：将数据 x 存入新节点的数据域 data，并将指针域 next 置为 NULL（因为新节点将成为尾节点）。

3. 处理链表为空的情况

if (*pphead == NULL)
{
    *pphead = newnode;
}
  • 若链表为空（头指针 *pphead 为 NULL），直接让头指针指向新节点。
  • 关键点：通过 *pphead 修改原头指针的值，使新节点成为链表的第一个节点。

4. 链表不为空时的尾插操作

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

 

  • 遍历找尾：从链表头开始，用 tail 指针遍历到最后一个节点（即 tail->next == NULL 的节点）。
  • 插入新节点：将尾节点的 next 指针指向新节点 newnode，使新节点成为新的尾节点。

函数定义进阶解析：

到这里相信很多人仍然对于二级指针那个点感到糊涂：为什么前面打印函数定义时就是一级指针，而到了插入函数开始就用二级指针了呢？下面我先顺着原始思路去解释，认为和打印函数一样用的是一级指针的代码和测试代码会如下：

void SLTPushBack(SLTNode* phead, SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->data = x;
	newnode->next = NULL;

	if (phead == NULL)
	{
		phead = newnode;
	}
	else
	{
		//找尾：
		SLTNode* tail = phead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void TestSList1()
{
	SLTNode* plist = NULL;
	SLTPushBack(plist, 1);
	SLTPushBack(plist, 2);
	SLTPushBack(plist, 3);
	SLTPushBack(plist, 4);

	SLTPrint(plist);
}

int main()
{
	TestSList1();

	return 0;
}

然而这样最终编译结果为：

我们可以看到，结果好像不是我们想要的，这是因为：

问题核心：形参与实参的区别

void SLTPushBack(SLTNode* phead, SLTDataType x)
  • 参数 phead 是实参的副本：当调用 SLTPushBack(plist, 1) 时，函数内部的 phead 是 plist 的拷贝，它们指向同一块内存，但本身是两个不同的变量。
  • 修改 phead 不影响实参 plist：在函数内部，当链表为空时执行 phead = newnode，只是修改了副本 phead 的值，原头指针 plist 仍为 NULL。

示例分析：

SLTNode* plist = NULL;  // plist 指向 NULL

第一次调用 SLTPushBack(plist, 1)：

  1. 传值调用：phead 是 plist 的副本，初始值为 NULL。
  2. 创建新节点：newnode 指向新分配的节点（数据为 1，next 为 NULL）。
  3. 执行 phead = newnode：phead 指向新节点，但 plist 仍为 NULL（因为 phead 是副本）。
  4. 函数返回：phead 被销毁，原 plist 未被修改，仍为 NULL。

后续调用 SLTPushBack(plist, 2)、SLTPushBack(plist, 3) 等：

  • 每次都重复上述过程，plist 始终为 NULL，所有新节点都无法连接到链表中。
  • 最终结果：链表为空，SLTPrint(plist) 输出 NULL。

正确做法：使用二级指针

void SLTPushBack(SLTNode** pphead, SLTDataType x)

 

  • 传址调用：pphead 是指向头指针 plist 的指针，通过 *pphead 可以直接修改原头指针。
  • 修改 *pphead 影响实参：当链表为空时，*pphead = newnode 直接将原头指针 plist 指向新节点。

 明白了这点之后，后续函数该用一级指针还是二级指针我们就清楚了。

四.新增节点函数：

完成尾插函数以后，我们发现需要开辟新的节点，我们也能预想到，后续函数也会用到新增节点，所以我们不妨封装这个函数，简化代码量：

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

之后在开辟时，直接调用即可；

五.头插函数：

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

代码解释： 

1. 断言检查

assert(pphead);
  • 确保传入的二级指针 pphead 不为空（即头指针的地址必须有效）。
  • 若 pphead 为空，程序会触发断言错误并终止（防止野指针）。

2. 创建新节点

SLTNode* newnode = BuySLTNode(x);
  • 调用 BuySLTNode 函数，创建一个新节点并初始化为数据 x，next 指针为 NULL。

3. 插入新节点到头部

newnode->next = *pphead;
*pphead = newnode;

 

  • 关键点：

    1. 将新节点的 next 指针指向原头节点（*pphead）。
    2. 将原头指针 *pphead 更新为新节点 newnode，使新节点成为链表的新头。

  • 无论链表是否为空，这两行代码都能正确工作：

    • 若链表为空（*pphead == NULL），新节点的 next 为 NULL，并成为唯一节点。
    • 若链表非空，新节点的 next 指向原头节点，实现头插。

头插函数很简约，理解起来也没什么大问题；

六.尾删函数：

void SLTPopBack(SLTNode** pphead)
{
	//暴力检查：
	assert(pphead);
	assert(*pphead);
	//只有一个节点；
	// 有多个节点；
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找尾：
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;

		prev->next = NULL;
	}
}

代码解释： 

1. 断言检查

assert(pphead);
assert(*pphead);
  • 第一个断言：确保传入的二级指针 pphead 不为空（防止野指针）。
  • 第二个断言：确保链表不为空（*pphead != NULL）。若链表为空时调用此函数，会触发断言错误，终止程序。

2. 处理只有一个节点的情况

if ((*pphead)->next == NULL)
{
    free(*pphead);
    *pphead = NULL;
}
  • 若链表只有一个节点（即头节点的 next 为 NULL）：
    1. 释放头节点的内存（free(*pphead)）。
    2. 将头指针置为 NULL（*pphead = NULL），表示链表已空。

3. 处理多个节点的情况

else
{
    SLTNode* prev = NULL;
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
        prev = tail;
        tail = tail->next;
    }
    free(tail);
    tail = NULL;
    prev->next = NULL;
}
  • 遍历找尾：
    • tail 指针遍历到最后一个节点，prev 始终指向 tail 的前一个节点。
  • 释放尾节点：
    1. 释放 tail 指向的尾节点（free(tail)）。
    2. 将 tail 置为 NULL（这一步是多余的，后面会解释）。
  • 更新链表：
    将 prev 的 next 置为 NULL，使 prev 成为新的尾节点。
  • 注意对于这段代码，while内的代码逻辑极其重要，不能找到尾以后就直接删去，这样将导致删完以后，尾部出现随机值的情况，需要格外注意！！！

但其实这段代码还存在一点小问题：

存在的问题：

free(tail);
tail = NULL;  // 这一步无效！
  • 问题：tail = NULL 仅将局部变量 tail 置为 NULL，无法影响原链表。
  • 原因：tail 是局部指针，free(tail) 后内存已释放，但 tail 本身仍保存着被释放内存的地址。将 tail 置为 NULL 只是修改了局部变量，对链表无影响。
  • 修正：删除 tail = NULL 这一行，因为它不影响链表结构，且是多余操作。

七.头删函数：

void SLTPopFront(SLTNode** pphead)
{
	//暴力检查：
	assert(pphead);
	assert(*pphead);

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

代码解释： 

1. 断言检查

assert(pphead);
assert(*pphead);
  • 第一个断言：确保传入的二级指针 pphead 不为空（防止野指针）。
  • 第二个断言：确保链表不为空（*pphead != NULL）。若链表为空时调用此函数，会触发断言错误，终止程序。

2. 保存原头节点并更新头指针

SLTNode* first = *pphead;
*pphead = first->next;

 

  • 关键点：
    1. 用临时指针 first 保存原头节点的地址。
    2. 将头指针 *pphead 更新为原头节点的下一个节点（first->next）。
  • 处理单节点情况：若链表只有一个节点，first->next 为 NULL，更新后头指针 *pphead 变为 NULL，链表为空。

3. 释放原头节点的内存

free(first);
first = NULL;

 

  • 释放内存：调用 free(first) 释放原头节点占用的内存。
  • 置空局部指针：将 first 置为 NULL（这一步是可选的，因为 first 是局部变量，函数返回后会被销毁）。

       这样一来，我们基础的尾插、尾删、头插、头删都已经讲完了，除了上面我们所关注到的细节点以外，还有一个点就是断言，我们发现有的地方加入了断言，有的地方没有，有的地方只有一个，而有的地方却有两个，我们来谈谈断言：

断言：

在 C 语言链表操作中，断言（assert） 是一种强大的调试工具，用于确保程序运行时的某些条件始终为真。

一、断言的本质与作用

断言是 C 标准库 <assert.h> 提供的宏，定义为：

void assert(int expression);

 

  • 功能：若 expression 为假（0），程序会立即终止，并打印错误信息（包括断言失败的位置、表达式内容）。
  • 目的：在开发和测试阶段尽早发现逻辑错误，避免程序在错误状态下继续运行导致更严重的问题。

二、链表操作中常见的断言场景

1. 检查指针有效性

assert(pphead);  // 确保二级指针（头指针的地址）不为NULL
  • 场景：在需要修改头指针的函数中（如 SLTPushBack、SLTPopFront），若传入的 pphead 为 NULL，后续解引用 *pphead 会导致野指针错误。
  • 错误示例： 
    SLTNode* plist = NULL;
SLTPushBack(NULL, 1);  // 错误：传入NULL作为pphead

2. 检查链表非空

assert(*pphead);  // 确保链表不为空（头指针不为NULL）
  • 场景：在删除操作（如 SLTPopBack、SLTPopFront）中，若链表为空，删除操作无意义且可能导致崩溃。
  • 错误示例： 
    SLTNode* plist = NULL;
SLTPopFront(&plist);  // 错误：对空链表执行头删

三、断言的优缺点

优点：

  1. 快速定位错误：断言失败时会直接打印错误位置和表达式，无需调试器即可快速发现问题。
  2. 强制约束条件：明确函数的前置条件（如 “链表必须非空”），提高代码安全性。
  3. 零运行时开销：在发布版本中可通过 #define NDEBUG 禁用断言，消除性能影响。

缺点：

  1. 仅在调试阶段有效：发布版本中断言被禁用，无法检查运行时错误。
  2. 可能掩盖真实问题：若断言条件过于严格，可能导致程序频繁崩溃，需谨慎设置。

所以，链表细节满满，需要大家多花时间去了解，剩下的一些函数，将会放到下一篇博客中，敬请期待......

 

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布