PTA 算法2-5 返回单链表 list 中第 i 个元素值

算法2-5 返回单链表 list 中第 i 个元素值

分数 15

作者 陈越

单位 浙江大学

请编写程序，将 n 个整数顺次插入一个初始为空的单链表的表头。对任一给定的位序 i（从 1 开始），输出链表中第 i 个元素的值。

输入格式：

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

输出格式：

在一行中输出链表中第 i 个元素的值。如果这个元素不存在，则输出 -1。

输入样例 1：

1
2
3
5
1 2 3 4 5
4

输出样例 1：

1
2

输入样例 2：

1
2
3
5
1 2 3 4 5
0

输出样例 2：

1
-1

答案

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
#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 InsertList(LinkList &L, int num) {
    LNode *newNode = new LNode;
    newNode->data = num;
    newNode->next = L->next;
    L->next = newNode;
}

// 获取指定位序的元素
int getElement(LinkList &L, int i) {
    if (i < 1) {
        return -1;
    }
    LNode *p = L;
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    if (p != NULL && j == i) {
        return p->data;
    } else {
        return -1;
    }
}

int main() {
    LNode *L; // 定义一个头指针
    InitList(L); // 初始化一个带头结点的链表
    int n, num, i;
    cin >> n; // 读取输入整数的个数
    for (int j = 0; j < n; ++j) {
        cin >> num; // 读取输入的数字
        InsertList(L, num); // 将读取到的数据插入到链表头部
    }
    cin >> i; // 读取需要返回元素的位次
    cout << getElement(L,i); // 输出内容
}

Summary

在链表的实现中，LinkList 和 LNode 通常是这样定义的：

1
2
3
4
5
6
typedef struct LNode {
    // 数据域
    int data;
    // 指针域，指向 next 节点
    struct LNode *next;
} LNode, *LinkList;

从这个定义可以看出：

  • LNode 是结构体类型，表示链表中的节点本身（如果写成LNode &L

    ，只能修改结点本身，不能改变指向）

  • LinkList 是 struct LNode* 的别名，表示指向节点的指针

所以在 InitList(LinkList &L) 中：

  • 参数类型是 LinkList &L，也就是 LNode* &L，表示指向指针的引用
  • 这样在函数内部修改 L 时（比如分配头节点），才能影响到主函数中实参的指向

而如果写成 LNode &L 则表示指向节点的引用，这不符合链表初始化的需求，因为初始化需要修改的是指针的指向（让它指向新创建的头节点），而不是修改某个节点的内容。

2.实参L传递的是什么

  • 实参是 L，传递的是头指针的值（即头节点的地址）