带头结点的单链表删除指定位置结点

1. 功能概述

bool ListDelete(LinkList &L, int i, ElemType &e) 函数的功能是：在带头结点的单链表 L 中，删除第 i 个位置的结点，并将被删除结点的数据通过引用参数 e 带回给调用者。

• 函数名: ListDelete，清晰表达了其功能。
  
• 返回值: bool 类型。true 表示删除成功，false 表示删除失败（例如，位置 i 不合法）。
  
• 参数:
  
  
  
  • LinkList &L: 链表的头指针（指向头结点），使用引用传递，意味着函数内部对链表的修改会直接作用于原始链表。
    
  • int i: 要删除的结点的位序（从1开始计数）。
    
  • ElemType &e: 一个引用参数，用于“返回”被删除结点的数据值。这是一种常见的C++技巧，比使用全局变量或指针返回值更安全、更优雅。
    
  
  

2. 代码逐行分析

1. bool ListDelete(LinkList &L, int i, ElemType &e) {
2.     // 1. 边界条件检查：位序是否合法
3.     if (i < 1) return false;         

复制代码

• 逻辑: 链表的位序是从1开始的。如果传入的 i 小于1，它肯定是一个非法位置。
  
• 优点: 这是最先进行的检查，可以快速处理无效输入，提高代码的健壮性。这是一种“防御性编程”的体现。
  

1.     // 2. 初始化指针和计数器
2.     LNode *p = L;                     // p指向头结点
3.     int j = 0;                        // 计数器

复制代码

• 逻辑:
  
  
  
  • LNode *p = L;: 声明一个指针 p，并让它指向链表的头结点。这是遍历链表的起点。注意：p 指向的是头结点，而不是第一个数据结点。头结点的位序可以看作是 0。
    
  • int j = 0;: 声明一个计数器 j，用来记录当前指针 p 指向的是第几个结点。因为 p 从头结点（位序0）开始，所以 j 初始化为 0。
    
  
  

1.     // 3. 循环查找第 i-1 个结点
2.     while (p != NULL && j < i-1) {   
3.         p = p->next;
4.         j++;
5.     }

复制代码

• 逻辑: 这是整个算法的核心步骤之一。循环的目标是让指针 p 移动到待删除结点的前驱结点上。
  
  
  
  • 为什么是 i-1？ 因为在单链表中，要删除一个结点，必须找到它的前一个结点，然后通过修改前驱结点的 next 指针来“跳过”待删除结点。我们无法直接访问一个结点的前驱。
    
  • 循环条件:
    
    
    
    • p != NULL: 确保指针没有走到链表的末尾。如果 p 已经是 NULL，说明链表长度不足 i-1，位置 i 肯定不合法。
      
    • j < i-1: 只要计数器 j 还没达到 i-1，就继续向后移动。
      
    
    
  
  
• 循环结束后 p 的状态:
  
  
  
  • 成功情况: p 指向了第 i-1 个结点。
    
  • 失败情况: p 变成了 NULL，说明链表长度小于 i-1。
    
  
  

1.     // 4. 再次检查位置i的合法性
2.     if (p == NULL || p->next == NULL)
3.         return false;

复制代码

• 逻辑: 在 while 循环结束后，需要进行一次最终的合法性检查。这个检查非常关键，它处理了两种失败情况：
  
  
  
  • p == NULL: 对应 while 循环因为 p != NULL 条件不满足而退出的情况。说明链表太短，根本没有第 i-1 个结点。
    
  • p->next == NULL: 这种情况更微妙。它说明虽然找到了第 i-1 个结点（p不为空），但这个结点是链表的最后一个结点，它后面没有第 i 个结点了。因此，i 的值等于链表长度+1，同样是一个非法位置。
    
  
  
• 优点: 这个双重检查确保了所有非法的 i 值（太小或太大）都能被捕获。
  

1.     // 5. 执行删除操作
2.     LNode *q = p->next;               // q指向待删除结点
3.     e = q->data;                      // 保存删除结点的值
4.     p->next = q->next;                // 前驱结点跳过q
5.     free(q);                          // 释放q的内存

复制代码

• 逻辑: 如果通过了所有检查，说明删除操作是安全的，可以执行。
  
  
  
  • LNode *q = p->next;: 创建一个临时指针 q，让它指向待删除的结点（即第 i 个结点）。这样做是为了后续能安全地释放它的内存。
    
  • e = q->data;: 将待删除结点的数据存入引用参数 e，以便调用者获取。
    
  • p->next = q->next;: 这是删除操作的核心。将前驱结点 p 的 next 指针，修改为指向待删除结点 q 的后继结点。这样，从 p 开始遍历，就会跳过 q，q 结点就从链表中“断开”了。
    
  • free(q);: 至关重要的一步。使用 free() 函数释放 q 所指向的内存空间。如果不释放，就会造成内存泄漏（Memory Leak），被删除的结点所占用的内存将永远无法被程序再次使用，直到程序结束。
    
  
  

1.     // 6. 返回成功
2.     return true;
3. }

复制代码

• 逻辑: 所有操作都成功完成，返回 true 表示删除成功。
  

3. 算法复杂度分析

• 时间复杂度: O(n)
  
  
  
  • 最坏情况：删除链表的最后一个结点（i = n），需要从头结点开始遍历整个链表，执行 n-1 次移动。
    
  • 最好情况：删除第一个结点（i = 1），while 循环条件 j < 0 不满足，直接跳过，时间复杂度为 O(1)。
    
  • 平均情况：在任意位置删除的概率均等，平均需要移动 (n-1)/2 次。
    
  • 综合来看，时间复杂度与链表长度 n 呈线性关系，因此为 O(n)。主要时间消耗在查找第 i-1 个结点的过程。
    
  
  
• 空间复杂度: O(1)
  
  
  
  • 算法只使用了固定数量的指针变量（p, q）和整型变量（j），这些额外占用的内存空间不随链表规模 n 的变化而变化。因此，空间复杂度是常数级 O(1)。
    
  
  

4. 优点与潜在问题

优点:

• 逻辑清晰，结构标准: 完全遵循了“检查 -> 查找 -> 修改 -> 释放”的标准单链表操作范式，易于理解和教学。
  
• 健壮性强: 通过 if (i < 1) 和 if (p == NULL || p->next == NULL) 两道防线，处理了所有可能的非法输入，保证了程序的稳定性。
  
• 正确性高: 代码逻辑严谨，特别是对 p->next == NULL 的检查，确保了不会对链表末尾之后的位置进行操作。
  
• 资源管理良好: 使用 free(q) 释放了被删除结点的内存，避免了内存泄漏，这是良好编程习惯的体现。
  
• 接口设计合理: 使用引用参数 &e 返回被删除的元素值，比使用指针或全局变量更符合现代C++的编程风格。
  

总结

这是一段高质量、教科书级别的单链表删除操作实现。它清晰地展示了算法的核心思想，并且在健壮性和资源管理方面都做得很好。对于学习数据结构的初学者来说，这是一个极佳的范例。唯一的改进点是在纯C++项目中，应将 free() 替换为 delete 以保持内存管理风格的一致性。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！