练习2-1 带空头结点的单链表操作

带空头结点的单链表操作

分数 20

作者 陈越

单位 浙江大学

如果链表采用带空头结点的方式实现，请修改算法 2-7（单链表插入）和算法 2-8（单链表删除），实现相应的插入和删除操作。

函数接口定义：

void Insert (List list, int i, ElemSet x); /* 在单链表 list 的第 i 个位置上插入元素 x */
void Remove ( List list, int i );          /* 从单链表 list 中删除第 i 个元素 */

其中 List 结构定义如下：

typedef struct ListNode *Position; /* 指针即结点位置 */
struct ListNode {
    ElemSet data;  /* 存储数据*/
    Position next; /* 线性表中下一个元素的位置 */
};
typedef struct HeadNode *List;
struct HeadNode {
    Position head; /* 单链表头指针 */
    int length;    /* 表长 */
};

函数接口定义中，i 是元素 x 需要被插入或删除的位序（从 1 开始）；ElemSet 是用户定义的数据类型，例如 int、double 或者 char 等。若传入的位序 i 不是合理的位置，则在一行中打印 ERROR。注意：list 的头指针 head 指向一个空的头结点，这个结点里不存任何真实数据。

裁判测试程序样例：

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

typedef int ElemSet;
typedef struct ListNode *Position; /* 指针即结点位置 */
struct ListNode {
    ElemSet data;  /* 存储数据*/
    Position next; /* 线性表中下一个元素的位置 */
};
typedef struct HeadNode *List;
struct HeadNode {
    Position head; /* 单链表头指针 */
    int length;    /* 表长 */
};

void Insert (List list, int i, ElemSet x);
void Remove ( List list, int i );

int main(void)
{
    int i, n, x;
    Position p;
    List list;
    
    list = (List)malloc(sizeof(struct HeadNode));
    list->head = (Position)malloc(sizeof(struct ListNode)); /* 创建空头结点 */;
    list->head->next = NULL;
    list->length = 0;
    scanf("%d: ", &n);
    for (i=1; i<=n; i++) {
        scanf("%d", &x);
        Insert(list, i, x);
    }
    scanf("%d", &i);
    if (scanf("%d", &x)!=EOF) {
        Insert(list, i, x);
    }
    else {
        Remove(list, i);
    }
    printf("%d:", list->length);
    p = list->head->next;
    while (p != NULL) {
        printf(" %d", p->data);
        p = p->next;
    }
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例 1：

3: 1 2 5
2 3

输出样例 1：

4: 1 3 2 5

输入样例 2：

6: 4 1 3 2 5 8
3

输出样例 2：

5: 4 1 2 5 8

输入样例 3：

6: 4 1 3 2 5 8
0 0

输出样例 3：

ERROR
6: 4 1 3 2 5 8

解析

void Insert(List list, int i, ElemSet x)
{
    // 检查i是否在有效范围内
    if (i < 1 || i > list->length + 1)
    {
        printf("Error\n");
        return;
    }
    

    // 为新节点分配内存
    Position Newnote = (Position)malloc(sizeof(struct ListNode));
    if (Newnote == NULL)  // 添加内存分配失败检查
    {
        printf("Error\n");
        return;
    }
    Newnote->data = x;
    Newnote->next = NULL;
    
    Position p = list->head;
    // 找到第i-1个节点
    for (int j = 1; j < i; j++)
    {
        p = p->next;
        // 防止意外的空指针访问（额外安全检查）
        if (p == NULL)
        {
            printf("Error\n");
            free(Newnote);
            return;
        }
    }
    
    // 插入新节点
    Newnote->next = p->next;
    p->next = Newnote;
    list->length++;
}

void Remove(List list, int i)
{
    // 检查链表是否为空
    if (list->length == 0)
    {
        printf("Error\n");
        return;
    }
    

    // 检查i是否在有效范围内
    if (i < 1 || i > list->length)
    {
        printf("Error\n");
        return;
    }
    
    Position p = list->head;
    // 找到第i-1个节点
    for (int j = 1; j < i; j++)
    {
        p = p->next;
        // 防止意外的空指针访问
        if (p == NULL || p->next == NULL)
        {
            printf("Error\n");
            return;
        }
    }
    
    // 删除第i个节点
    Position q = p->next;
    p->next = q->next;
    free(q);
    list->length--;
}

注意

一个插入或删除，首先要进行位置有效性检查：

插入时：插入点在1到length+1之间

删除时：删除点也必须在1到length之间

然后是插入操作

看是顺序表还是单链表，链表只用改指针，顺序表要一个一个往后挪

  1. Insert 函数：
    • 合法性判断：i 必须在 [1, list->length + 1] 范围内（允许在链表末尾插入）。
    • 指针操作：先让新节点的 next 指向 “前驱节点的原后继”，再让 “前驱节点的 next 指向新节点”，确保后续节点不丢失。
    • 表长更新：插入成功后长度 +1。
  2. Remove 函数：
    • 合法性判断：i 必须在 [1, list->length] 范围内（需存在要删除的节点）。
    • 指针操作：先保存 “待删除节点”，再让 “前驱节点的 next 跳转到待删除节点的后继”，最后释放待删除节点。
    • 表长更新：删除成功后长度 -1。

实验2-1 求链式线性表的倒数第 m 项

分数 20

作者 陈越

单位 浙江大学

请设计时间和空间上都尽可能高效的算法，求链式存储的线性表的倒数第m（>0）个元素。

函数接口定义：

ElemSet Find( List list, int m );

其中List结构定义如下：

typedef struct ListNode *Position; /* 指针即结点位置 */
typedef Position List;
struct ListNode {
    ElemSet data;  /* 存储数据 */
    Position next;  /* 线性表中下一个元素的位置 */
};

函数接口定义中，ElemSet 是用户定义的数据类型，例如 int、double 或者 char 等。函数 Find 的功能是，返回带空头结点的单链表 list 的倒数第 m 个元素的值，并且不得对 list 做任何改变。如果这样的元素不存在，则返回一个错误标志 ERROR（这个标志的值由裁判程序定义）。

裁判测试程序样例：

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

#define ERROR -1
typedef int ElemSet;
typedef struct ListNode *Position; /* 指针即结点位置 */
typedef Position List;
struct ListNode {
    ElemSet data;   /* 存储数据 */
    Position next;  /* 线性表中下一个元素的位置 */
};

List ReadList()
{ /* 创建带空头结点的、有n个数据结点的单链表 */
    List p, rear;
    int n;
    scanf("%d", &n);
    p = (List)malloc(sizeof(struct ListNode));
    p->next = NULL;
    rear = p;
    while (n--) { /* 新读入的数据插在链表尾 */
        rear->next = (List)malloc(sizeof(struct ListNode));
        scanf("%d", &rear->next->data);
        rear->next->next = NULL;
        rear = rear->next;
    }
    return p;
}

void PrintList( List list )
{ /* 顺序输出带空头结点的单链表的结点数据 */
    while (list->next != NULL) {
        list = list->next;
        printf("%d ", list->data);
    }
    printf("\n");
}

ElemSet Find( List list, int m );

int main(void)
{
    List list;
    int m;
    
    list = ReadList();
    scanf("%d", &m);
    printf("%d\n", Find(list, m));
    PrintList(list);
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

5
1 2 4 5 6
3

输出样例：

4
1 2 4 5 6

解析

ElemSet Find( List list, int m )
{
    Position p = list;
    Position q = list;
    int i = 0;
    for (i = 0; i < m; i++)
    {
        p = p->next;
        if (p == NULL)
        {
            return ERROR;
        }
    }
    int j = 0;
    for (; p != NULL; p = p->next)
    {
        q = q->next;
    }
    return q->data;
}

注意

  1. 双指针技巧：

    快指针（fast）和慢指针（slow）都从第一个数据节点开始

    快指针先移动m步

    然后两个指针以相同速度同时移动

  2. 数学原理：

    当快指针到达链表末尾（NULL）时，它比慢指针多走了m步

    这意味着慢指针正好指向倒数第m个节点

  3. 边界情况处理：

    如果m大于链表长度，快指针在移动m步之前就会遇到NULL

    此时直接返回ERROR