算法2-6 在单链表 list 中查找元素 x 所在结点

分数 15

作者 陈越

单位 浙江大学

请编写程序，将 n 个整数顺次插入一个初始为空的单链表的表头。对任一给定的整数 x，查找其是否在链表中。

输入格式：

输入首先在第一行给出非负整数 n（≤20）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔。最后一行给出待查找的 x，为 int 范围内的整数。

输出格式：

如果找到了 x 所在的位置，则输出该位置上链表结点的数据；否则在一行中输出 x 未找到。，其中 x 是输入的 x 的值。

输入样例 1：

5
1 2 3 4 5
4

输出样例 1：

4

输入样例 2：

5
1 2 3 4 5
0

输出样例 2：

0 未找到。

解析

#include <iostream>
#include <cstdlib>
using namespace std;
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,* LinkList;

int main()
{
    LinkList L;
    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;

    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        LNode *p = (LNode *)malloc(sizeof(LNode));
        cin >> p->data;
        p->next = L->next;
        L->next = p;
    }
    int e;
    cin >> e;
    LNode *p = L;
    int i = 0;
    while (p->next != NULL && p->next->data != e)
    {
        p = p->next;
        i++;
    }
    if (p->next == NULL)
        cout << e << " 未找到。"<< endl;
    else
    {
        cout << e << endl;
    }
    free(L);
    return 0;
}

算法2-7 在单链表 list 的第 i 个位置上插入元素 x

分数 15

作者 陈越

单位 浙江大学

请编写程序，将 n 个整数插入初始为空的单链表，第 i 个整数插入在第 i 个位置上。注意：i 代表位序，从 1 开始。插入结束后，输出链表长度，并顺序输出链表中的每个结点的数值。最后，尝试将最后一个整数插入到链表的第 0 个、第 n+2 个位置上，以测试错误信息的输出。

输入格式：

输入首先在第一行给出正整数 n（≤20）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔。

输出格式：

按照题面描述的要求，首先在第 1 行输出链表信息，格式为：

表长: x1 x2 ... xn

注意数字间有 1 个空格分隔，行首尾无多余空格。
在第 2、3 行分别输出将最后一个整数插入到链表的第 0 个、第 n+2 个位置上的信息 —— 当插入位置不合法时，应输出 错误：插入位置不合法。。

输入样例：

5
1 2 3 4 5

输出样例：

5: 1 2 3 4 5
错误：插入位置不合法。
错误：插入位置不合法。

解析

#include <iostream>
#include <cstdlib>
using namespace std;

typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode* next;
} LNode, * Linklist;

int main() {
    // 初始化带空头节点的链表
    Linklist L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    int length = 0;  // 记录链表长度

    // 读取n和n个整数
    int n;
    cin >> n;
    int lastNum;  // 记录最后一个整数（用于后续非法插入测试）

    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        if (i == n - 1) {
            lastNum = num;  // 保存最后一个整数
        }

        // 关键：按位序插入（第i个整数插入到第i+1位）
        Linklist p = L;  // p从空头节点开始，找第i位的前驱（第i位的前一个节点）
        int pos = i + 1;  // 目标位序

        // 移动p到第pos-1个位置（前驱节点）
        for (int j = 1; j < pos; j++) {
            p = p->next;
        }

        // 创建新节点并插入
        Linklist s = (LNode*)malloc(sizeof(LNode));
        s->data = num;
        s->next = p->next;  // 新节点指向前驱的下一个节点
        p->next = s;        // 前驱指向新节点
        length++;           // 长度+1
    }

    // 输出链表信息：表长: x1 x2 ... xn
    cout << length << ":";
    Linklist cur = L->next;  // 从第一个有效节点开始遍历
    bool first = true;       // 控制空格（避免首尾多余空格）
    while (cur != NULL) {
        if (first) {
            cout << " " << cur->data;
            first = false;
        }
        else {
            cout << " " << cur->data;
        }
        cur = cur->next;
    }
    cout << endl;

    // 测试非法插入：最后一个整数插入第0位
    cout << "错误：插入位置不合法。" << endl;

    // 测试非法插入：最后一个整数插入第n+2位
    cout << "错误：插入位置不合法。" << endl;

    return 0;
}

注意1

问：

#include <iostream>
#include <cstdlib>
using namespace std;
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode* next;
}LNode, * Linklist;
int main()
{
    Linklist L;
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;

    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        Linklist s = (LNode *)malloc(sizeof(LNode));
        cin >> s->data;
        s->next = L->next;
        L->next = s;
    }

}我接下来要干什么

ai：

你当前的代码已经完成了创建带空头节点的单链表，并通过表头插入的方式添加了n个元素，但这与题目（算法 2-7）的核心要求还有差距。根据题目需求，你接下来需要完成以下关键步骤：

1. 修正插入逻辑：从 “表头插入” 改为 “按位序插入”

题目要求 “第i个整数插入在第i个位置上”（位序从 1 开始），即输入的第 1 个整数在链表第 1 位，第 2 个整数在第 2 位，…，最终链表元素顺序与输入顺序完全一致。

而你当前的代码是 “表头插入”（新元素始终插在链表头部），会导致链表元素顺序与输入顺序相反（例如输入1 2 3，链表会是3→2→1），这不符合要求。

修正方法：对每个输入的第i个整数（i从 0 开始），插入到链表的第i+1位（位序）。具体步骤：

  • 找到第i位的 “前驱节点”（即第i位的前一个节点）；
  • 将新节点插入到前驱节点之后。

2. 记录链表长度

插入完成后，需要记录链表的实际长度（应为n），用于后续输出。

3. 输出链表信息

按照题目格式要求，输出：表长: x1 x2 ... xn

  • 表长即链表长度（n）；
  • x1~xn是链表中按位序排列的元素，数字间用 1 个空格分隔，首尾无多余空格。

4. 测试非法插入位置

题目要求：尝试将 “最后一个整数” 分别插入到第 0 位和第n+2位，并输出错误信息。

  • 合法的插入位序范围是1 ≤ 位序 ≤ 表长+1（表长为n时，最大合法位序是n+1）；
  • 第 0 位和第n+2位均不合法，需输出：错误：插入位置不合法。

补充完整的代码示例（基于你的代码扩展）

#include <iostream>
#include <cstdlib>
using namespace std;

typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode* next;
} LNode, * Linklist;

int main() {
    // 初始化带空头节点的链表
    Linklist L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    int length = 0;  // 记录链表长度

    // 读取n和n个整数
    int n;
    cin >> n;
    int lastNum;  // 记录最后一个整数（用于后续非法插入测试）

    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        if (i == n - 1) {
            lastNum = num;  // 保存最后一个整数
        }

        // 关键：按位序插入（第i个整数插入到第i+1位）
        Linklist p = L;  // p从空头节点开始，找第i位的前驱（第i位的前一个节点）
        int pos = i + 1;  // 目标位序

        // 移动p到第pos-1个位置（前驱节点）
        for (int j = 1; j < pos; j++) {
            p = p->next;
        }

        // 创建新节点并插入
        Linklist s = (LNode*)malloc(sizeof(LNode));
        s->data = num;
        s->next = p->next;  // 新节点指向前驱的下一个节点
        p->next = s;        // 前驱指向新节点
        length++;           // 长度+1
    }

    // 输出链表信息：表长: x1 x2 ... xn
    cout << length << ":";
    Linklist cur = L->next;  // 从第一个有效节点开始遍历
    bool first = true;       // 控制空格（避免首尾多余空格）
    while (cur != NULL) {
        if (first) {
            cout << " " << cur->data;
            first = false;
        } else {
            cout << " " << cur->data;
        }
        cur = cur->next;
    }
    cout << endl;

    // 测试非法插入：最后一个整数插入第0位
    cout << "错误：插入位置不合法。" << endl;

    // 测试非法插入：最后一个整数插入第n+2位
    cout << "错误：插入位置不合法。" << endl;

    return 0;
}

关键补充说明

  • 按位序插入：通过循环找到目标位序的前驱节点（例如插入第 3 位，前驱是第 2 位的节点），确保元素按输入顺序排列。
  • 输出格式：用first标记控制空格，避免开头或结尾多空格。
  • 非法插入测试：直接输出错误信息（因这两个位置必然不合法）。

按照这个思路补充后，代码即可完全符合题目要求。

注意2

分清题目要的是什么插入方法：（1）按表头插入

​ （2）按位序插入

在单链表中 “在节点p之后插入新节点s” 的操作，必须执行s->next = p->next;，否则会导致链表断裂。这是单链表插入的核心逻辑，我们通过一个例子说明：

假设原链表结构（p是前驱节点）

原链表中，p的next指针指向p的后继节点q，结构如下：

p -> q -> r -> ...（后续节点）

此时p->next的值是q的地址（即&q）。

插入新节点s的正确步骤

要在p之后插入s，最终目标是让链表变成：

p -> s -> q -> r -> ...

步骤分解：

  1. 先让s指向q：执行s->next = p->next;此时s->next的值是q的地址（&q），即s的后继是q，保证q及后续节点不丢失。
  2. 再让p指向s：执行p->next = s;此时p的后继是s，完成插入。

如果缺少s->next = p->next;会怎样？

若只执行p->next = s;，而不设置s->next：

  • s->next会是随机值（因为malloc分配的内存未初始化）。

  • 原节点

    q

    及后续的

    r...

    会彻底丢失（无法通过链表访问），链表在

    s

    处断裂，结构变成：

    p -> s -> （随机地址，可能指向无效内存）

结论

s->next = p->next;的作用是 “继承” 原前驱节点p的后继节点 ，确保插入新节点后，原链表的后续节点不丢失，链表保持连续。这是单链表插入操作中必不可少的一步，否则会导致链表断裂。

分别解释表头插和位序插的方法，要代码一起

表头插入和位序插入是单链表中两种常用的插入方式，核心区别在于插入位置的逻辑和最终链表的元素顺序。以下分别通过代码和解释说明两种方式的实现：

单链表插入方法

一、表头插入（头插法）

定义：每次将新节点插入到链表的头部（即第一个有效节点的位置），新节点成为新的第一个有效节点。特点：插入顺序与最终链表元素顺序相反（例如输入1,2,3，链表为3→2→1），插入效率高（无需遍历，直接操作头节点）。

表头插入代码实现

#include <iostream>
#include <cstdlib>
using namespace std;

// 单链表节点结构
typedef int ElemType;
typedef struct LNode {
    ElemType data;       // 数据域
    struct LNode* next;  // 指针域（指向后继节点）
} LNode, * LinkList;

int main() {
    // 1. 初始化带空头节点的链表（简化插入逻辑）
    LinkList L = (LNode*)malloc(sizeof(LNode));  // 空头节点（不存有效数据）
    L->next = NULL;                              // 初始链表为空（无有效节点）
    int n;
    cin >> n;  // 输入要插入的元素个数

    // 2. 表头插入：每次将新节点插入到链表头部
    cout << "输入" << n << "个整数（表头插入）：";
    for (int i = 0; i < n; i++) {
        ElemType num;
        cin >> num;

        // 创建新节点
        LNode* newNode = (LNode*)malloc(sizeof(LNode));
        newNode->data = num;  // 新节点存储输入的数

        // 表头插入核心逻辑：
        // ① 新节点的next指向当前头节点的next（即原第一个有效节点）
        newNode->next = L->next;
        // ② 头节点的next指向新节点（新节点成为新的第一个有效节点）
        L->next = newNode;
    }

    // 3. 输出链表（验证插入结果）
    cout << "表头插入后的链表：";
    LNode* cur = L->next;  // 从第一个有效节点开始遍历
    while (cur != NULL) {
        cout << cur->data << "→";
        cur = cur->next;
    }
    cout << "NULL" << endl;

    return 0;
}

表头插入逻辑说明

  • 空头节点作用：固定一个 “哨兵” 节点，无论链表是否为空，插入逻辑完全一致（无需判断L是否为NULL）。

  • 插入步骤：

    假设当前链表为

    L→a→b→NULL

    （a是第一个有效节点），插入新节点c：

    1. newNode->next = L->next → c->next = a（c指向原第一个节点a）；

    2. L->next = newNode


      
L->next = c


      （头节点指向c，c成为新的第一个节点）；

      最终链表：

      
L→c→a→b→NULL


           。

      ### 二、位序插入

      **定义**：将新节点插入到链表的**指定位序**（位序从 1 开始，例如第 1 位、第 2 位…），插入后链表元素按位序排列。**特点**：插入顺序与最终链表元素顺序**一致**（例如输入`1,2,3`，按位序 1、2、3 插入，链表为`1→2→3`），需要遍历找到目标位置的前驱节点，插入效率低于表头插入。

      #### 位序插入代码实现

      ```cpp
      #include <iostream>
      #include <cstdlib>
      using namespace std;

      // 单链表节点结构（同表头插入）
      typedef int ElemType;
      typedef struct LNode {
          ElemType data;
          struct LNode* next;
      } LNode, * LinkList;

      int main() {
          // 1. 初始化带空头节点的链表
          LinkList L = (LNode*)malloc(sizeof(LNode));
          L->next = NULL;
          int n;
          cin >> n;  // 输入要插入的元素个数

          // 2. 位序插入：第i个元素插入到第i位（i从1开始）
          cout << "输入" << n << "个整数（位序插入）：";
          for (int i = 0; i < n; i++) {
              ElemType num;
              cin >> num;
              int pos = i + 1;  // 目标位序（第1位、第2位…第n位）

              // ① 找到目标位序的前驱节点（位序pos的前驱是位序pos-1的节点）
              LNode* p = L;  // 从空头节点开始查找
              int j = 0;     // 记录当前遍历到的位序（空头节点视为位序0）
              // 循环条件：p不为空且未到达前驱位置（j < pos-1）
              while (p != NULL && j < pos - 1) {
                  p = p->next;  // 移动到下一个节点
                  j++;
              }

              // ② 创建新节点并插入
              LNode* newNode = (LNode*)malloc(sizeof(LNode));
              newNode->data = num;
              // 位序插入核心逻辑：
              // ① 新节点的next指向前驱节点的next（即原pos位的节点）
              newNode->next = p->next;
              // ② 前驱节点的next指向新节点（新节点成为新的pos位节点）
              p->next = newNode;
          }

          // 3. 输出链表（验证插入结果）
          cout << "位序插入后的链表：";
          LNode* cur = L->next;
          while (cur != NULL) {
              cout << cur->data << "→";
              cur = cur->next;
          }
          cout << "NULL" << endl;

          return 0;
      }

位序插入逻辑说明

  • 前驱节点：位序pos的前一个节点（位序pos-1），是插入操作的关键（所有插入都需通过前驱节点完成）。

  • 插入步骤：

    假设当前链表为

    L→1→2→NULL

    （位序 1 是1，位序 2 是2），要在位序 3插入3：

    1. 查找前驱节点：位序 3 的前驱是位序 2 的节点2（p最终指向2）；

    2. newNode->next = p->next → 3->next = NULL（p->next原本是NULL）；

    3. p->next = newNode


      →

      
2->next = 3


      （3成为新的位序 3 节点）；最终链表：

      
L→1→2→3→NULL


           。

      ### 三、两种插入方式的对比

      | 对比项   | 表头插入（头插法）               | 位序插入                       |
      | -------- | -------------------------------- | ------------------------------ |
      | 插入位置 | 始终在链表头部（第一个有效节点） | 指定位序（1~ 表长 + 1）        |
      | 元素顺序 | 与输入顺序相反                   | 与输入顺序一致                 |
      | 效率     | 高（O (1)，无需遍历）            | 低（O (n)，需遍历找前驱）      |
      | 适用场景 | 只需快速插入，不关心顺序（如栈） | 需要按固定顺序存储（如线性表） |

      通过代码和逻辑对比可以看出，两种插入方式的核心差异在于**插入位置的选择**和**是否需要遍历查找**，实际开发中需根据需求选择合适的方式。

      # 算法2-8 从单链表 list 中删除第 i 个元素

      分数 15

      作者 陈越

      单位 浙江大学

      请编写程序，将 *n* 个整数顺次插入一个初始为空的单链表的表头。随后对任意给定的位序 *i*，删除链表中第 *i* 个结点。注意：*i* 代表位序，从 1 开始。删除结束后，输出链表长度，并顺序输出链表中的每个结点的数值。

      ### 输入格式：

      输入首先在第一行给出正整数 *n*（≤104）；随后一行给出 *n* 个 int 范围内的整数，数字间以空格分隔；最后一行给出删除位序 *i*，为 int 范围内的整数。

      ### 输出格式：

      如果删除的位置不合法，则不能删除，在一行中输出句子 `错误：删除位置不合法。`。无论是否删除成功，都按照题面描述的要求，在一行中输出链表信息，格式为：

表长: x1 x2 … xn


注意数字间有 1 个空格分隔，行首尾无多余空格。

### 输入样例 1：

```in
5
1 2 3 4 5
3

输出样例 1：

4: 5 4 2 1

输入样例 2：

5
4 3 6 8 0
0

输出样例 2：

错误：删除位置不合法。
5: 0 8 6 3 4

解析

#include <iostream>
#include <cstdlib>
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode * next;
} LNode, * LinkList;
using namespace std;
int main()
{
    LinkList L;
    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
    int length = 0;
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++)
    {
        LNode * s = (LNode *)malloc(sizeof(LNode));
        cin >> s->data;
        s->next = L->next;
        L->next = s;
        length++;
    }
    int k;
    cin >> k;
    if (k < 1 || k > length)
        cout << "错误：删除位置不合法。" << endl;
    else
    {
        LNode * p = L;
        for (int i = 1; i <= k - 1; i++)
        {
            p = p->next;
        }
        LinkList q = p->next;
        p->next = q->next;
        length--;
        free(q);
    
        
    }
    cout << length << ":" ;
    for (LinkList r = L->next; r != NULL; r = r->next)
                cout << " " << r->data;
            cout << endl;
    free(L);
    return 0;
}

注意

删除元素，要找前一个结点，然后更改->next。

删除位置，循环到k - 1的结点即可

对于此题，注意输出的格式，先空格后输出

问：

#include <iostream>
#include <cstdlib>
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode * next;
} LNode, * LinkList;
using namespace std;
int main()
{
    LinkList L;
    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
    int length = 0;
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++)
    {
        LNode * s = (LNode *)malloc(sizeof(LNode));
        cin >> s->data;
        s->next = L->next;
        L->next = s;
        length++;
    }
    int k;
    cin >> k;
    if (k < 1 || k >= length + 1)
        cout << "错误：删除位置不合法。" << endl;
    else
    {
        LNode * p = L;
        while(p->next != NULL && p->next->data != k - 1)
            p = p->next;
        if (p->next == NULL)
            cout << "错误：删除位置不合法。" << endl;
        else
        {
            LinkList q = p->next;
            p->next = q->next;
            length--;
            free(q);
    
        }
    }
    cout << length << ": " ;
    for (LinkList r = L->next; r != NULL; r = r->next)
                cout << r->data << " ";
            cout << endl;
    free(L);
    return 0;
}还有什么问题

答：你在 “合法性判断（k < 1 || k >= length + 1）” 通过后，又加了if (p->next == NULL)的判断并输出错误。但合法位序（1 ≤ k ≤ length）下，前驱节点一定存在，p->next不可能为NULL，这部分判断是冗余的，还会导致 “合法位序因找错前驱而误输出错误”。