九、结构体

到这一页，你可能已经感觉到一个问题：数组只能存「同一种东西的一串」。

一个学生的信息有姓名（字符串）、语文成绩（整数）、数学成绩（整数）、总分（整数）——用数组怎么存？开四个数组，然后靠下标 i 把它们「对齐」：

char name[105][20];
int chinese[105], math[105], total[105];
// 第 i 个学生的信息在 name[i]、chinese[i]、math[i]、total[i]

能跑，但很容易出错：排序的时候你得同时交换四个数组的对应位置，漏一个就全乱。

结构体就是来解决这个问题的——把属于同一个对象的一组数据，打包成一个整体。

这一页 2 章 11 道题。题量不大，但它是「从写小程序到写能维护的程序」的分界线。

29. 定义、访问与数组

29.1 定义自己的类型

struct Student {
    char name[25];
    int chinese;
    int math;
    int total;
};

struct 定义一个「类型」，就像 int 是一种类型一样。区别是 int 只能装一个数，Student 能装一组相关的数据。

定义完就有了一种新类型，可以像 int 一样声明变量：

Student s;                    // 一个学生
Student a[105];               // 105 个学生

访问成员用点号：

s.chinese = 90;
s.math = 85;
s.total = s.chinese + s.math;      // 180
strcpy(s.name, "张三");            // 字符数组不能直接赋值

s.total = s.chinese + s.math 这行最能说明结构体的好处——总分和它的两个组成部分在一起，一眼就知道关系。

struct Student { ... };     // 放在这里，全局

int main() {
    Student s;               // 这里才能用
}

还有一个新手常犯的：结构体定义结尾的分号不能漏。

struct Student {
    int x;
};          // ← 这个分号漏了，报错信息会指向莫名其妙的地方

29.2 结构体作为函数参数

结构体可以整个传给函数：

int calcTotal(Student s) {
    return s.chinese + s.math;
}

注意这里又是复制传参——传进去的是整个结构体的副本。所以：

• 如果结构体很大（比如里面有长字符串），复制会有开销
• 函数里改 s.chinese 不会影响原来的变量

需要修改原变量时，用引用：

void addBonus(Student &s) {      // 加了 &，传的是本体
    s.total += 10;
}

& 在这里是「引用」，意思是「不复制，直接用原来那个」。第 3 章 scanf 里的 & 是取地址，这里是引用——长得一样，作用都是为了「操作本体而不是副本」。

29.3 结构体数组

最常见的用法：一个数组装一堆对象。

Student a[105];
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
    scanf("%s %d %d", a[i].name, &a[i].chinese, &a[i].math);
    a[i].total = a[i].chinese + a[i].math;
}

注意 scanf("%s", a[i].name) 不加 &——数组名本身就是地址（第 31 章会详细解释）。

a[i].chinese 这个写法要习惯：先按下标取出第 i 个学生，再用点号取出他的语文成绩。

30. 结构体数组与多关键字排序

这一章解决一个具体问题：怎么按自定义规则排序。

30.1 sort 的第三个参数

第 24 章用过 sort(a, a+n)，那是按默认规则（从小到大）排。现在要按「总分从高到低」排，就得告诉 sort 你的规则。

规则写成一个函数：

bool cmp(Student a, Student b) {
    return a.total > b.total;      // 总分大的排前面
}

sort(stu, stu + n, cmp);

cmp(a, b) 的含义是：「a 应该排在 b 前面吗？」

• 返回 true：a 排前面
• 返回 false：b 排前面

所以 a.total > b.total 表示「a 的总分比 b 大时，a 排前面」，也就是从大到小。

想从小到大就改成 a.total < b.total。

bool cmp(Student a, Student b) {
    return a.total >= b.total;     // 错！可能导致程序崩溃
}

30.2 多关键字排序

真实题目经常要求「总分相同看语文，语文相同看数学」：

bool cmp(Student a, Student b) {
    if (a.total != b.total) return a.total > b.total;    // 第一关键字
    if (a.chinese != b.chinese) return a.chinese > b.chinese;  // 第二关键字
    return a.math > b.math;                               // 第三关键字
}

写法套路：逐级比较，前面的分出胜负就直接返回，分不出才看下一级。

这个结构几乎是所有多关键字排序的标准写法，记住它。

还有一种更紧凑的写法（利用「与」的短路特性）：

bool cmp(Student a, Student b) {
    if (a.total != b.total) return a.total > b.total;
    return a.chinese > b.chinese;
}

30.3 排序的稳定性与原始顺序

有个细节值得知道：sort 是不稳定的——两个「相等」的元素，排完之后谁在前谁在后，不确定。

如果题目要求「分数相同时，按输入顺序输出」，你有两个办法：

办法一：在 cmp 里加一个「编号」关键字

struct Student {
    int id;          // 输入顺序
    int score;
};

bool cmp(Student a, Student b) {
    if (a.score != b.score) return a.score > b.score;
    return a.id < b.id;      // 分数相同，编号小的在前
}

办法二：用 stable_sort（稳定排序，代价是稍慢）

stable_sort(a, a + n, cmp);

推荐办法一——它不依赖库的行为，而且逻辑更明确。

30.4 更复杂的排序题

延伸阅读

服务器上有一整套 OI-Wiki（621 页），是给竞赛选手写的参考手册。下面几页跟这一页相关，但不是每一页都该现在看——标了「现在跳过」的，等以后再说。

• 可以先看：结构体 —— 结构体的完整说明，含成员访问和初始化