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

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

分数 15

作者 陈越

单位 浙江大学

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

输入格式：

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

输出格式：

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

1
表长: x1 x2 ... xn

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

输入样例 1：

1
2
3
5
1 2 3 4 5
3

输出样例 1：

1
4: 5 4 2 1

输入样例 2：

1
2
3
5
4 3 6 8 0
0

输出样例 2：

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

答案

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#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 InsertAtHead(LinkList &L, int num) {
    LNode *newNode = new LNode;
    newNode->data = num;
    newNode->next = L->next;
    L->next = newNode;
}

// 获取链表长度
int getLength(LinkList L) {
    int length = 0;
    LNode *p = L;
    while(p->next != NULL) {
        p = p->next;
        length++;
    }
    return length;
}

// 删除位序为i的元素
bool deleteElement(LinkList &L, int i) {
    // 检查删除位置是否合法
    int length = getLength(L);
    if (i < 1 || i > length) {
        return false;
    }
    //找到第i-1个位置
    LNode *p = L;
    for (int j = 0; j < i - 1; j++) {
        p = p->next;
    }
    // 定义q指向第i个结点
    LNode *q = p->next;
    p->next = q->next;
    delete q;
    return true;
}

// 打印链表
void printLinkList(LinkList L) {
    LNode *p = L;
    while(p->next != NULL) {
        p = p->next;
        cout << " " << p->data;
    }
}

int main() {
    LNode *L; // 定义一个头指针，用来指向链表
    InitList(L); // 初始化一个带头结的链表
    int n, num, i;
    cin >> n; // 读取输入元素的个数n
    for (int j = 0; j < n; j++) {
        cin >> num; // 读取输入的元素
        InsertAtHead(L, num); // 将num插入到链表头部
    }
    cin >> i; // 读取插入的位序
    if (!deleteElement(L, i)) {
        cout << "错误：删除位置不合法。" << endl;
    }
    cout << getLength(L) << ":";
    printLinkList(L); // 打印链表
}

Summary

1.L

  • L是头指针，里面存的是头结点的地址，指向头结点
  • L->next里面存的是第一个结点的地址，指向第一个结点

2.

1
2
3
4
5
6
7
8
9
10
// 获取链表长度
int getLength(LinkList L) {
    int length = 0;
    LNode *p = L;
    while(p->next != NULL) {
        p = p->next;
        length++;
    }
    return length;
}
  • 注意是while(p->next != NULL) 而不是while(L->next != NULL)