结构体与结构体排序课堂笔记

配套训练：【基础语法】结构体+结构体排序

---

一、结构体

1. 什么是结构体

结构体可以把同一个对象的多项信息放在一起。

例如，一名学生有学号、姓名和成绩：

struct fd{
	int id,score;
	string name;
};

其中：

• fd 是结构体类型名；
• id、score、name 是结构体成员；
• 一个 fd 变量可以保存一名学生的完整信息。

2. 定义和使用结构体变量

fd s;
cin>>s.id>>s.name>>s.score;
cout<<s.id<<" "<<s.name<<" "<<s.score;

访问结构体成员时使用 .。

3. 结构体数组

有多名学生时，可以定义结构体数组：

const int N=2e5+10;
fd s[N];

输入第 i 名学生：

cin>>s[i].id>>s[i].name>>s[i].score;

结构体数组的优点是：排序时一名学生的所有信息会一起移动，不会出现姓名和成绩错位。

---

二、结构体排序

1. sort 的基本格式

sort(s+1,s+1+n,f);

• s+1：从 s[1] 开始；
• s+1+n：排序到 s[n]；
• f：比较函数。

比较函数的基本形式：

bool f(fd s1,fd s2){
	return s1.score>s2.score;
}

当 s1 应该放在 s2 前面时返回 true。

2. 单关键字排序

按成绩从高到低排序：

bool f(fd s1,fd s2){
	return s1.score>s2.score;
}

按成绩从低到高排序：

bool f(fd s1,fd s2){
	return s1.score<s2.score;
}

口诀：

从小到大用 <
从大到小用 >

3. 多关键字排序

要求：

1. 成绩从高到低；
2. 成绩相同，学号从小到大。

bool f(fd s1,fd s2){
	if(s1.score!=s2.score) return s1.score>s2.score;
	return s1.id<s2.id;
}

写法要点：只有当前关键字相同时，才比较下一个关键字。

4. 字符串关键字

s1.name.size()>s2.name.size() //长度降序
s1.name<s2.name               //字典序升序
s1.name>s2.name               //字典序降序

5. 预先计算新成员

如果排序需要总分，可以在输入时算好：

struct fd{
	int a,b,c,z;
};

cin>>s[i].a>>s[i].b>>s[i].c;
s[i].z=s[i].a+s[i].b+s[i].c;

这样比较函数只需要比较 z，代码更清楚。

---

三、比较函数的规则和常见错误

1. 相等时不能返回 true

错误写法：

bool f(fd s1,fd s2){
	return s1.score>=s2.score;
}

当两个成绩相等时，f(s1,s2) 和 f(s2,s1) 都会返回 true，排序规则发生矛盾。

正确写法：

bool f(fd s1,fd s2){
	return s1.score>s2.score;
}

比较函数中通常使用 < 或 >，不能使用 <= 或 >=。

2. 排序后判断两项是否等价

如果数组已经使用同一个合法的比较函数排好序，并且比较相邻元素，那么可以写：

if(f(s[i-1],s[i])==0){
	//两项在排序关键字上等价
}

原因是排序结果已经保证：

f(s[i],s[i-1])==0

如果正反两个方向都不成立，说明二者在这个排序规则下等价。

注意：这只能证明排序关键字等价，不代表结构体的所有成员完全相同。例如两名学生成绩相同，但学号和姓名可以不同。

如果只按成绩判断并列，直接比较成员会更直观：

if(s[i].score==s[i-1].score){
	//成绩相同
}

3. 括号位置错误

错误：

f(s[i-1],s[i]==0)

程序会先计算 s[i]==0，但结构体不能直接与整数比较。

正确：

f(s[i-1],s[i])==0

4. 多关键字方向写反

题目要求“总分降序，学号升序”时，两个关键字的符号不同：

bool f(fd s1,fd s2){
	if(s1.z!=s2.z) return s1.z>s2.z;//总分降序
	return s1.id<s2.id;//学号升序
}

写比较函数前，先把每个关键字的方向列出来。

---

四、排名与恢复输入顺序

1. 普通排名

排序后，第 i 个对象的名次就是 i：

for(int i=1;i<=n;i++) s[i].m=i;

2. 并列排名

常见的并列排名有两种，必须看清题意。

跳号排名：

1 1 3 4

if(s[i].score==s[i-1].score) s[i].m=s[i-1].m;
else s[i].m=i;

连续排名：

1 1 2 3

if(s[i].score==s[i-1].score) s[i].m=s[i-1].m;
else s[i].m=s[i-1].m+1;

3. 恢复输入顺序

排序会改变顺序。如果题目要求最后按原输入顺序输出，需要保存原位置：

s[i].p=i;

排名计算完成后：

ans[s[i].p]=s[i].m;

最后顺序输出 ans[1] 到 ans[n]。

---

五、经典题目

4778. 信息输出

题意简洁概括

输入 n 名学生的学号、姓名和分数，按照输入顺序的倒序输出所有学生的信息。

题目分析

这道题用于练习结构体的定义、输入和输出。题目没有要求按照成员大小重新排列，所以不需要 sort()，直接从 n 枚举到 1 即可。

时间复杂度为 O(n)。

C++代码

#include<bits/stdc++.h>
const int N=2e5+10;
using namespace std;
struct fd{
	int id,score;
	string name;
};
fd s[N];
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i].id>>s[i].name>>s[i].score;
	}
	for(int i=n;i>=1;i--){
		//倒序枚举，不需要排序
		cout<<s[i].id<<" "<<s[i].name<<" "<<s[i].score<<endl;
	}
	return 0;
}

4780. 期末考试成绩排名

题意简洁概括

把学生按照数学成绩从高到低排序；成绩相同的学生，按照学号从小到大排序。输出排序后的学号、姓名和成绩。

题目分析

每名学生的三项信息必须一起移动，因此使用结构体保存。比较函数先比较成绩，只有成绩相同时才比较学号。

时间复杂度为 O(n log n)。

C++代码

#include<bits/stdc++.h>
const int N=2e5+10;
using namespace std;
struct fd{
	int id,score;
	string name;
};
fd s[N];
int n;
bool f(fd s1,fd s2){
	if(s1.score!=s2.score) return s1.score>s2.score;//成绩降序
	return s1.id<s2.id;//成绩相同，学号升序
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i].id>>s[i].name>>s[i].score;
	}
	sort(s+1,s+1+n,f);
	for(int i=1;i<=n;i++){
		cout<<s[i].id<<" "<<s[i].name<<" "<<s[i].score<<endl;
	}
	return 0;
}

4775. 姓名排序

题意简洁概括

依次按照姓名长度降序、姓名字典序降序、学号降序排列所有学生。

题目分析

这是典型的三关键字排序。比较函数必须严格按照题目给出的优先级书写：前一个关键字不同就立即返回，相同时再比较下一个关键字。

字符串长度使用 size()，字符串可以直接使用 <、> 比较字典序。

C++代码

#include<bits/stdc++.h>
const int N=2e5+10;
using namespace std;
struct fd{
	int id;
	string name;
};
fd s[N];
int n;
bool f(fd s1,fd s2){
	if(s1.name.size()!=s2.name.size()){
		return s1.name.size()>s2.name.size();//姓名长度降序
	}
	if(s1.name!=s2.name) return s1.name>s2.name;//字典序降序
	return s1.id>s2.id;//学号降序
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i].id>>s[i].name;
	}
	sort(s+1,s+1+n,f);
	for(int i=1;i<=n;i++){
		cout<<s[i].id<<" "<<s[i].name<<endl;
	}
	return 0;
}

4773. 奖学金

题意简洁概括

每名学生有语文、数学、英语三科成绩。按照总分降序、语文成绩降序、学号升序排列，输出前 5 名的学号和总分。

题目分析

学号就是输入顺序，可以在输入时记录为 i。总分会被多次比较和输出，因此输入时直接计算并保存。

比较顺序：

1. 总分高的在前；
2. 总分相同，语文高的在前；
3. 仍然相同，学号小的在前。

C++代码

#include<bits/stdc++.h>
const int N=2e5+10;
using namespace std;
struct fd{
	int id,a,b,c,z;
};
fd s[N];
int n;
bool f(fd s1,fd s2){
	if(s1.z!=s2.z) return s1.z>s2.z;//总分降序
	if(s1.a!=s2.a) return s1.a>s2.a;//语文降序
	return s1.id<s2.id;//学号升序
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i].a>>s[i].b>>s[i].c;
		s[i].id=i;//输入顺序就是学号
		s[i].z=s[i].a+s[i].b+s[i].c;//计算总分
	}
	sort(s+1,s+1+n,f);
	for(int i=1;i<=5;i++){
		cout<<s[i].id<<" "<<s[i].z<<endl;
	}
	return 0;
}

4783. 学生的名次3

题意简洁概括

按照成绩降序、学号升序排列学生。成绩相同者名次相同，后续名次连续增加，最后按照原输入顺序输出每个人的名次。

例如成绩排序后为 100、100、90、80，名次是 1、1、2、3。

题目分析

这道题有三个步骤：

1. 保存每名学生的原输入位置 p；
2. 排序后计算连续并列名次；
3. 使用 ans[p] 把答案放回原位置。

姓名不参与排序和最终输出，但仍按照题目格式读入。

C++代码

#include<bits/stdc++.h>
const int N=2e5+10;
using namespace std;
struct fd{
	int id,score,p,m;
	string name;
};
fd s[N];
int n,ans[N];
bool f(fd s1,fd s2){
	if(s1.score!=s2.score) return s1.score>s2.score;//成绩降序
	return s1.id<s2.id;//成绩相同，学号升序
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i].id>>s[i].name>>s[i].score;
		s[i].p=i;//保存原输入位置
	}
	sort(s+1,s+1+n,f);
	s[1].m=1;
	for(int i=2;i<=n;i++){
		if(s[i].score==s[i-1].score){
			s[i].m=s[i-1].m;//同分并列
		}else{
			s[i].m=s[i-1].m+1;//题目要求名次连续增加
		}
	}
	for(int i=1;i<=n;i++){
		ans[s[i].p]=s[i].m;//恢复原输入顺序
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

---

六、结构体排序通用模板

#include<bits/stdc++.h>
const int N=2e5+10;
using namespace std;
struct fd{
	int id,score;
	string name;
};
fd s[N];
int n;
bool f(fd s1,fd s2){
	if(s1.score!=s2.score) return s1.score>s2.score;
	return s1.id<s2.id;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i].id>>s[i].name>>s[i].score;
	}
	sort(s+1,s+1+n,f);
	for(int i=1;i<=n;i++){
		cout<<s[i].id<<" "<<s[i].name<<" "<<s[i].score<<endl;
	}
	return 0;
}

七、课堂总结

完成结构体排序题时，按下面的顺序思考：

1. 一个对象包含哪些信息；
2. 哪些信息需要放进结构体；
3. 是否需要计算总分、平均分等新成员；
4. 排序有几个关键字，每个关键字是升序还是降序；
5. 是否存在并列，属于跳号排名还是连续排名；
6. 最后按照排序顺序输出，还是恢复原输入顺序输出。

最重要的三句话：

比较函数返回 true，表示第一个对象应该放在第二个对象前面。
多关键字排序中，当前关键字相同后才能比较下一个关键字。
排序后的顺序不一定是题目要求的最终输出顺序。