单链表基本操作的实现与解析(补充)
目录
一、引言
二、代码实现
遍历考虑情况
三、操作解析
查找操作（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后删函数，此处修改函数名为slteraseafter
void 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 。
四、应用场景与拓展
应用场景
数据管理系统：在小型数据管理系统中，单链表可用于存储和管理数据记录，如简单的学生信息管理系统，每个学生信息作为一个节点，通过单链表方便地进行插入、删除和查找操作。
缓存机制：在一些简单的缓存实现中，单链表可以用来管理缓存数据，通过删除最近最少使用的节点（后删操作）来为新数据腾出空间。
拓展
双向链表：单链表只能单向遍历，而双向链表在单链表基础上增加了指向前一个节点的指针，使得遍历更加灵活，可实现从后向前的查找和删除等操作。
循环链表：循环链表的尾节点指向头节点，形成一个环形结构，在一些需要循环处理数据的场景中，如循环队列的实现，循环链表能发挥独特的优势。
五、总结
通过上述代码和解析，我们对单链表的基本操作有了全面且深入的理解。这些操作是处理单链表的基石，在实际的算法设计和数据处理中频繁使用。掌握好单链表的操作，不仅能提升编程能力，更能为进一步学习其他复杂的数据结构和算法，如栈、队列、树等，打下坚实的基础。在实际应用中，应根据具体需求选择合适的数据结构和操作方法，以实现高效的数据处理和算法设计。