第九章 结构体、枚举类型和链表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里是内存残留读出来是什么数全看运气用之前务必先赋值。C11 起还能缺省字段值写在定义里初始化时可以不写。struct Student { string name; int grade 1; int score 0; }; Student e { 赵六 }; // grade 是 1score 是 01.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 的结构体常见平台上占八字节两个字段挨着坐。┌─────────────────────────────────────────────────┐ │ 点号和箭头 │ ├─────────────────────────────────────────────────┤ │ 变量用点指针用箭头 │ │ │ │ ------------------------------------------ │ │ |手上是什么 |访问成员的写法 | │ │ ------------------------------------------ │ │ |Student 变量 |stu.name | │ │ |Student 指针 |p-name | │ │ |想用点的场合 |(*p).name 也对 | │ │ ------------------------------------------ │ │ │ │ 箭头是点的缩写两条线一回事 │ │ - 前面必须是个地址 │ └─────────────────────────────────────────────────┘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; }┌──────────────────────────────────────────────────────┐ │ 过门的规矩 │ ├──────────────────────────────────────────────────────┤ │ 一条数据过门三条路 │ │ │ │ ---------------------------------------------- │ │ |写法 |形参拿到啥 |改得动吗 | │ │ ---------------------------------------------- │ │ |Student s |整份拷贝 |改的是副本 | │ │ |Student *p |一个地址 |改得了 | │ │ |const Student s|原数据的别名 |只读 | │ │ ---------------------------------------------- │ │ │ │ 小的传值省心大的传引用 │ │ 不碰原数据const 焊死在前面 │ └──────────────────────────────────────────────────────┘只读的场合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 是什么编译器不管跑出怪现象慢慢查。┌───────────────────────────────────────────────────┐ │ 数字没名字 │ ├───────────────────────────────────────────────────┤ │ 0 1 2 是谁的天下 │ │ │ │ -------------------------------------------- │ │ |代码里 |三个月后 | │ │ -------------------------------------------- │ │ |if (state 0) |0 是什么状态 | │ │ |if (state 1) |1 又是什么状态 | │ │ |if (state 2) |翻定义去累 | │ │ -------------------------------------------- │ │ │ │ 换成名字写代码自己会说话 │ │ 名字顶替数字错拼编译器就拦 │ └───────────────────────────────────────────────────┘枚举就是给数字上户口。给每个数起个名字代码自己会说话。enum State { IDLE, RUNNING, STOPPED }; State s RUNNING; if (s RUNNING) { /* 干什么 */ }名字顶替数字错拼一个字母编译器就拦下这比默默跑错强太多。2.2 enum 的基本用法定义一条枚举enum 加名字花括号里列名字逗号隔开分号收尾。enum Color { RED, GREEN, BLUE };不写值时从 0 起自动编号RED 是 0GREEN 是 1BLUE 是 2。可以指定从哪儿起头也可以只给中间的。enum Level { LOW 1, MID 5, HIGH 10 }; // LOW 1MID 5HIGH 10 enum Err { OK, WARN 100, FATAL }; // OK 0WARN 100FATAL 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编译器直接拦。C11 送来 enum class把名字收进枚举自己家里。2.3 enum classenum class Color { RED, GREEN, BLUE }; enum class Week { Mon, Tue, Wed }; Color c Color::RED; // 得报清家门 Week d Week::Mon;必须带前缀 Color::REDWeek::Mon。名字归自己管撞不到别人。还有个好处不会偷偷转成 int和老式 enum 划清界限。#include iostream using namespace std; enum class Week { Mon, Tue, Wed }; int main() { Week d Week::Mon; cout static_castint(d) endl; // 0 // cout d endl; // 编译不过不让直接输出 // if (d 1) { } // 编译不过不和 int 比 return 0; }┌───────────────────────────────────────────────────┐ │ 枚举三种脸 │ ├───────────────────────────────────────────────────┤ │ 老写法新写法一堂课认全 │ │ │ │ -------------------------------------------- │ │ |写法 |长相 | │ │ -------------------------------------------- │ │ |enum Color |RED GREEN BLUE | │ │ |enum Level |LOW1 MID5 HIGH10 | │ │ |enum class Week |Mon Tue Wed | │ │ -------------------------------------------- │ │ │ │ 不带 class名字直挺挺躺在外层 │ │ 带 class得报清 Week 家门 │ │ 新工程起手就上 class 版 │ └───────────────────────────────────────────────────┘想输出得 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当终点站。C11 起空指针写 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 是链表程序的标配从头开始逐个 deletehead 一路往前推。第六章说过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; };C11 起点号取成员s.a变量场合箭头取成员p-a指针场合嵌套初始化S s { 1, { 2, 3 } };一层层对位sizeofsizeof(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 classcout 打不出枚举enum class 不让转 intstatic_cast 一下枚举值不是预期那个指定编号后跟着走数一遍每个的值sizeof 比想的大对齐补齐字段按大小从大到小排遍历卡死或读乱next 没走到空指针查最后节点放没放 nullptr头插后链断了next 和 head 顺序反了先存旧头再改 head删完节点踩垃圾delete 后又读它先跨线再 delete读完再释放跑久了内存涨new 的没 delete收工 while 逐个释放