第二章数据结构线性表 – 单链表的插入和删除操作

一、知识要点

1.1 按位序插入 – 带头结点

1.2 按位序插入 – 不带头结点

1.3 指定结点的后插操作

1.4 指定结点的前插操作

1.5 按位序删除（带头结点）

1.6 指定结点删除

1.7 封装的好处

二、单链表 – 插入操作

3.1 按位序插入（带头结点） – ListInsert(&L，i，e)

ListInsert(&L，i，e) : 插入操作。在表L中的第 i 个位置上插入指定元素e。

c语言代码实现

#include <stdio.h>
#include <stdlib.h>

// 单链表节点定义（考研标准写法）
typedef struct LNode {
    int data;          // 数据域
    struct LNode *next;// 指针域
} LNode, *LinkList;     // LNode是节点类型，LinkList是链表类型（指向头节点的指针）

/**
 * 按位序插入操作：在链表L的第i个位置插入元素e
 * @param L 指向链表头指针的指针（用于可能修改头节点的情况）
 * @param i 插入位置（从1开始计数）
 * @param e 要插入的元素值
 * @return 插入成功返回1，失败返回0
 */
int ListInsert(LinkList *L, int i, int e) {
    // 1. 检查位置合法性（i不能小于1）
    if (i < 1) return 0;

    // 2. 查找第i-1个节点（p最终指向i-1号节点）
    LNode *p = *L;       // p初始指向头节点（头节点是第0个节点）
    int j = 0;           // 计数器，记录当前p指向的是第j个节点
    while (p != NULL && j < i - 1) { // 循环条件：p不为空且未到达i-1位置
        p = p->next;     // p后移
        j++;             // 计数器递增
    }

    // 3. 若i-1位置不存在（p为NULL说明i超过链表长度+1）
    if (p == NULL) return 0;

    // 4. 创建新节点（考研中通常不处理malloc失败的情况）
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;

    // 5. 插入操作（关键步骤）
    s->next = p->next;   // 新节点的next指向原i-1节点的后继
    p->next = s;         // 原i-1节点的next指向新节点

    return 1;            // 插入成功
}

// 测试函数（考研中可能需要自行编写测试用例）
int main() {
    // 初始化带头节点的空链表
    LinkList L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;

    // 测试插入操作：在第1个位置插入5
    ListInsert(&L, 1, 5);  // 链表变为：头节点 -> 5 -> NULL

    // 在第2个位置插入10
    ListInsert(&L, 2, 10); // 链表变为：头节点 -> 5 -> 10 -> NULL

    // 在第1个位置插入3（头插法效果）
    ListInsert(&L, 1, 3);  // 链表变为：头节点 -> 3 -> 5 -> 10 -> NULL

    // 遍历输出链表验证
    LNode *p = L->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    // 输出结果应为：3 5 10
    return 0;
}

这段代码实现了带头节点的单链表按位序插入操作，并通过main函数进行了测试验证。以下是代码的详细执行过程分析：

一、基础结构：单链表节点定义

首先看节点结构体的定义：

typedef struct LNode {
    int data;          // 数据域（存储具体数值）
    struct LNode *next;// 指针域（指向下一个节点）
} LNode, *LinkList;     // LNode是节点类型，LinkList是链表类型（指向头节点的指针）

• LNode：表示一个具体的链表节点（包含数据和指向下一个节点的指针）。
• LinkList：本质是LNode*（指向节点的指针），通常作为链表的头指针（指向头节点）。

二、核心函数：ListInsert（按位序插入）

函数功能是在链表的第i个位置插入元素e，关键步骤如下：

1. 位置合法性检查

if (i < 1) return 0;  // 位序从1开始，i=0或负数不合法

• 单链表的位序从 1 开始计数（第一个数据节点是位置 1），因此i < 1时直接返回失败。

2. 查找第i-1个节点（前驱节点）

LNode *p = *L;       // p初始指向头节点（头节点是第0个节点）
int j = 0;           // 计数器：p当前指向第j个节点（头节点是j=0）
while (p != NULL && j < i - 1) { 
    p = p->next;     // p后移
    j++;             // 计数器递增
}

• 为什么找i-1节点？：插入第i个位置时，需要将新节点插入到第i-1个节点之后（例如在位置 2 插入，需要找到位置 1 的节点，将新节点接在它后面）。
• 头节点的作用：头节点是链表的 “哨兵”（第 0 个节点），不存储数据。即使插入位置是 1（第一个数据位置），也可以通过头节点找到前驱（头节点本身就是i-1=0的节点）。
• 循环终止条件：p != NULL确保不越界（如果链表长度不足i-1，p会变成NULL）；j < i-1确保找到第i-1个节点。

3. 检查前驱节点是否存在

if (p == NULL) return 0;  // 若i-1位置不存在（链表长度不足），插入失败

• 如果p为NULL，说明链表长度不够（例如链表只有 2 个数据节点，但尝试在位置 4 插入），此时无法插入。

4. 创建新节点并插入

LNode *s = (LNode *)malloc(sizeof(LNode));  // 分配内存
s->data = e;                                 // 存储数据e
s->next = p->next;                           // 新节点的next指向原i-1节点的后继
p->next = s;                                 // 原i-1节点的next指向新节点

• 指针操作顺序：必须先将新节点的next指向原i-1节点的后继（p->next），再将p->next指向新节点。如果顺序颠倒，会导致原i-1节点的后继丢失（断链）。

三、测试函数：main的执行过程

main函数初始化了一个带头节点的空链表，并进行了 3 次插入操作，最终遍历输出结果。

1. 初始化空链表

LinkList L = (LNode *)malloc(sizeof(LNode));  // 创建头节点
L->next = NULL;                               // 头节点的next为空（空链表）

此时链表结构：
头节点（data无意义） -> NULL

2. 第一次插入：ListInsert(&L, 1, 5)

• 目标：在位置 1 插入元素 5。
• 执行过程：
  • i=1，检查i >= 1合法。
  • 查找i-1=0的节点（即头节点）：p初始指向头节点，j=0，循环j < 0不成立，p仍指向头节点。
  • p不为NULL，创建新节点s（data=5）。
  • s->next = p->next（p->next是NULL，所以s->next=NULL）。
  • p->next = s（头节点的 next 指向s）。
• 插入后链表：
  头节点 -> 5（位置1） -> NULL

3. 第二次插入：ListInsert(&L, 2, 10)

• 目标：在位置 2 插入元素 10。
• 执行过程：
  • i=2，检查i >= 1合法。
  • 查找i-1=1的节点：p初始指向头节点（j=0），循环j < 1成立，p后移指向位置 1 的节点（data=5），j=1，循环结束。
  • p不为NULL，创建新节点s（data=10）。
  • s->next = p->next（p->next是NULL，所以s->next=NULL）。
  • p->next = s（位置 1 的节点的 next 指向s）。
• 插入后链表：
  头节点 -> 5（位置1） -> 10（位置2） -> NULL

4. 第三次插入：ListInsert(&L, 1, 3)

• 目标：在位置 1 插入元素 3（头插法效果）。
• 执行过程：
  • i=1，检查i >= 1合法。
  • 查找i-1=0的节点（头节点）：p初始指向头节点，j=0，循环j < 0不成立，p仍指向头节点。
  • p不为NULL，创建新节点s（data=3）。
  • s->next = p->next（p->next是位置 1 的节点，即 data=5 的节点）。
  • p->next = s（头节点的 next 指向s）。
• 插入后链表：
  头节点 -> 3（位置1） -> 5（位置2） -> 10（位置3） -> NULL

5. 遍历输出验证

LNode *p = L->next;  // p指向第一个数据节点（位置1）
while (p != NULL) {
    printf("%d ", p->data);  // 输出3 5 10
    p = p->next;
}

最终输出结果为3 5 10，与预期一致。

总结

这段代码通过带头节点的单链表实现了按位序插入操作，核心逻辑是：

1. 检查插入位置合法性；
2. 找到插入位置的前驱节点（第i-1个节点）；
3. 通过修改指针将新节点插入到前驱节点之后。

测试用例验证了不同位置的插入（头插、中间插、尾插），最终输出结果正确，说明插入操作实现正确。

3.2 按位序插入（不带头结点） – ListInsert(&L，i，e)

三、单链表 – 不带头结点