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

算法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>
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;
}

// 查找元素
bool findElement(LinkList &L, int x) {
    LNode *p = L->next;
    while (p != NULL && p->data != x) {
        p = p->next;
    }
    if (p != NULL && p->data == x) {
        return true;
    } else {
        return false;
    }
}
int main() {
    LNode *L; // 定义一个头指针
    InitList(L); // 初始化链表，让头指针指向头结点
    int n, x, num;
    cin >> n; // 读取待输入的整数的个数
    for (int i = 0; i < n; i++) {
        cin >> num; // 读取要插入的数据
        InsertAtHead(L, num);
    }
    cin >> x; // 读取待查找的数据x
    if(findElement(L, x)) {
        cout << x;
    } else {
        cout << x << " 未找到。";
    }
}

Summary

为什么是p != NULL && p->data == x，而不是p->data == x && p != NULL

// 查找元素
bool findElement(LinkList &L, int x) {
    LNode *p = L->next;
    while (p != NULL && p->data != x) {
        p = p->next;
    }
    if (p != NULL && p->data == x) {
        return true;
    } else {
        return false;
    }
}

• findElement函数的最后判断部分，当链表中没有找到目标元素时，p会变成NULL，此时访问p->data仍然会导致空指针错误
• 确保了只有当p不是空指针时，才会去访问p->data，彻底解决了空指针访问的问题。当遍历完整个链表都没有找到目标元素时，p会变成NULL，这时函数会正确返回false