第九章结构体、枚举类型和链表

1. 结构体

1.1 项目引入-成绩系统第二次改版

先把出事那版摊开。三个数组并排，加个班级字段之后长这样。

#include <iostream>
#include <string>
using namespace std;

int main() {
string names[5] = { "张三", "李四", "王五", "赵六", "孙七" };
int scores[5] = { 78, 92, 55, 100, 88 };
int classes[5] = { 1, 2, 1, 2, 1 };

for (int i = 0; i < 5; i++) {
cout << names[i] << " " << classes[i] << "班 "
<< scores[i] << "分" << endl;
}
return 0;
}

跑起来一切正常。问题不在能跑，在三个数组的关系只存在于写代码的人脑子里。哪天加个家长电话，就是第四条队。

┌─────────────────────────────────────┐
│ 并行数组的暗线 │
├─────────────────────────────────────┤
│ 两条队，一条看不见的线 │
│ │
│ 并排的两条队 │
│ │
│ 名字队分数队 │
│ +—+—+—+ +—+—+—+ │
│ | 张 | 李 | 王 | |78 |92 |55 | │
│ +—+—+—+ +—+—+—+ │
│ ^ ^ │
│ +—– 靠你记 —–+ │
│ │
│ 下标对齐全凭自觉，加个班级字段 │
│ 就得再牵一条，线越多越容易错 │
└─────────────────────────────────────┘

结构体的思路一句话，把一条记录焊成一个整体。名字、班级、分数装进同一个格子，关系和字段都写进代码里，不用人脑牵线。

#include <iostream>
#include <string>
using namespace std;

struct Student {
string name;
int grade;
int score;
};

int main() {
Student stu[5] = {
{ "张三", 1, 78 },
{ "李四", 2, 92 },
{ "王五", 1, 55 },
{ "赵六", 2, 100 },
{ "孙七", 1, 88 },
};

for (int i = 0; i < 5; i++) {
cout << stu[i].name << " " << stu[i].grade << "班 "
<< stu[i].score << "分" << endl;
}
return 0;
}

三条队变成一条队，一个格子住三样东西。想加家长电话，往 struct 里加一行，别处不动。排序也简单了，交换整个 Student，名字班级分数捆在一起走，不存在牵错线。

┌─────────────────────────────────────────────┐
│ 三条队并成一条队 │
├─────────────────────────────────────────────┤
│ 一格住三样，不用再牵线 │
│ │
│ struct Student { │
│ string name; │
│ int score; │
│ }; │
│ │
│ +——————+——————–+ │
│ |写法 |取到的东西 | │
│ +——————+——————–+ │
│ |stu[0].name |第一个人的名字 | │
│ |stu[0].score |第一个人的分数 | │
│ |stu[2].score |第三个人的分数 | │
│ +——————+——————–+ │
│ │
│ 名字和分数装进同一个格子 │
│ 关系不用再靠人脑记 │
└─────────────────────────────────────────────┘

1.2 struct 的定义与初始化

struct 的写法固定，struct 加名字，一对花括号，字段挨个声明，分号收尾。字段的类型可以是学过的任何一种，也可以还是结构体。

struct Student {
string name;
int grade;
int score;
};

记住定义末尾那个分号。花括号后面漏了它，编译器报错的位置能飘到下一行，第一次见容易发懵。

初始化跟着数组学，一串花括号按顺序对位。

Student a = { "张三", 1, 78 }; // 三个字段全给
Student b { "李四", 2, 92 }; // 等号省略也行
Student c = { "王五", 1 }; // 只给前两个，第三个补零
Student d; // 一个不给，里面是垃圾值

只给一部分，剩下的自动补零，和数组一个脾气。一个不给的那种，score 里是内存残留，读出来是什么数全看运气，用之前务必先赋值。C++11 起还能缺省字段值，写在定义里，初始化时可以不写。

struct Student {
string name;
int grade = 1;
int score = 0;
};

Student e = { "赵六" }; // grade 是 1，score 是 0

1.3 成员访问，点号和箭头

结构体变量取成员用点号，指针取成员用箭头。

#include <iostream>
#include <string>
using namespace std;

struct Student {
string name;
int score;
};

int main() {
Student stu = { "张三", 78 };
Student *p = &stu;

cout << stu.name << " " << stu.score << endl; // 张三 78
cout << p->name << " " << p->score << endl; // 张三 78
cout << (*p).name << endl; // 张三

stu.score = 90;
cout << p->score << endl; // 90

return 0;
}

┌────────────────────────────────────────┐
│ 一个格子住两个字段 │
├────────────────────────────────────────┤
│ 成员按声明顺序排 │
│ │
│ ┌──────────────────────────────────┐ │
│ │struct Point { int x; int y; }; │ │
│ │+——–+——–+ │ │
│ │| x | y | │ │
│ │+——–+——–+ │ │
│ └──────────────────────────────────┘ │
│ │
│ 常见平台上两个 int 共八字节 │
│ Student 里含 string，多大看实现 │
│ 成员按声明顺序排，中间可能补齐 │
└────────────────────────────────────────┘

点号和箭头是一条路。p->score 就是 (*p).score 的缩写，两条线一回事，箭头纯粹少打几个字。指针改成员，原变量跟着变，第六章解引用的规矩在这接着用。

1.4 结构体数组与嵌套

结构体数组就是一条队，每格住一个完整记录，上一节的 Student stu[5] 已经是了。取第 i 个人的分数，stu[i].score，下标和点号连用，先挑格子再取字段。

结构体套结构体也自然，字段的类型可以是另一个结构体。

#include <iostream>
#include <string>
using namespace std;

struct Date {
int year;
int month;
int day;
};

struct Student {
string name;
Date birthday;
int score;
};

int main() {
Student stu = { "张三", { 2005, 9, 1 }, 78 };

cout << stu.name << " " << stu.birthday.year << "年"
<< stu.birthday.month << "月" << stu.birthday.day << "日 "
<< stu.score << "分" << endl;

return 0;
}

点号可以连着写，stu.birthday.year 一层层往里走。嵌套别贪深，两层够用，三层以上读起来费劲，该拆的时候拆。

内存里字段按声明顺序排，编译器可能在中间塞补齐字节。看个干净的，两个 int 的结构体，常见平台上占八字节，两个字段挨着坐。

1.5 内存对齐，8 对 12

同样三个字段，换个顺序排，占地能差一半。这不是编译器抠门，是对齐在管事。int 爱坐在四的倍数地址上，char 哪儿都能坐。struct A 里两个 char 挤在前头，补齐两字节，int 坐第四格起，总共八字节。struct B 里 char 坐第一格，int 得挪到第五格起，末尾那个 char 后面还得再补三字节，总共十二字节。

┌────────────────────────────────────────────┐
│ 补齐的空地 │
├────────────────────────────────────────────┤
│ 同样三个字段，排法不同占地差一半 │
│ │
│ struct A { char c1; char c2; int n; }; │
│ +–+–+–+–+–+–+–+–+ │
│ |c1|c2|补|补| n | │
│ +–+–+–+–+–+–+–+–+ │
│ │
│ struct B { char c1; int n; char c2; }; │
│ +–+–+–+–+–+–+–+–+–+–+–+–+ │
│ |c1|补|补|补| n |c2|补|补|补| │
│ +–+–+–+–+–+–+–+–+–+–+–+–+ │
│ │
│ 八字节对十二字节，补齐的空地占着不用 │
│ 大的先声明，小的随后跟 │
└────────────────────────────────────────────┘

代码里不用背规则，记住一条就够，字段按大小从大到小声明，char 放一堆，int 放一堆，string 放最前，补齐的空地能少一大块。sizeof 随时问，别猜。

#include <iostream>
using namespace std;

struct A { char c1; char c2; int n; };
struct B { char c1; int n; char c2; };
struct C { int n; char c1; char c2; };

int main() {
cout << sizeof(A) << " " << sizeof(B) << " " << sizeof(C) << endl;
return 0;
}

常见平台输出 8 12 8。A 和 C 字段一模一样，只换了顺序，一样大。B 白白胖出四字节。这是行为跟平台走，换台机器可能不同，sizeof 自己问才作数。

1.6 结构体进函数

结构体当参数，第七章那三条路原样适用，值传递、指针、引用。Student 这种个头大的，值传递要整份拷贝，能省则省。

#include <iostream>
#include <string>
using namespace std;

struct Student {
string name;
int score;
};

void printByValue(Student s) {
cout << s.name << " " << s.score << endl;
}

void raise(Student *p, int delta) {
p->score += delta;
}

void show(const Student &s) {
cout << s.name << " " << s.score << endl;
}

int main() {
Student stu = { "张三", 78 };

printByValue(stu); // 张三 78，副本改不动原值
raise(&stu, 5); // 张三 83
show(stu); // 张三 83

return 0;
}

只读的场合，const Student &s 是首选，不拷贝又碰不了原数据。要改的场合，引用和指针都行，第七章讲过怎么挑，小数据值传递，要改数据用引用。结构体还能当返回值，return 一个 Student 回去，调用点接住，第七章说过的拷贝规矩一样管。

2. 枚举类型

2.1 0 1 2 说不清

状态这种字段，新手最爱拿小整数凑。0 是待机，1 是运行，2 是停机，写起来快，三个月后没人认得。

int state = 0;
if (state == 0) { /* 干什么 */ }
if (state == 1) { /* 干什么 */ }

代码当时看得懂，隔天就糊涂。0 是什么状态，1 又是什么状态，翻定义翻到眼花。更险的是拼写，state == 3 是什么，编译器不管，跑出怪现象慢慢查。

枚举就是给数字上户口。给每个数起个名字，代码自己会说话。

enum State { IDLE, RUNNING, STOPPED };

State s = RUNNING;
if (s == RUNNING) { /* 干什么 */ }

名字顶替数字，错拼一个字母编译器就拦下，这比默默跑错强太多。

2.2 enum 的基本用法

定义一条枚举，enum 加名字，花括号里列名字，逗号隔开，分号收尾。

enum Color { RED, GREEN, BLUE };

不写值时从 0 起自动编号，RED 是 0，GREEN 是 1，BLUE 是 2。可以指定从哪儿起头，也可以只给中间的。

enum Level { LOW = 1, MID = 5, HIGH = 10 }; // LOW 1，MID 5，HIGH 10
enum Err { OK, WARN = 100, FATAL }; // OK 0，WARN 100，FATAL 101

后面的值跟着前一个走，FATAL 是 101，不是 2。这点容易看走眼，编号不一定连续。

枚举变量之间能比大小，switch 里也能用，第七章的 switch 配它正合适。

#include <iostream>
using namespace std;

enum Level { LOW = 1, MID = 5, HIGH = 10 };

int main() {
Level lv = HIGH;

switch (lv) {
case LOW: cout << "低" << endl; break;
case MID: cout << "中" << endl; break;
case HIGH: cout << "高" << endl; break;
}

cout << (MID < HIGH) << endl; // 1

return 0;
}

老式 enum 有个毛病，名字直挺挺躺在外层作用域，和别的枚举撞名算冲突。两个 enum 都有 RED，编译器直接拦。C++11 送来 enum class，把名字收进枚举自己家里。

2.3 enum class

enum class Color { RED, GREEN, BLUE };
enum class Week { Mon, Tue, Wed };

Color c = Color::RED; // 得报清家门
Week d = Week::Mon;

必须带前缀 Color::RED，Week::Mon。名字归自己管，撞不到别人。还有个好处，不会偷偷转成 int，和老式 enum 划清界限。

#include <iostream>
using namespace std;

enum class Week { Mon, Tue, Wed };

int main() {
Week d = Week::Mon;

cout << static_cast<int>(d) << endl; // 0

// cout << d << endl; // 编译不过，不让直接输出
// if (d == 1) { } // 编译不过，不和 int 比

return 0;
}

想输出得 static_cast 转一下，想比较得拿枚举之间对。啰嗦是啰嗦，换来的是 type 安全，值传错了编译器当场拦。新代码优先 enum class，老代码里认得出老写法就行。

3. 链表

3.1 数组的硬伤

数组是条队，一格挨一格。中间插一个人，后面全体搬家。五个人的队还好，五万人的队，插一次搬五万格。

┌──────────────────────────────────────────┐
│ 数组的搬家费 │
├──────────────────────────────────────────┤
│ 插队容易，搬家费吓人 │
│ │
│ 数组 78 92 55 100 88 │
│ 要在下标 1 插个 90 │
│ │
│ 第一步从后往前，88 100 55 依次右移 │
│ 第二步 90 落进下标 1 空出来的位 │
│ │
│ 一个人进场，三个人挪窝 │
│ 人多时候，这笔搬运费吓人 │
└──────────────────────────────────────────┘

删人也一样，中间挖走一个，后面集体前移。这些搬运费，链表一分不花。链表是一节一节车厢，用指针串起来，中间接一节只改两根线。

┌──────────────────────────────────────────┐
│ 车厢的模样 │
├──────────────────────────────────────────┤
│ 一节车厢两样东西 │
│ │
│ ┌────────────────────────────────────┐ │
│ │Node │ │
│ │ +——–+——–+ │ │
│ │ | data | next | │ │
│ │ +——–+——–+ │ │
│ │ 存数据存下一节的地址 │ │
│ └────────────────────────────────────┘ │
│ │
│ 最后一节的 next 放空指针 │
│ 空指针是这条线的终点站 │
└──────────────────────────────────────────┘

3.2 节点长什么样

链表的基本单元叫节点，一个节点装两样东西，自己的数据，和下一节的地址。

struct Node {
int data;
Node *next;
};

结构体里出现指向自己的指针，这叫自引用，合法且常见。最后一节的 next 不放地址，放空指针 nullptr，当终点站。C++11 起空指针写 nullptr，第六章用过。

搭链就是让一节一节的 next 指下去。头插法，新节点往队头塞，尾插法，新节点往队尾接。

#include <iostream>
using namespace std;

struct Node {
int data;
Node *next;
};

int main() {
Node *head = nullptr;

// 尾插 1 2 3
Node *tail = nullptr;
for (int i = 1; i <= 3; i++) {
Node *p = new Node;
p->data = i;
p->next = nullptr;
if (head == nullptr) {
head = p;
} else {
tail->next = p;
}
tail = p;
}

// 顺着 next 走一遍
for (Node *p = head; p != nullptr; p = p->next) {
cout << p->data << " "; // 1 2 3
}
cout << endl;

return 0;
}

输出 1 2 3。尾插保序，先进先出。注意 new 出来的节点，循环里逐个要，程序退出前不 delete 就是泄漏，下一节收拾。

遍历的写法就一句，for (Node *p = head; p != nullptr; p = p->next)。从 head 出发，顺着 next 一路走，走到空指针停。这句是链表的总机关，插删查找都长在它身上。

3.3 头插与遍历

头插法更省事，不用记 tail。新节点的 next 先指向旧头，head 再改指新节点，两步。

Node *head = nullptr;

for (int i = 1; i <= 3; i++) {
Node *p = new Node;
p->data = i;
p->next = head; // 新节点指向旧头
head = p; // 头指针改指新节点
}

for (Node *p = head; p != nullptr; p = p->next) {
cout << p->data << " "; // 3 2 1
}
cout << endl;

输出 3 2 1，后来的站前面，后进先出。两步有顺序讲究，p->next = head 必须先做，先把旧头的地址存下来，再让 head 改指。顺序反了，旧头的地址一丢，整条链断在后面。

┌────────────────────────────────────────┐
│ 链表只动线 │
├────────────────────────────────────────┤
│ 链表只改两根线 │
│ │
│ ┌──────────────────────────────────┐ │
│ │ 新节点 90 │ │
│ │ next –> 92 那间房 │ │
│ └──────────────────────────────────┘ │
│ 78 那间房的 next –> 新节点 │
│ │
│ 一个人的进场费，两根线 │
│ 后面的人原地不动 │
└────────────────────────────────────────┘

3.4 删除与释放

删除要分两头。队头好删，head 往前推一格就行，收工那个 while 干的就是这事。队中间得先找到前一个，让前一个的 next 跨过它，再 delete。

#include <iostream>
using namespace std;

struct Node {
int data;
Node *next;
};

int main() {
Node *head = nullptr;
for (int i = 1; i <= 3; i++) {
Node *p = new Node;
p->data = i;
p->next = head;
head = p;
}
// 此时链是 3 2 1

// 删中间的 2，先找到它前面的 3
Node *prev = head; // 3
Node *cur = head->next; // 2
prev->next = cur->next; // 3 的 next 改指 1
delete cur; // 释放 2

for (Node *p = head; p != nullptr; p = p->next) {
cout << p->data << " "; // 3 1
}
cout << endl;

// 收工，剩下的逐个释放，每轮都是删队头
while (head != nullptr) {
Node *p = head;
head = head->next;
delete p;
}

return 0;
}

输出 3 1。删中间节点三步，找到前一个，让前一个的 next 跨过它，delete 它。顺序不能反，先 delete 再跨线，那条线指着已经释放的内存，踩下去是什么全看造化。

收尾那个 while 是链表程序的标配，从头开始逐个 delete，head 一路往前推。第六章说过，new 出来的内存活到 delete 那一刻，链表这章尤其要盯紧，一节不漏才叫收工。

3.5 链表的代价

链表不是免费午餐，省了搬家费，另有两笔成本。

第一笔，不能随机访问。数组 a[3] 一步到位，链表得从 head 数三节。找第 i 个是 O(i)，数组是 O(1)。按位置反复取的场合，数组赢。

第二笔，缓存不友好。数组在内存里连续排，缓存一次搬一大段，第六章提过。链表的节散在各处，next 指哪儿算哪儿，跳着扫缓存吃亏。

所以选择题很简单，数据定长、按位置取，用数组；数据增减频繁、个头不定，用链表。实际工程里手写链表的机会不多，标准库的 list、vector 都是更好用的成品，第十章之后陆续见。链表的价值在把指针练熟，面试爱问，底层数据结构全靠它打底。

4. 小结

┌──────────────────────────────┐
│ 本章收口 │
├──────────────────────────────┤
│ 三样东西，一条上坡路 │
│ │
│ 结构体关系焊进代码里 │
│ 枚举名字顶替数字 │
│ 链表用指针串起数据 │
│ │
│ 结构体里塞进函数，就是类 │
│ 下一章类与对象，正式开工 │
└──────────────────────────────┘

三样东西一条线。结构体把关系焊进数据，字段挨个声明，花括号初始化，点号取成员，箭头配指针，sizeof 问大小，字段按大小声明省补齐。传参三条路照旧，只读用 const 引用。

枚举给数字上户口，老式 enum 名字躺在外层，enum class 收进自家门还禁隐式转换，新代码优先 class 版。链表一节两样，data 加 next，尾插保序头插逆序，遍历顺着 next 走到空指针，删除先跨线再 delete，收工逐个释放。

链表的选择题记住两句，定长按位置取用数组，常增常减用链表，不能随机访问和缓存吃亏是它的两面。

三个平台的速查卡和排错表在附录，打印贴墙。

附录 A 速查卡

知识点写法说明

定义结构体	struct S { int a; };	末尾分号不能少
初始化	S s = { 1, 2 };	缺的补零
成员默认值	struct S { int a = 1; };	C++11 起
点号取成员	s.a	变量场合
箭头取成员	p->a	指针场合
嵌套初始化	S s = { 1, { 2, 3 } };	一层层对位
sizeof	sizeof(S)	问编译器，别猜
老式枚举	enum E { A, B };	从 0 起
指定编号	enum E { A = 1, B = 5 };	后续跟着走
强类型枚举	enum class E { A };	E::A 访问，禁隐式转换
节点定义	struct Node { int data; Node *next; };	自引用合法
建空链	Node *head = nullptr;	空指针是终点站
头插	p->next = head; head = p;	顺序不能反
尾插	tail->next = p; tail = p;	要记 tail
遍历	for (Node *p = head; p; p = p->next)	链表总机关
删中间节点	prev->next = cur->next; delete cur;	先跨线再释放
整链释放	while (head) { p = head; head = head->next; delete p; }	收工标配

附录 B 排错表

常见现象病根药方

报错 expected 分号	struct 定义末尾漏分号	花括号后补上
成员是垃圾值	变量没初始化	花括号给值，或写默认值
报错 p.name 用不了	p 是指针	改 p->name 或 (*p).name
两个 RED 撞名	老式 enum 名字在外层	换 enum class
cout 打不出枚举	enum class 不让转 int	static_cast 一下
枚举值不是预期那个	指定编号后跟着走	数一遍每个的值
sizeof 比想的大	对齐补齐	字段按大小从大到小排
遍历卡死或读乱	next 没走到空指针	查最后节点放没放 nullptr
头插后链断了	next 和 head 顺序反了	先存旧头再改 head
删完节点踩垃圾	delete 后又读它	先跨线再 delete，读完再释放
跑久了内存涨	new 的没 delete	收工 while 逐个释放

第九章结构体、枚举类型和链表