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

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

分数 15

作者 陈越

单位 浙江大学

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

输入格式：

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

输出格式：

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

1
表长: x1 x2 ... xn

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

输入样例：

1
2
5
1 2 3 4 5

输出样例：

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

答案

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
using namespace std;
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

// 初始化链表
void InitList(LinkList &L) {
    L = new LNode;
    L->next = NULL;
}

// 插入元素
void InsertAtTail(LinkList &p, int num) {
    LNode *newNode = new LNode;
    newNode->data = num;
    newNode->next = p->next;
    p->next = newNode;
}

// 插入元素到第x个位置
bool InsertELement(int x,int n) {
    if (x < 1 || x > n+1) {
        return false;
    }
}

// 打印链表
void printLinkList(LinkList L) {
    LNode *currentNode = L; // 定义一个指针，方便遍历
    while (currentNode->next != NULL) {
        currentNode = currentNode->next;
        cout << " " << currentNode->data;
    }
    cout << endl;
}

int main() {
    LNode *L; // 定义一个头指针，指向链表
    InitList(L); // 初始化链表，使头指针指向头节点
    int n, num;
    cin >> n; // 读取插入链表元素的个数
    LNode *p = L; // 定义一个尾指针，方便插入
    for (int i = 0; i < n; i++) {
        cin >> num; // 读取插入的元素
        InsertAtTail(p, num); // 尾插法插入num
        p = p->next; // 更新尾指针
    }
    cout << n << ":"; // 输出表长
    printLinkList(L);
    bool isInsert1 = InsertELement(0, n);
    if (!isInsert1) {
        cout << "错误：插入位置不合法。" <<endl;
    }
    bool isInsert2= InsertELement(n+2 ,n);
    if (!isInsert2) {
        cout << "错误：插入位置不合法。";
    }
}

Summary

  1. 代码采用尾插法构建链表：
    • 定义了**尾指针p**并初始化为头节点
    • 每次插入新节点后，通过p = p->next更新尾指针
    • 尾插法能保持插入元素的顺序与输入顺序一致
  2. 链表遍历输出的实现：
    • 定义了临时指针currentNode用于遍历
    • 从首元节点开始（跳过头节点）依次访问并输出元素
    • 避免了直接操作头指针导致的链表结构破坏