程序开发实训 【专题五】 单链表的增、删、查

包含题目

1、学生成绩（单链表-求表长）
2、学生成绩（单链表-按位查找）
3、学生成绩（单链表-按值查找位置）
4、学生成绩（单链表-插入）
5、学生成绩（单链表-删除）

注意

1.以下代码仅供参考，不代表最优解。如果您有更优的解，欢迎加群交流。
2.代码的运行结果与编译环境有关，以下代码均通平台测试，如果代码存在无法编译或输出异常，请检查运行环境。

1、学生成绩（单链表-求表长）

【问题描述】

从键盘依次输入某班学生的姓名和成绩（一个班级人数最多不超过 50 人）并保存。

【输入形式】

从键盘依次输入最多不超过 50 个学生的学生姓名和成绩和待查找学生的姓名； 第一行输入班级学生人数 n； 接下来的 n 行：在单独行上输入空格隔开的学生姓名和成绩，其中学生成绩是整数。

【输出形式】

单链表的表长。

【输入样例】

4
aaa 50
bbb 70
ccc 65
ddd 90

【输出样例】 4

#include <iostream>
using namespace std;
typedef struct node
{
    string name;
    int score;
    node *next;
} node;

node *create(node *head, string name[], int score[], int len);
int getLength(node *first);
int main()
{
    int n;
    cin >> n;
    string name[n];
    int score[n];
    node *first = NULL;
    for (int i = 0; i < n; i++)
        cin >> name[i] >> score[i];
    first = create(first, name, score, n);
    //show(first);
    cout << getLength(first) << endl;
    return 0;
}
node *create(node *first, string name[], int score[], int len)
{
    first = new node;
    first->next = NULL;
    node *rear = first;
    for (int i = 0; i < len; i++)
    {
        node *s = new node;
        s->name = name[i];
        s->score = score[i];
        s->next = NULL;
        rear->next = s;
        rear = s;
    }
    return first;
}

int getLength(node *first)
{
    int count = 0;
    node *curr = first;
    while (curr->next != NULL)
    {
        count++;
        curr = curr->next;
    }
    return count;
}

2、学生成绩（单链表-按位查找）

【问题描述】

从键盘依次输入某班学生的姓名和成绩（一个班级人数最多不超过 50 人）并保存，然后输入待查找学生的序号。如果该学生存在，程序输出该学生的姓名和成绩；如果不存在，程序输出 NO。

【输入形式】

从键盘依次输入最多不超过 50 个学生的学生姓名和成绩和待查找学生的姓名；

第一行输入班级学生人数 n；

接下来的 n 行：在单独行上输入空格隔开的学生姓名和成绩，其中学生成绩是整数。

最后一行输入待查找学生的序号。

【输出形式】

查找结果。如果该学生存在，程序输出该学生的姓名和成绩；如果不存在，程序输出 NO。

【输入样例】

4
aaa 50
bbb 70
ccc 65
ddd 90
2

【输出样例】

bbb 70

#include <iostream>
using namespace std;
typedef struct node
{
    string name;
    int score;
    node *next;
} node;

node *create(node *head, string name[], int score[], int len);
node *get(node *first, int num);
int main()
{
    int n;
    cin >> n;
    string name[n];
    int score[n];
    node *first = NULL;
    for (int i = 0; i < n; i++)
        cin >> name[i] >> score[i];
    first = create(first, name, score, n);
    int num;
    cin >> num;
    node *p = get(first, num);
    if (p == NULL)
        cout << "NO" << endl;
    else
        cout << p->name << "  " << p->score << endl;
    return 0;
}
node *create(node *first, string name[], int score[], int len)
{
    first = new node;
    first->next = NULL;
    node *rear = first;
    for (int i = 0; i < len; i++)
    {
        node *s = new node;
        s->name = name[i];
        s->score = score[i];
        s->next = NULL;
        rear->next = s;
        rear = s;
    }
    return first;
}

// 注意，此方法不严谨，仅供参考
node *get(node *first, int num)
{
    node *curr = first;
    while (num--)
        curr = curr->next;
    return curr;
}

3、学生成绩（单链表-按值查找位置）

【问题描述】

从键盘依次输入某班学生的姓名和成绩（一个班级人数最多不超过 50 人）并保存，然后输入待查找学生的名字。如果该学生存在，程序输出该学生在单链表中的位置；如果不存在，程序输出 NO。

【输入形式】

从键盘依次输入最多不超过 50 个学生的学生姓名和成绩和待查找学生的姓名；

第一行输入班级学生人数 n；

接下来的 n 行：在单独行上输入空格隔开的学生姓名和成绩，其中学生成绩是整数。

最后一行输入待查找学生的姓名。

【输出形式】

查找结果。如果该学生存在，程序输出该学生在单链表中的位置；如果不存在，程序输出 NO。

【输入样例】

4
aaa 50
bbb 70
ccc 65
ddd 90
aaa

【输出样例】

1

#include <iostream>
using namespace std;
typedef struct node
{
    string name;
    int score;
    node *next;
} node;

node *create(node *head, string name[], int score[], int len);
void show(node *first);
int getLocation(node *first, string name);
int main()
{
    int n;
    cin >> n;
    string name[n];
    int score[n];
    node *first = NULL;
    for (int i = 0; i < n; i++)
        cin >> name[i] >> score[i];
    first = create(first, name, score, n);
    //show(first);
    string stuName;
    cin >> stuName;
    int location = getLocation(first, stuName);
    if (location == 0)
        cout << "NO" << endl;
    else
        cout << location << endl;
    return 0;
}
node *create(node *first, string name[], int score[], int len)
{
    first = new node;
    first->next = NULL;
    node *rear = first;
    for (int i = 0; i < len; i++)
    {
        node *s = new node;
        s->name = name[i];
        s->score = score[i];
        s->next = NULL;
        rear->next = s;
        rear = s;
    }
    return first;
}

void show(node *first)
{
    node *p = first->next;
    while (p != NULL)
    {
        cout << p->name << "  " << p->score << endl;
        p = p->next;
    }
}

int getLocation(node *first, string name)
{
    int location = 0;
    node *curr = first;
    while (curr->next != NULL)
    {
        location++;
        curr = curr->next;
        if (curr->name == name)
            return location;
    }
    return 0;
}

4、学生成绩（单链表-插入）待优化

【问题描述】

从键盘依次输入某班学生的姓名和成绩（一个班级人数最多不超过 50 人）并保存，然后输入某个学生的待插入位置，以及该学生的姓名和成绩。如果可以插入，则输出插入该学生后的单链表；如果不能插入，则输出 NO。

【输入形式】

从键盘依次输入最多不超过 50 个学生的学生姓名和成绩和待插入学生的位置，以及姓名和成绩；

第一行输入班级学生人数 n；

接下来的 n 行：在单独行上输入空格隔开的学生姓名和成绩，其中学生成绩是整数。

最后一行输入待插入学生的位置，姓名和成绩。

【输出形式】

如果可以插入，则输出插入该学生后的单链表；如果不能插入，则输出 NO。

【输入样例】

4
aaa 50
bbb 70
ccc 65
ddd 90
2 eee 100

【输出样例】

aaa 50
eee 100
bbb 70
ccc 65
ddd 90

#include <iostream>
#include <stdio.h>
using namespace std;
typedef struct node
{
    string name;
    int score;
    node *next;
} node;

node *create(node *head, string name[], int score[], int len);
void show(node *first);
bool insertNode(node *first, int location, string name, int score);
int main()
{
    int n;
    cin >> n;
    string name[n];
    int score[n];
    node *first = NULL;
    for (int i = 0; i < n; i++)
        cin >> name[i] >> score[i];
    first = create(first, name, score, n);
    int location, stuScore;
    string stuName;
    cin >> location >> stuName >> stuScore;
    bool flag = insertNode(first, location, stuName, stuScore);
    if (flag == false)
        cout << "NO" << endl;
    else
        show(first);
    return 0;
}
node *create(node *first, string name[], int score[], int len)
{
    first = new node;
    first->next = NULL;
    node *rear = first;
    for (int i = 0; i < len; i++)
    {
        node *s = new node;
        s->name = name[i];
        s->score = score[i];
        s->next = NULL;
        rear->next = s;
        rear = s;
    }
    return first;
}

void show(node *first)
{
    node *p = first->next;
    while (p != NULL)
    {
        cout << p->name << "  " << p->score << endl;
        p = p->next;
    }
}

bool insertNode(node *first, int location, string name, int score)
{
int j = 1;
    node *curr = first;
    // 定位到指定位置
    while (curr && j < location)
    {
        curr = curr->next;
        j++;
    }

    // 判断是否可以插入
    if (!curr || j > location)
        return false;

    // 插入
    node *p = new node;
    p->name = name;
    p->score = score;
    p->next = curr->next;
    curr->next = p;

    return true;
}

5、学生成绩（单链表-删除）

【问题描述】

从键盘依次输入某班学生的姓名和成绩（一个班级人数最多不超过 50 人）并保存，然后输入某个学生的编号，删除该学生的下一个学生。如果可以删除，则输出删除后的单链表；如果不能插入，则输出 NO。

【输入形式】

从键盘依次输入最多不超过 50 个学生的学生姓名和成绩和待删除学生的位置，以及姓名和成绩；

第一行输入班级学生人数 n；

接下来的 n 行：在单独行上输入空格隔开的学生姓名和成绩，其中学生成绩是整数。

最后一行输入待删除学生的编号。

【输出形式】

如果可以删除，则输出删除后的单链表；如果不能插入，则输出 NO。

【输入样例】

4
aaa 50
bbb 70
ccc 65
ddd 90
2

【输出样例】

aaa 50
bbb 70
ddd 90

#include <iostream>
#include <stdio.h>
using namespace std;
typedef struct node
{
    string name;
    int score;
    node *next;
} node;

node *create(node *head, string name[], int score[], int len);
void show(node *first);
bool deleteNode(node *first, int location, string &name, int &score);
int main()
{
    int n;
    cin >> n;
    string name[n];
    int score[n];
    node *first = NULL;
    for (int i = 0; i < n; i++)
        cin >> name[i] >> score[i];
    first = create(first, name, score, n);
    int location, stuScore;
    string stuName;
    cin >> location;
    bool flag = deleteNode(first, location, stuName, stuScore);
    if (flag == false)
        cout << "NO" << endl;
    else
        show(first);
    return 0;
}
node *create(node *first, string name[], int score[], int len)
{
    first = new node;
    first->next = NULL;
    node *rear = first;
    for (int i = 0; i < len; i++)
    {
        node *s = new node;
        s->name = name[i];
        s->score = score[i];
        s->next = NULL;
        rear->next = s;
        rear = s;
    }
    return first;
}

void show(node *first)
{
    node *p = first->next;
    while (p != NULL)
    {
        cout << p->name << "  " << p->score << endl;
        p = p->next;
    }
}

bool deleteNode(node *first, int location, string &name, int &score)
{
    node *rear = first;
    // 定位到指定位置
    while (rear && location--)
        rear = rear->next;

    // 判断是否可以删除
    if (!rear || !rear->next)
        return false;

    // 删除
    node *curr = rear->next;
    rear->next = curr->next;
    delete (curr);
    return true;
}

评论交流

最后，如果你觉得笔记对你有帮助，不妨赞赏一杯可乐😅

QQ 交流群 217394861