PTA（链表）1-3 递增的整数序列链表的插入

1-3 递增的整数序列链表的插入

分数 4

作者 DS课程组

单位 浙江大学

本题要求实现一个函数，在递增的整数序列链表（带头结点）中插入一个新整数，并保持该序列的有序性。

函数接口定义：

1
List Insert( List L, ElementType X );

其中List结构定义如下：

1
2
3
4
5
6
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Insert要将X插入L，并保持该序列的有序性，返回插入后的链表头指针。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表 */

List Insert( List L, ElementType X );

int main()
{
    List L;
    ElementType X;
    L = Read();
    scanf("%d", &X);
    L = Insert(L, X);
    Print(L);
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

1
2
3
5
1 2 4 5 6
3

输出样例：

1
1 2 3 4 5 6

我的段错误答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
List Insert( List L, ElementType X ) {
    List p = L->Next; // 定义指针p，用于遍历链表L,初始指向第一个结点
    // 特殊情况：比第一个还小,插在第一个的前面
    if (X < p->Data) {
        List newNode = (List) malloc(sizeof (struct Node));
        newNode->Data = X;
        newNode->Next = L->Next;
        L->Next = newNode;
        return L;
    }
    // 插在中间的情况
    while (p->Next != NULL) {
        if (p->Data <= X && X <= p->Next->Data) { // X位于两个结点中间，插入
            List newNode = (List) malloc(sizeof (struct Node));
            newNode->Data = X;
            newNode->Next = p->Next;
            p->Next = newNode;
            return L;
        }
        p = p->Next;
    }
    // 特殊情况：如果比最后一个还大
    if (p->Next == NULL && p->Data < X) {
        List newNode = (List) malloc(sizeof (struct Node));
        newNode->Data = X;
        newNode->Next = NULL;
        p->Next = newNode;
        return L;
    }
    return L;
}

段错误是啥

程序非法访问了不属于它的内存区域

本质是程序违反了内存访问规则，常见场景包括：

  1. 解引用空指针：访问 NULL 指针或未初始化的野指针的成员（比如 NULL->Data）。
  2. 越界访问数组 / 链表：比如数组下标超出范围、链表遍历到 NULL 后仍继续访问下一个节点。
  3. 访问已释放的内存：内存被 free 后再次访问，或使用已销毁的栈变量指针。
  4. 栈溢出：递归过深、局部数组过大等导致栈内存超出限制。
  5. 修改只读内存：比如试图修改字符串常量（如 char *s = "abc"; s[0] = '1'）。

排查思路

  1. 检查指针初始化：确保所有指针使用前已正确赋值，避免 NULL 指针解引用。
  2. 验证内存访问边界：链表遍历前判断指针是否为 NULL，数组访问确认下标在合法范围。
  3. 规范内存管理：避免重复释放内存、访问已释放的内存。
  4. 使用调试工具：通过 gdb（Linux）、IDE 调试功能（如 CLion 的断点调试）跟踪指针值变化，定位非法访问的代码行。

我段错误原因

1
2
3
List p = L->Next; // 定义指针p，用于遍历链表L,初始指向第一个结点
    // 特殊情况：比第一个还小,插在第一个的前面
    if (X < p->Data) {...

如果是空链表，头结点后面是NULL，p->Data相当于NULL->Data，解引用空指针

正确答案（复杂）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
List Insert( List L, ElementType X ) {
    // 处理空链表（只有头结点，没有数据节点）
    if (L->Next == NULL) {
        List newNode = (List)malloc(sizeof(struct Node));
        newNode->Data = X;
        newNode->Next = NULL;
        L->Next = newNode;
        return L;
    }
    List p = L->Next; // 定义指针p，用于遍历链表L,初始指向第一个结点
    // 特殊情况：比第一个还小,插在第一个的前面
    if (X < p->Data) {
        List newNode = (List) malloc(sizeof (struct Node));
        newNode->Data = X;
        newNode->Next = L->Next;
        L->Next = newNode;
        return L;
    }
    // 插在中间的情况
    while (p->Next != NULL) {
        if (p->Data <= X && X <= p->Next->Data) { // X位于两个结点中间，插入
            List newNode = (List) malloc(sizeof (struct Node));
            newNode->Data = X;
            newNode->Next = p->Next;
            p->Next = newNode;
            return L;
        }
        p = p->Next;
    }
    // 特殊情况：如果比最后一个还大
    if (p->Next == NULL && p->Data < X) {
        List newNode = (List) malloc(sizeof (struct Node));
        newNode->Data = X;
        newNode->Next = NULL;
        p->Next = newNode;
        return L;
    }
    return L;
}

这段代码可以简化，核心是利用一个指针遍历找到插入位置，无需拆分多个特殊情况判断。简化后的版本保留了所有功能

正确答案（简化）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Node {
    ElementType Data;
    struct Node *Next;
};
typedef struct Node *List;

List Insert(List L, ElementType X) {
    List p = L;  // 从表头开始遍历（更灵活）
    
    // 找到插入位置：p的下一个节点值大于X，或p是最后一个节点
    while (p->Next != NULL && p->Next->Data < X) {
        p = p->Next;
    }
    
    // 此时p就是要插入的前一个节点，统一处理所有插入情况
    List newNode = (List)malloc(sizeof(struct Node));
    newNode->Data = X;
    newNode->Next = p->Next;  // 新节点指向p原来的下一个节点
    p->Next = newNode;        // p指向新节点
    
    return L;
}

豆包比我聪明多了

简化思路说明：

  1. 统一插入逻辑：
    • 用 p 从表头开始遍历（而非第一个数据节点），找到 “下一个节点值大于 X” 的位置
    • 无论插入在头部、中间还是尾部，都可以用相同的代码完成插入（利用 p->Next 连接）
  2. 减少条件判断：
    • 原代码中的 “空链表”“头部插入”“尾部插入” 等特殊情况，被while循环的条件自然覆盖：
      • 空链表时，p->Next 为 NULL，直接插入
      • 插入头部时，p 停留在表头（L）
      • 插入尾部时，p 停留在最后一个节点
  3. 代码更健壮：
    • 无需单独处理各种边界情况，逻辑更清晰
    • 所有路径都能正确返回，避免编译错误