第 30 课：结构体及排序
在我们平时的生活中，一些数据往往包含不同的数据类型，而不仅仅是单一的整型、浮点型、字符型等。最近蛙蛙就听班主任说学校要做一个教务管理系统，他想利用自己所学的知识帮助学校搭建这个系统，但在编写程序的过程中，他遇到了一些问题。
比如对于每个学生，蛙蛙需要根据学校的需求统计他们的姓名（string）、性别（char）、年龄（int）、学号（string）、成绩（int）等信息。
由于数据种类很多，很容易产生混乱。为了解决这个问题，氪町博士给蛙蛙讲解了结构体的知识点，告诉蛙蛙结构体是 C++ 给出的可以让用户自定义的数据类型。通过结构体，我们可以构造自己需要的数据类型。
30.1 定义及操作
结构体定义
struct 结构体名 {
成员列表; // 成员可以是各种数据类型、结构体类型
成员函数; // 与结构体相关的函数
}; // 结尾的分号不能丢在定义结构体时，系统不给它分配实际内存，只有在定义结构体变量时，系统才为其分配内存。
对于前面所述的问题，我们可以构造一个"学生类型"，每个学生类型都有姓名、性别、年龄等多个元素（成员变量）。
struct Stu { // 定义学生结构体类型 Stu
string name; // 姓名
char sex; // 性别
int age; // 年龄
};
Stu stu, stus[100]; // 定义 Stu 类型变量 stu 和数组 stus结构体变量的调用
使用结构体变量的成员格式：结构体变量名.成员名
例如，对于上面定义的结构体变量，我们可以这样操作：
cin >> stu.name;
stu.sex = 'f';
stu.age = 25;
cout << stu.name << " " << stu.sex << " " << stu.age << endl;30.2 实例讲解
例 1：成绩统计
统计两位同学的姓名、年龄以及语文、数学、英语三门科目的成绩，计算每位同学的总分。
若两位同学总分存在差异，则输出总分较高的同学的姓名；若总分相同，则将两位同学的姓名一同输出，姓名以单个空格分隔。
【输入格式】输入两行，每行是一位同学的姓名（为简单起见，假设本例中只输入同学的名字）、年龄、语文成绩、数学成绩、英语成绩。
【输出格式】输出一行，如果总分不同，则输出总分较高的同学的姓名，如果总分相同，则分别输出两位同学的姓名，用单个空格隔开。
【输入样例】
Bob 9 45 89 30
Alice 10 73 83 72【输出样例】Alice
【数据范围】姓名为长度不超过 20 的字符串，且不包含空格；年龄为正整数，范围是 1 到 100；语文、数学、英语成绩均为 0 到 100 的整数。
解析
- 先构造一个结构体类型，包括学生的姓名（string）、年龄（int），以及语文、数学、英语成绩（int），代码如下：
struct STU
{
string name;
int age, chn, math, eng;
};- 声明两个整型变量，分别用来保存两位同学的总分，代码如下：
int suma, sumb;
cin >> a.name >> a.age >> a.chn >> a.math >> a.eng;
cin >> b.name >> b.age >> b.chn >> b.math >> b.eng;
suma = a.chn + a.math + a.eng;
sumb = b.chn + b.math + b.eng;- 比较两位同学的总成绩，输出总成绩分数较高的那位同学的姓名，代码如下：
if (suma > sumb)
cout << a.name;
else if (suma < sumb)
cout << b.name;
else
cout << a.name << " " << b.name;参考代码
#include <iostream>
using namespace std;
struct STU
{
string name;
int age, chn, math, eng;
};
int main()
{
STU a, b;
int suma, sumb;
cin >> a.name >> a.age >> a.chn >> a.math >> a.eng;
cin >> b.name >> b.age >> b.chn >> b.math >> b.eng;
suma = a.chn + a.math + a.eng;
sumb = b.chn + b.math + b.eng;
if (suma > sumb)
cout << a.name;
else if (suma < sumb)
cout << b.name;
else
cout << a.name << " " << b.name;
return 0;
}例 2：涨薪
蛙蛙父亲所在的公司拥有 n 名员工，为激励员工更高效地为公司贡献力量，公司老板决定为每位员工上调工资。
此次工资涨幅与员工在公司的工作年限紧密相关，员工每在公司工作满一年，月薪将相应增加 500 元。现已知每位员工的姓名、当前月薪以及在公司的工作年限，请计算出每位员工涨薪后的月薪是多少。
【输入格式】输入 n + 1 行。
第 1 行为该公司的员工数 n（n ≤ 100）；之后的 n 行分别为该公司每位员工的姓名、当前月薪以及在该公司的工作年限，中间用单个空格隔开。
【输出格式】输出 n 行，每一行分别为该公司每位员工的姓名以及对应员工涨完工资之后的月薪，中间用单个空格隔开。
【输入样例】
5
Zhangsan 12000 5
Lisi 10000 4
Wangwu 15000 10
Zhaoliu 8000 2
Tianqi 5432 2【输出样例】
Zhangsan 14500
Lisi 12000
Wangwu 20000
Zhaoliu 9000
Tianqi 6432解析
本题要求先读取员工数量，接着读取每位员工的姓名、当前月薪以及工作年限，算出每位员工涨薪后的月薪，最后输出每位员工的姓名和涨薪后的月薪。
结构体定义：可以定义一个名为 sal 的结构体，用来存储员工的相关信息。
a. string 类型的 name 用于存储员工的姓名。
b. int 类型的 salary 用于存储员工的当前月薪。
c. int 类型的 year 用于存储员工在公司的工作年限。
读取员工信息并计算涨薪后的月薪：先定义一个 sal 类型的数组 s 用于存储员工的信息，然后通过 for 循环遍历所有员工，再根据工作年限计算涨薪额度并将其加到当前月薪上，代码如下：
for (int i = 0; i < n; i++)
{
cin >> s[i].name >> s[i].salary >> s[i].year;
s[i].salary += 500 * s[i].year;
}参考代码
#include <iostream>
using namespace std;
struct sal
{
string name;
int salary, year;
} s[101];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s[i].name >> s[i].salary >> s[i].year;
s[i].salary += 500 * s[i].year;
}
for (int i = 0; i < n; i++)
cout << s[i].name << " " << s[i].salary << endl;
return 0;
}30.3 结构体成员函数
除了成员变量外，我们还可以在结构体内定义一些函数来作为结构体的成员函数。结构体中的变量可以作为成员函数的引用参数，而不需要另外定义形参。
例如我们可以在记录学生数学、语文、英语成绩的结构体 Grade 中加入一个表示总分的函数 sum，代码如下：
struct Grade
{
int math;
int chinese;
int english;
int sum()
{
return math + chinese + english;
}
} a, b, c;结构体成员函数的调用
调用结构体成员函数的一般形式为：结构体变量名.成员函数()
例如需要调用刚才 Grade 中的 sum 函数来求总分的时候，我们可以这样使用：
cout << a.sum(); // 输出 a 的总分例 3：竞赛优秀生认定
蛙蛙所在的学校有一个竞赛班，班级里共有 n 个学生，为了激发学生的学习热情和竞争意识，学校精心组织了一系列竞赛活动，该班级的全体学生都需要参与四轮紧张激烈的竞赛。
每一轮竞赛的满分设定为 100 分，其难度不容小觑，对学生的知识储备、应变能力以及心理素质都提出了很高的要求。经过综合考量，学校制定了严格的优秀生选拔标准：只有四轮竞赛总分累计能达到 200 分的学生，才有资格被认定为优秀生。
现在，学校需要蛙蛙帮忙编写程序，对学生的竞赛成绩进行处理。程序要能够依次输出符合优秀生标准的学生信息，这些信息包括学生的学号以及每一轮竞赛的具体成绩等。在完成所有优秀生信息的输出后，最后一行要明确输出在该班级中成功挑选出的优秀生的人数，以便直观地了解班级优秀学生的整体情况。
【输入格式】输入 n + 1 行。
第 1 行输入一个正整数 n，n ≤ 200。
接下来 n 行中，每行输入 5 个数，第 1 个数为该班级当前学生的学号，后面的 4 个数为四轮竞赛的得分，其中学生学号不超过 8 个数字，每轮竞赛得分不超过 100。
【输出格式】先输出所有选出的优秀生的信息，包括学号和四轮竞赛的得分，最后一行输出在该班级被认定为优秀生的人数。
【输入样例】
4
1947 54 57 60 41
2848 43 43 49 46
4687 52 50 45 43
4955 59 56 48 50【输出样例】
1947 2848 4687
3注：原文此处样例表格在文档转换中存在错位，以上为按原文数据重排的结果，可能与教材原书略有出入。
解析
- 结构体定义：定义一个名为 STU 的结构体，用于存储学生的信息，其中包含：int 类型的学生学号 num 以及学生四轮竞赛得分 a、b、c、d 这五个成员变量；int 类型的 sum 成员函数，用于计算学生四轮竞赛的总分，它将四轮得分相加并返回结果。紧接着声明 STU 类型的 stu 一维数组用于存储学生信息，代码如下：
struct STU
{
int num, a, b, c, d;
int sum()
{
return a + b + c + d;
}
} stu[205];读取学生信息并筛选优秀生
a. 使用 for 循环遍历每个学生。循环变量 i 从 0 开始，到 n - 1 结束，确保处理完所有学生的信息。
b. 读入第 i 个学生的学号以及四轮竞赛的得分，并存储到结构体数组 stu 的对应元素中。
c. 调用结构体 STU 的成员函数 sum 计算第 i 个学生的四轮竞赛总分，并判断是否大于或等于 200 分。如果满足条件，说明该学生是优秀生，输出其学号及四轮竞赛得分，并将优秀生的数量加 1。
参考代码
#include <iostream>
using namespace std;
struct STU
{
int num, a, b, c, d;
int sum()
{
return a + b + c + d;
}
} stu[205];
int main()
{
int n, t = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> stu[i].num >> stu[i].a >> stu[i].b >> stu[i].c >> stu[i].d;
if (stu[i].sum() >= 200) // 判断该生总分是否不小于 200
{
cout << stu[i].num << " " << stu[i].a << " " << stu[i].b << " ";
cout << stu[i].c << " " << stu[i].d << endl;
t++;
}
}
cout << t;
return 0;
}30.4 结构体排序
sort 函数
在之前课程的学习中，我们学习了选择、冒泡、插入、计数等排序的知识，今天氪町博士给大家介绍一种排序函数 sort，我们可以直接调用 sort 函数来实现排序。下面我们来看看 sort 的具体使用方法。
形式：sort(first_pointer, first_pointer + n, cmp)
- 第一个参数：数组的首地址，通常是数组名。
- 第二个参数：首地址 + 数组的长度 n。
- 第三个参数：排序规则函数的名称（自定义函数 cmp），若无此参数，sort 会默认按数组升序排序（从小到大）。
注意，使用 sort 需要加 algorithm 头文件，即：#include <algorithm>。
比如对一组数进行从小到大排序，使用 sort 函数可以这样写：
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int arr[] = {5, 2, 8, 1, 9};
sort(arr, arr + 5);
for (int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
return 0;
}运行结果：1 2 5 8 9
但在平时的生活中，我们常常要对一些数据按照不同的规则进行排序，例如：对学生的总分进行排序，总分相同再按照数学成绩进行排序，数学成绩相同再按照语文成绩进行排序。这该如何解决呢？
我们可以使用 sort 来对结构体数组进行排序，排序规则在 cmp 函数里定义即可。比如要想对上述场景进行排队，我们可以这样写：
- 定义结构体
struct Grade
{
int math, chinese, english; // 三科成绩
int sum()
{
return math + chinese + english; // 三科总分
}
} a[101];- 排序规则
bool cmp(Grade a, Grade b)
{
if (a.sum() != b.sum())
return a.sum() > b.sum(); // 降序排列，总分高的排在前面
if (a.math != b.math)
return a.math > b.math; // 总分相同，数学成绩高的排在前面
return a.chinese > b.chinese; // 数学成绩也相同，语文成绩高的排在前面
}- sort 排序
sort(a + 1, a + 100 + 1, cmp);例 4：学生成绩排名
期末考试落下帷幕，学校需要对学生成绩进行精准分析。
现已知每位学生的学号以及对应的考试成绩，现在学校有一个特殊需求，希望你能够凭借聪明才智，对学生成绩进行排序，最后精准输出第 m 名学生的学号和成绩。但需要注意的是，可能存在若干个学生成绩相同的情况，此时学号较小的学生将优先被输出。
【输入格式】输入 t + 1 行。
第 1 行输入两个整数，第一个整数 t 表示有 t 组数据，第二个整数 m 表示所求学生的成绩排名。
接下来 t 行中，每行一组数据，其中第一个数表示学号 n，第二个数表示学生的总成绩 s（t ≤ 10000，m ≤ 10000，n ≤ 10000，s ≤ 1000）。
【输出格式】输出一行，为成绩排第 m 名的学生的学号及成绩。
【输入样例】
3 2
1234 179
1345 172
1435 167【输出样例】1345 172
解析
结构体定义：定义一个名为 stu 的结构体，用于存储学生的信息，在结构体内声明两个 int 类型的变量，分别表示学生的学号和学生成绩。
自定义比较函数：定义比较函数 cmp，用于在排序时比较两个学生的信息，如果两个学生的成绩不相等，那么按照成绩从高到低排序，即成绩高的学生排在前面；如果两个学生的成绩相等，那么按照学号从小到大排序，即学号小的学生排在前面。代码如下：
bool cmp(stu a, stu b)
{
if (a.s != b.s)
return a.s > b.s;
return a.n < b.n;
}- 主函数内调用 sort 函数对其学生成绩进行排序，最后输出第 m 名学生的信息。
参考代码
#include <iostream>
#include <algorithm>
using namespace std;
struct stu
{
int n, s;
} xs[10001];
bool cmp(stu a, stu b)
{
if (a.s != b.s)
return a.s > b.s;
return a.n < b.n;
}
int n, m, t = 0, sum;
int main()
{
cin >> t >> m;
for (int i = 1; i <= t; i++)
cin >> xs[i].n >> xs[i].s;
sort(xs + 1, xs + t + 1, cmp);
cout << xs[m].n << " " << xs[m].s;
return 0;
}