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

一、什么是结构体

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

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

struct student{
    int id;
    string name;
    int score;
};

定义一个学生：

student a;

访问成员时使用点号：

cin>>a.id>>a.name>>a.score;
cout<<a.id<<" "<<a.name<<" "<<a.score;

结构体数组：

student a[N];

输入第 i 名学生：

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

二、为什么使用结构体

如果不用结构体，可能需要分别定义三个数组：

int id[N],score[N];
string name[N];

排序时必须保证三个数组一起移动，容易出错。

使用结构体后，一个学生的全部信息会一起交换：

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

因此，只要结构体成员设计清楚，代码会更短，也更安全。

---

三、结构体的输入和输出

1. 正序输入、正序输出

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

2. 倒序输出

如果题目要求按输入顺序的倒序输出，不需要排序，只要倒序枚举：

for(int i=n;i>=1;i--){
    cout<<a[i].id<<" "<<a[i].name<<" "<<a[i].score<<endl;
}

注意：倒序输出不等于排序。题目只要求把输入顺序反过来时，不需要调用 sort()。

---

四、结构体排序

1. sort 的基本格式

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

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

比较函数的形式：

bool f(fd s1,fd s2){
    //s1应该排在s2前面时返回true
}

必须记住：

返回 true：s1 放在 s2 前面
返回 false：不要求 s1 放在 s2 前面

它不是在回答“二者是否相等”。

2. 单关键字排序

成绩从高到低：

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

学号从小到大：

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

3. 多关键字排序

例如，学生成绩排序的规则是：

1. 成绩高的在前。
2. 成绩相同时，学号小的在前。

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

可以把规则理解为：先比较第一关键字，第一关键字相同后再比较第二关键字。

4. 字符串排序

例如，姓名排序的规则是：

1. 姓名长度降序。
2. 长度相同，姓名字典序降序。
3. 姓名相同，学号降序。

bool f(fd s1,fd s2){
    int l1=s1.name.size();
    int l2=s2.name.size();
    if(l1!=l2) return l1>l2;
    if(s1.name!=s2.name) return s1.name>s2.name;
    return s1.id>s2.id;
}

写多关键字排序时，使用“不同就立刻返回”的形式更清楚。

---

五、比较函数的常见错误

1. 排序后能否用比较函数判断并列

如果已经使用同一个合法的比较函数完成排序，并且比较的是相邻元素，那么下面的写法可以判断两人在排序规则下是否等价：

if(f(a[i-1],a[i])==0){
    //两人在比较函数使用的关键字上相同，可以并列
}

原因是排序后的相邻元素已经保证：

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

如果此时还有 f(a[i-1],a[i])==0，就说明谁都不应该排在谁前面，因此二者在该比较规则下等价。

但要注意：这里证明的是“排序关键字等价”，不一定表示结构体的所有成员完全相同。例如两人的原输入编号 p 可以不同，但成绩关键字相同，仍然应该并列。

为了让代码含义更加直观，也可以单独定义：

bool same(fd s1,fd s2){
    return s1.z==s2.z&&s1.l==s2.l&&s1.g==s2.g;
}

在本题中，两种写法都正确，same() 只是更容易阅读和维护。

2. 括号位置错误

一种常见的错误写法是：

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

这里会先计算：

s[i]==0

但 s[i] 是结构体，不能直接与整数 0 比较，因此编译失败。

如果确实要判断比较函数的返回值，应写：

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

这才是原代码中的括号错误。改正后可以直接用于判断并列，也可以使用独立的 same() 函数让含义更清楚。

3. 相等时返回 true

错误示例：

if(s1.score==s2.score) return true;

两个完全相等的对象不能互相都排在对方前面。完全相等时应返回 false。

---

六、排名问题

1. 普通排名

如果没有并列：

第1名、第2名、第3名、第4名

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

2. 并列且跳号

如果题目规定多人并列时需要跳过后续名次，排名可能是：

1, 1, 3, 4, 4, 6

如果当前学生与前一名并列，排名不变；否则排名应等于当前排序位置 i：

a[1].m=1;
for(int i=2;i<=n;i++){
    if(same(a[i-1],a[i])) a[i].m=a[i-1].m;
    else a[i].m=i;
}

不能写成：

a[i].m=a[i-1].m+1;

因为前面如果有多人并列，下一名需要跳过被占用的名次。

3. 恢复输入顺序

题目先要求按成绩排序计算排名，最后却要求按原输入顺序输出。

输入时保存原位置：

a[i].p=i;

计算排名后：

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

最后输出：

for(int i=1;i<=n;i++) cout<<ans[i]<<endl;

---

七、综合例题：多科成绩排序

题目规则

依次比较：

1. 三科总分，高者在前。
2. 语文、数学两科总分，高者在前。
3. 语文、数学两科最高分，高者在前。
4. 三项全部相同，则并列。

正确代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct fd{
    int a,b,c;
    int z,l,g;
    int p,m;
};

bool f(fd s1,fd s2){
    if(s1.z!=s2.z) return s1.z>s2.z;
    if(s1.l!=s2.l) return s1.l>s2.l;
    return s1.g>s2.g;
}

bool same(fd s1,fd s2){
    return s1.z==s2.z&&s1.l==s2.l&&s1.g==s2.g;
}

fd s[N];
int n,ans[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i].a>>s[i].b>>s[i].c;
        s[i].z=s[i].a+s[i].b+s[i].c;//三科总分
        s[i].l=s[i].a+s[i].b;//语文数学总分
        s[i].g=max(s[i].a,s[i].b);//语文数学最高分
        s[i].p=i;//记录原输入位置
    }
    sort(s+1,s+1+n,f);
    s[1].m=1;
    for(int i=2;i<=n;i++){
        if(same(s[i-1],s[i])) s[i].m=s[i-1].m;
        else s[i].m=i;//不并列时，排名等于排序位置
    }
    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;
}

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

---

八、常见运行错误

1. 数组开小导致段错误

例如题目允许 n<=10000，却只定义：

fd s[105];

但题目范围是：

n<=10000

当输入人数超过 104 时会越界，容易出现 Segmentation fault。应根据范围开数组：

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

2. 程序没有输出

如果只完成排序和排名计算，却没有写最终输出循环，评测会读到 EOF。

完成代码后要检查：

输入是否读完？
算法是否执行？
答案是否输出？
输出顺序是否符合题目？

3. 排名递推错误

并列后下一名不是“上一名排名加一”，而是当前排序位置 i。

4. 排序结果和输出顺序不同

有些题目需要借助排序计算名次，但最后要求按输入顺序输出。因此必须保存 p，不能直接输出排序后的数组。

---

九、结构体排序通用模板

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct fd{
    int x,y,p;
    string s;
};

bool f(fd s1,fd s2){
    if(s1.x!=s2.x) return s1.x>s2.x;//第一关键字降序
    if(s1.y!=s2.y) return s1.y<s2.y;//第二关键字升序
    return s1.p<s2.p;//最后用原编号保证顺序唯一
}

fd a[N];
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y>>a[i].s;
        a[i].p=i;
    }
    sort(a+1,a+1+n,f);
    for(int i=1;i<=n;i++){
        cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].s<<endl;
    }
    return 0;
}

---

十、课堂总结

结构体题可以按照以下步骤完成：

1. 找出每个对象有哪些信息。
2. 把这些信息写进一个结构体。
3. 根据数据范围正确开数组。
4. 输入所有成员，必要时保存原下标。
5. 把题目的排序规则逐条写进比较函数。
6. 如果有并列，可以利用排好序后的比较结果判断，也可以单独写 same()。
7. 排名不并列时使用当前位置 i，处理跳号。
8. 按题目要求的顺序输出答案。

最重要的两句话：

比较函数定义“谁在前面”；排好序后，可以用比较关系判断排序关键字是否等价。
排序后的顺序，不一定是题目要求的最终输出顺序。