单链表基本操作的实现与解析(补充)

一、引言

二、代码实现

遍历考虑情况

三、操作解析

查找操作（sltfind函数）

前插操作（sltinsert函数）

后插操作（sltinsertafter函数）

前删操作（slterase函数）

后删操作（slteraseafter函数）

四、应用场景与拓展

应用场景

拓展

五、总结

一、引言

作者主页：共享家9527-CSDN博客

作者小仓库：https://blog.csdn.net/nplplus/category_12904039.html?fromshare=blogcolumn&sharetype=blogcolumn&sharerId=12904039&sharerefer=PC&sharesource=nplplus&sharefrom=from_link

单链表作为一种基础且常用的数据结构，在计算机科学领域应用广泛。它以节点为基本单元，通过指针构建节点间的线性关系，每个节点包含数据域与指向下一节点的指针域。这种链式存储结构相比数组，在内存使用上更加灵活，无需连续的内存空间。在实际编程中，对单链表执行查找、插入和删除等操作是数据处理和算法设计的基础，理解和掌握这些操作，对后续学习复杂数据结构与算法至关重要。本文将结合具体的C语言代码，深入且细致地剖析单链表的这些基本操作。

二、代码实现

c#include <stdio.h>#include <stdlib.h>#include <assert.h>// 定义单链表节点结构typedef int SLTDataType;typedef struct SLTNode {SLTDataType data;struct SLTNode* next;} SLTNode;// 创建新节点的函数SLTNode* BuySLTNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("malloc");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;}// 查找函数SLTNode* sltfind(SLTNode* pphead, int x) {SLTNode* cur = pphead;while (cur) {if (cur->data == x) {return cur;}else {cur = cur->next;}}return NULL;}// pos前插函数void sltinsert(SLTNode** pphead, SLTNode* pos, int x) {assert(pphead);assert(pos);if (pos == *pphead) {SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;}else {SLTNode* pre = *pphead;while (pre->next != pos) {pre = pre->next;}SLTNode* newnode = BuySLTNode(x);pre->next = newnode;newnode->next = pos;}}// pos后插函数void sltinsertafter(SLTNode* pos, int x) {assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;}// pos前删函数void slterase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(pos);if (pos == *pphead) {SLTNode* temp = *pphead;*pphead = (*pphead)->next;free(temp);}else {SLTNode* pre = *pphead;while (pre->next != pos) {pre = pre->next;}pre->next = pos->next;free(pos);}}// pos后删函数，此处修改函数名为slteraseaftervoid slteraseafter(SLTNode* pos) {assert(pos);assert(pos->next);SLTNode* mid = pos->next;pos->next = pos->next->next;free(mid);mid = NULL;}

遍历考虑情况

三、操作解析

查找操作（sltfind函数）

- 函数功能：此函数用于在单链表中查找特定数据值 x 所在的节点。

- 参数：接受链表头指针 pphead 和要查找的值 x 。

- 执行过程：从链表头节点开始，通过 while 循环依次遍历每个节点。在每次循环中，将当前节点 cur 的数据与目标值 x 进行比较。若相等，说明找到目标节点，直接返回该节点指针；若不相等，则将 cur 指向下一个节点继续查找。当遍历完整个链表仍未找到匹配值时，返回 NULL 。例如，在一个包含节点数据为 1, 3, 5, 7 的链表中查找值为 5 的节点，当 cur 遍历到第三个节点时，数据匹配，函数返回该节点指针。

前插操作（sltinsert函数）

- 函数功能：在指定位置 pos 之前插入一个新节点，新节点的数据为 x 。

- 参数：需要链表头指针的二级指针 pphead （用于修改头指针）、插入位置的指针 pos 以及要插入的值 x 。

- 执行过程：首先使用 assert 进行断言检查，确保传入的头指针和插入位置指针有效。若插入位置 pos 恰好是头节点，直接创建新节点，让新节点的 next 指向原头节点，然后更新头指针指向新节点，这样新节点就插入到了头节点之前。若 pos 不是头节点，则从链表头节点开始，通过 while 循环查找 pos 的前一个节点 pre 。找到后，创建新节点，将 pre 的 next 指向新节点，新节点的 next 再指向 pos ，完成插入操作。比如，在链表 1 -> 3 -> 5 中，要在值为 3 的节点前插入值为 2 的节点，先找到值为 1 的节点（即 3 节点的前一个节点），然后按上述步骤插入新节点，链表变为 1 -> 2 -> 3 -> 5 。

后插操作（sltinsertafter函数）

- 函数功能：在指定节点 pos 之后插入一个新节点，新节点的数据为 x 。

- 参数：接受插入位置的指针 pos 和要插入的值 x 。

- 执行过程：先使用 assert 检查 pos 是否有效。然后创建新节点，将新节点的 next 指针指向 pos 的下一个节点，再将 pos 的 next 指针指向新节点。例如，在链表 1 -> 3 -> 5 中，在值为 3 的节点后插入值为 4 的节点，新节点 4 的 next 指向原 3 节点的下一个节点 5 ，然后 3 节点的 next 指向新节点 4 ，链表变为 1 -> 3 -> 4 -> 5 。

前删操作（slterase函数）

- 函数功能：删除指定位置 pos 的节点。

- 参数：接受链表头指针的二级指针 pphead 和要删除节点的指针 pos 。

- 执行过程：首先进行断言检查，保证头指针和要删除节点指针有效。若要删除的节点 pos 是头节点，先保存头节点到临时变量 temp ，然后将头指针更新为原头节点的下一个节点，最后释放 temp 节点的内存。若 pos 不是头节点，则从链表头节点开始，通过 while 循环找到 pos 的前一个节点 pre 。找到后，将 pre 的 next 指针直接指向 pos 的下一个节点，然后释放 pos 节点的内存。比如，在链表 1 -> 3 -> 5 中删除值为 3 的节点，先找到值为 1 的节点（即 3 节点的前一个节点），然后修改指针，将 1 节点的 next 指向 5 节点，再释放 3 节点的内存，链表变为 1 -> 5 。

后删操作（slteraseafter函数）

- 函数功能：删除指定节点 pos 之后的节点。

- 参数：接受删除位置的指针 pos 。

- 执行过程：先使用 assert 检查 pos 及其下一个节点是否有效。然后保存 pos 的下一个节点到 mid ，将 pos 的 next 指针指向 mid 的下一个节点（即 pos 的下下个节点），最后释放 mid 节点的内存。例如，在链表 1 -> 3 -> 5 -> 7 中，删除值为 3 节点后的节点（即值为 5 的节点），先保存 5 节点到 mid ，然后将 3 节点的 next 指向 7 节点，再释放 5 节点的内存，链表变为 1 -> 3 -> 7 。

四、应用场景与拓展

应用场景

数据管理系统：在小型数据管理系统中，单链表可用于存储和管理数据记录，如简单的学生信息管理系统，每个学生信息作为一个节点，通过单链表方便地进行插入、删除和查找操作。

缓存机制：在一些简单的缓存实现中，单链表可以用来管理缓存数据，通过删除最近最少使用的节点（后删操作）来为新数据腾出空间。

拓展

双向链表：单链表只能单向遍历，而双向链表在单链表基础上增加了指向前一个节点的指针，使得遍历更加灵活，可实现从后向前的查找和删除等操作。

循环链表：循环链表的尾节点指向头节点，形成一个环形结构，在一些需要循环处理数据的场景中，如循环队列的实现，循环链表能发挥独特的优势。

五、总结

通过上述代码和解析，我们对单链表的基本操作有了全面且深入的理解。这些操作是处理单链表的基石，在实际的算法设计和数据处理中频繁使用。掌握好单链表的操作，不仅能提升编程能力，更能为进一步学习其他复杂的数据结构和算法，如栈、队列、树等，打下坚实的基础。在实际应用中，应根据具体需求选择合适的数据结构和操作方法，以实现高效的数据处理和算法设计。