C语言学习笔记——结构体与共用体

1 三个数组的麻烦

数组与字符串开头是"要存 100 个数就用数组". 那 100 个数是同一种类型, 排一排正好

学生的信息就不一样了:

1
2
3
int   id;        // 学号
char name[20]; // 姓名
float score; // 成绩

三个字段三种类型, 硬要装就只能开三个平行的:

1
2
3
int   ids[50];
char names[50][20];
float scores[50];

现在这种写法要是想把"第 3 个学生"整个传给函数, 得传三个值; 想排序, 三个数组要同步交换

问题是这三个值本来是一件事, 却被拆成了三份. 结构体就是把它们重新捆成一个类型:

1
2
3
4
5
struct Student {
int id;
char name[20];
float score;
};

现在 struct Student 和 int、float 一样, 是个完整的类型名

2 定义与使用

1
2
3
4
struct 结构体名 {
类型 成员名;
...
};

Student 叫结构体名(标签), 里面每一项叫成员. 结尾那个分号不能丢

有了类型就能声明变量:

1
2
struct Student s1;
struct Student s2 = {1001, "Tom", 91.5};

初始化语句中大括号里的值要按成员顺序一个个对上. 用 . 访问(读取):

1
2
3
4
5
s1.id = 1002;
strcpy(s1.name, "Jerry");
s1.score = 88.0;

printf("%d %s %.1f\n", s1.id, s1.name, s1.score); // 1002 Jerry 88.0

注意: name 是数组, s1.name = "Jerry" 编不过, 得用 strcpy. 这个和数组与字符串里说的一样, 数组名不能整体赋值

结尾的分号

1
2
3
4
5
struct Student {
int id;
} // 少了分号

int main() { ... }

编译器会把 int main() 当成接着定义成员, 然后报一串莫名其妙的错

3 结构体数组

1
2
3
4
5
struct Student cls[3] = {
{1, "Tom", 90.0},
{2, "Jerry", 85.5},
{3, "Spike", 77.0}
};

外层是数组, 里面每个大括号是一个元素. 两次下标:

1
printf("%d\n", cls[1].id);     // 2

遍历跟普通数组相同:

1
2
3
int i;
for (i = 0; i < 3; i++)
printf("%d %s %.1f\n", cls[i].id, cls[i].name, cls[i].score);
1
2
3
1 Tom 90.0
2 Jerry 85.5
3 Spike 77.0

sizeof 结果:

1
2
sizeof(cls);      // 84
sizeof(cls[0]); // 28

84 就是 3 乘 28. 至于一个 struct Student 为什么正好是 28, 但换个成员顺序就未必了, 后文细说

4 结构体指针

1
2
struct Student s = {1001, "Tom", 91.5};
struct Student *p = &s;

用指针取成员,不能写 *p.id:

1
2
3
*p.id        // 错: . 的优先级比 * 高, 等于 *(p.id)
(*p).id // 对, 但括号烦
p->id // 对

-> 就是为这种情况发明的, 意思是"顺着指针取成员", 等价于 (*p).id 但不用写括号

1
2
3
printf("%d\n", p->id);      // 1001
printf("%d\n", (*p).id); // 1001
printf("%s\n", p->name); // Tom

p++ 会跳一整个结构体:

1
2
3
4
5
6
struct Student *p = cls;
int i;
for (i = 0; i < 3; i++) {
printf("%d %s %.1f\n", p->id, p->name, p->score);
p++;
}

-> 和 . 混用是最常见的错

1
2
3
4
5
struct Student s;
struct Student *p = &s;

s->id = 1; // 错, s 不是指针
p.id = 1; // 错, p 是指针

变量用 ., 指针用 ->. -> 长得像箭头, 箭头就是"顺地址过去"的意思

因此最佳办法是只记住正确用法

5 typedef

struct Student 写起来长, typedef A B 作用是给A一个别名B:

1
2
3
4
5
typedef struct Student {
int id;
char name[20];
float score;
} Stu;

这句先后定义了 struct Student, 又给它起了别名 Stu

1
2
struct Student a;
Stu b; // 一样

更常见的写法是连标签都省掉:

1
2
3
4
typedef struct {
int x;
int y;
} Point;

另外 typedef 对普通类型的语句也适用:

1
2
typedef int INT;
INT a = 10; // 就是 int a = 10;

typedef 后面的名字是类型, 不是变量

1
2
3
typedef struct { int x; } Point;
Point = 10; // 错, Point 是类型
Point p; // 对

typedef 定义的是类型别名, 想声明变量得另写一行

6 传参和返回

结构体可以像普通变量一样传进函数

1
2
3
4
5
6
7
8
9
10
void move_by_value(struct Point p, int dx, int dy)
{
p.x += dx;
p.y += dy;
printf("inside: %d %d\n", p.x, p.y);
}

struct Point a = {1, 2};
move_by_value(a, 10, 20);
printf("after: %d %d\n", a.x, a.y);
1
2
inside: 11 22
after: 1 2

函数里改的是副本. 这就是函数讲的传值, 只是这次拷贝的是整个结构体

想改原件就传地址:

1
2
3
4
5
6
7
8
void move_by_ptr(struct Point *p, int dx, int dy)
{
p->x += dx;
p->y += dy;
}

move_by_ptr(&a, 10, 20);
printf("after: %d %d\n", a.x, a.y); // 11 22

结构体一大会很亏. 假设它占 100 字节, 传值就是每次调用都复制 100 字节, 而函数可能只是读一下

1
2
void show(struct Student *s);            // 传指针
void show(const struct Student *s); // 传指针 + 承诺不改, 更好

加了 const 之后函数里想改也改不了. 和指针里把 const char * 加在字符串参数上是同一个道理

返回结构体是允许的:

1
2
3
4
5
6
7
8
9
10
struct Point make(int x, int y)
{
struct Point p;
p.x = x;
p.y = y;
return p;
}

struct Point b = make(7, 8);
printf("%d %d\n", b.x, b.y); // 7 8

这一点和数组不一样. 数组名是地址, 返回它等于返回一个马上失效的地址, 就是指针里说的悬垂指针. 结构体变量名就是本身

整体赋值也行:

1
2
3
4
5
6
struct Point a = {1, 2};
struct Point b;

b = a; // 合法, 逐成员拷贝
b.x = 99;
printf("%d %d\n", a.x, a.y); // 1 2, a 没受影响

但不能 ==:

1
if (a == b)         // 编译错误
1
error: invalid operands to binary == (have 'struct P' and 'struct P')

要比较只能逐个成员比. memcmp 也能用, 但有个隐患: 填充字节里是什么没有保证, 两个逻辑上一样的结构体可能比出不等, 所以还是逐个比稳当

7 嵌套与自引用

结构体可以套结构体:

1
2
3
4
5
6
7
8
9
10
11
struct Date {
int year;
int month;
int day;
};

struct Student {
int id;
char name[20];
struct Date birthday;
};

访问剥两层:

1
2
3
4
5
struct Student s;
s.birthday.year = 2006;

struct Student *p = &s;
p->birthday.year = 2007;

指针和点可以连着用, -> 在前

结构体能包含自己, 但只能是指针:

1
2
3
4
struct Node {
int data;
struct Node *next; // 对
};
1
2
3
4
struct Node {
int data;
struct Node next; // 错, 大小算不出来
};

第二种编不过. next 里又有 next, 一路套下去, 这个类型到底多大永远确定不了. 指针长度固定, 所以没问题

用这个可以串一条链:

1
2
3
4
5
6
7
8
9
struct Node n1, n2, n3;

n1.data = 1; n1.next = &n2;
n2.data = 2; n2.next = &n3;
n3.data = 3; n3.next = NULL; // 到头了

struct Node *p;
for (p = &n1; p != NULL; p = p->next)
printf("%d ", p->data); // 1 2 3
1
sizeof(struct Node);   // 16, 不是 12

这里 16 而不是 4 + 8 = 12, 而是因为之前说过的对齐

8 共用体

共用体写法跟结构体几乎一样:

1
2
3
4
5
union Data {
int i;
float f;
char str[8];
};

但内存安排完全不同. 结构体是每个成员各占一块:

1
2
3
4
struct Node
┌────────┬────────┬────────┐
│ id │ name │ score │
└────────┴────────┴────────┘

共用体是所有成员叠在同一块上:

1
2
3
4
5
6
union Data
┌─────────────────┐
│ i ┐ │
│ f ├ 共用这一块 │
│ str ┘ │
└─────────────────┘
1
2
3
4
5
union Data u;
struct Node n;

printf("%d\n", (int)sizeof(u)); // 8, 最大的成员 str[8]
printf("%d\n", (int)sizeof(n)); // 16, 三个成员加起来

后果就是改一个, 而动全体:

1
2
3
4
5
6
memset(&u, 0, sizeof(u));
u.i = 65;

printf("%d\n", u.i); // 65
printf("%f\n", u.f); // 0.000000
printf("%s\n", u.str); // A

写进去 65, 读 str 得到 "A", 因为 65 就是 'A' 的 ASCII 码, 它们占的是同一块地方

再狠一点:

1
2
3
strcpy(u.str, "ABCDEFG");
printf("%s\n", u.str); // ABCDEFG
printf("%d\n", u.i); // 1145258561

i 变成 1145258561. 换成十六进制是 0x44434241, 正好是 'A'(0x41)、'B'(0x42)、'C'(0x43)、'D'(0x44) 按小端序拼起来的. 小端序是低位存低地址, 内存里从低到高是 41 42 43 44, 当 int 读就反过来了

共用体的用处主要是省内存和类型双关. 一个数据可能是 int 也可能是 float, 用共用体只占一份:

1
2
3
4
5
6
7
8
union Value {
int i;
float f;
char *s;
};

union Value v;
v.i = 42; // 现在存的是 int

规矩是同一时刻只有一个成员有效, 写哪个读哪个

串着读不会报错, 只是结果是垃圾

1
2
3
union Data u;
u.i = 10;
printf("%f\n", u.f); // 能编译, 打印出来毫无意义

这里是把 10 的二进制按 IEEE 754 解释成浮点数. 和数据类型里"同一串二进制按不同方式解释结果不同"是一回事, 只是那里靠强转, 这里靠共用体天生重叠

struct union
成员内存 各占一块 全重叠
大小 成员之和(还要对齐) 最大成员
同时有效 全部 只有一个

9 枚举

结构体把不同类型捆在一起, 共用体让它们重叠, 枚举管的是另一件事: 给一组固定的整数起名字

写代码时经常遇到"这个变量只能取几个值"的情况, 比如星期几、颜色、性别、状态码. 用宏也能干:

1
2
3
#define RED   0
#define GREEN 1
#define BLUE 2

能用, 但有几个毛病: 宏在预处理阶段就被替换掉了, 编译器根本不知道 RED 和 BLUE 是一组; 调试的时候看到的也是 0、1, 不知道原本叫什么; 想加个新颜色还得手动起名、手动给值

枚举就是为了解决这个:

1
enum Color { RED, GREEN, BLUE };

这一行做了两件事: 定义了一个类型 enum Color, 同时定义了三个枚举常量 RED、GREEN、BLUE

枚举值默认从 0 开始递增:

1
printf("%d %d %d\n", RED, GREEN, BLUE);   /* 0 1 2 */

声明变量跟结构体一样:

1
2
enum Color c = GREEN;
printf("%d\n", c); /* 1 */

可以手动指定值, 后面的接着往上加:

1
2
3
4
5
enum Week {
MON = 1, TUE, WED, THU, FRI, SAT, SUN
};

printf("%d %d %d\n", MON, TUE, SUN); /* 1 2 7 */

只给 MON 赋了 1, 后面六个自动是 2 到 7. 中间也能重设:

1
2
3
enum Mixed { X = 5, Y, Z = 20, W };

printf("%d %d %d %d\n", X, Y, Z, W); /* 5 6 20 21 */

Y 跟着 X 是 6, W 跟着 Z 是 21

枚举变量的大小

1
2
printf("%d\n", (int)sizeof(enum Color));   /* 4 */
printf("%d\n", (int)sizeof(c)); /* 4 */

就是 4 字节, 和 int 一样. 枚举在内存里就是个整数, 没有任何额外开销

枚举到底算不算真的"限制"

不算. C 的枚举没有任何类型检查, 这一点和 C++ 或别的语言不一样:

1
2
enum Color c = 99;      /* 编得过, 存进去就是 99 */
c = 1; /* 也编得过 */

编译器不会拦着, 99 不在 Color 的取值范围内它也照存. 所以枚举是"给人看的约束", 不是给编译器执行的

但反过来, 枚举常量本身是只读的:

1
RED = 5;                /* 编译错误 */
1
error: lvalue required as left operand of assignment

RED 是编译期就定死的符号, 不是变量, 所以 RED++ 这类写法一律不行

枚举的典型用法

最实用的是代替一串魔数:

1
2
3
4
5
6
enum Status { OK = 0, ERR_OPEN, ERR_READ, ERR_WRITE };

enum Status st = ERR_READ;

if (st != OK)
printf("出错了, 代码 %d\n", st); /* 2 */

不加枚举的话, 满屏的 if (st == 2) 没人知道 2 是什么, 三个月后自己都不记得

另一个用法是状态机的状态:

1
2
3
4
5
6
7
8
9
10
enum State { IDLE, RUNNING, PAUSED, STOPPED };

enum State cur = IDLE;

switch (cur) {
case IDLE: /* ... */ break;
case RUNNING: /* ... */ break;
case PAUSED: /* ... */ break;
case STOPPED: /* ... */ break;
}

switch 里直接用枚举常量当 case 标号, 可读性好很多

switch 里别把枚举常量写成数字

1
2
3
4
5
6
switch (cur) {
case 0: /* 能跑, 但看不出是 IDLE */
break;
case IDLE: /* 这样才对 */
break;
}

枚举存在的意义就是让代码能读, 写回数字就白用了

另外 case 后面必须是常量表达式, 枚举常量符合这个要求, 所以能直接用

#define enum
处理阶段 预处理 编译
编译器是否认识 不认识, 只是文本替换 认识, 是个类型
调试器能看到名字 一般不能 能
是否自动递增 不能, 得一个个写 能
有作用域 没有, 全局生效 有, 受块作用域限制

面试常问"枚举和宏有什么区别", 记住三个字: 宏是替换, 枚举是类型

考试里枚举一般考"默认值是多少"和"某个成员等于几", 都是数出来的, 不难

10 *内存对齐

第 3 节那个 28 是巧合, 换成员顺序就未必了:

1
2
3
4
5
6
struct A {
char c; // 1 字节
int i; // 4 字节
};

printf("%d\n", (int)sizeof(struct A)); // 8, 不是 5

虽然 1 + 4 = 5, 但是实际变成了 8. 中间空出来的 3 个字节是填充

原因是 CPU 读内存不是一字节一字节读的, 而是一次读一个字(4 或 8 字节), 而且倾向于从对齐的地址开始读. int 放在 4 的倍数上, 一次就读出来; 放在奇地址上可能要读两次再拼

所以编译器主动插空白, 让每个成员都落在自己合适的边界上

具体有两条规则:

  1. 每个成员的起始偏移得是它自身大小的整数倍
  2. 整个结构体的大小是最大成员对齐值的整数倍

以 struct A 为例:

1
2
3
4
5
6
7
偏移 0  ┌────┐
│ c │ 1 字节
偏移 1 ├────┤
│填充│ 3 字节, 为了 i 落在 4 的倍数上
偏移 4 ├────┤
│ i │ 4 字节
偏移 8 └────┘

总大小 8, 是 4 的倍数, 合规

换个顺序:

1
2
3
4
5
6
struct B {
int i; // 4
char c; // 1
};

printf("%d\n", (int)sizeof(struct B)); // 8

还是 8, 但填充挪到结尾了:

1
2
3
4
5
6
7
偏移 0  ┌────┐
│ i │ 4 字节
偏移 4 ├────┤
│ c │ 1 字节
偏移 5 ├────┤
│填充│ 3 字节, 为了总大小是 4 的倍数
偏移 8 └────┘

结尾必须补齐, 否则数组里第二个元素的 i 就不对齐了

最亏的一种:

1
2
3
4
5
6
7
struct D {
char a; // 1
int i; // 4
char b; // 1
};

printf("%d\n", (int)sizeof(struct D)); // 12, 不是 6
1
2
3
4
5
6
7
8
9
10
11
偏移 0  ┌────┐
│ a │ 1
偏移 1 ├────┤
│填充│ 3
偏移 4 ├────┤
│ i │ 4
偏移 8 ├────┤
│ b │ 1
偏移 9 ├────┤
│填充│ 3
偏移 12 └────┘

12 字节里只用了 6 个, 一半是空的

其他的一些例子:

结构体 成员 大小
char + int 1 + 4 8
int + char 4 + 1 8
char + char + char + int 1+1+1+4 8
char + int + char 1+4+1 12
double + char 8 + 1 16

记住"按最大的成员对齐"即可

真不想对齐有 #pragma pack(1) 这种指令, 嵌入式里做通信协议才用, 考试不考

11 *链表

有了 malloc 和二级指针, 链表就水到渠成了

如果你学过Python, 一定会非常怀念里面看似无限长度的列表

而C里面数组有一个问题, 大小是死的

1
struct Student cls[50];    // 就 50 个, 第 51 个没地方放

链表不需要预先定大小, 要一个节点就申请一个, 用指针串起来:

1
2
3
4
5
6
head
│
▼
┌────┬────┐ ┌────┬────┐ ┌────┬────┐
│ 1 │ ●──┼───►│ 2 │ ●──┼───►│ 3 │NULL│
└────┴────┘ └────┴────┘ └────┴────┘

节点就是第 7 节那个自引用结构体:

1
2
3
4
struct Node {
int data;
struct Node *next;
};

head 指向第一个, 最后一个的 next 是 NULL

建节点

1
2
3
4
5
6
7
8
struct Node *create(int v)
{
struct Node *n = (struct Node *)malloc(sizeof(struct Node));
if (n == NULL) return NULL;
n->data = v;
n->next = NULL;
return n;
}

malloc 的返回值必须检查, 这是指针提出的规矩

遍历

1
2
3
4
5
6
7
8
9
void print(struct Node *head)
{
struct Node *cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}

用了个 cur 而不是直接动 head, 因为外面还要用 head. 和遍历数组不能改原指针是一个道理

头插

1
2
3
4
5
6
7
void push_front(struct Node **head, int v)
{
struct Node *n = create(v);
if (n == NULL) return;
n->next = *head; // 新头的下一个是旧头
*head = n; // 设置新头
}

形参是 Node **. 因为要改的是 head 本身, 写成 Node *head 改的只是副本, 外面不动

尾插

头插不用管后面, 尾插得先走到最后一个. 拿链表 1 -> 2 -> 3 插 4 演示一遍:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
初始:  head -> [1] -> [2] -> [3] -> NULL
↑
cur ← 起点是 *head, 不是 head

第 1 圈: cur 在 [1], cur->next 是 [2], 不是 NULL, 继续
cur = cur->next, cur 落到 [2]

第 2 圈: cur 在 [2], cur->next 是 [3], 不是 NULL, 继续
cur = cur->next, cur 落到 [3]

第 3 圈: cur 在 [3], cur->next 是 NULL, 停!
这时 cur 就是尾节点, 把新节点接上去:
cur->next = n

结束: head -> [1] -> [2] -> [3] -> [4] -> NULL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void append(struct Node **head, int v)
{
struct Node *n = create(v);
struct Node *cur;
if (n == NULL) return;

if (*head == NULL) { /* 空链表, 新节点直接当第一个 */
*head = n;
return;
}

cur = *head;
while (cur->next != NULL) /* 停的条件是"下一个是空" */
cur = cur->next; /* 不是"自己是空" */
cur->next = n; /* 这时 cur 是最后一个 */
}

几个地方值得单独说:

cur = *head 为什么是 *head. 形参是 Node **head, 也就是"头指针的地址". *head 才是头指针本身, 也就是指向第一个节点的那个东西. 想拿到第一个节点, 必须解一层

while (cur->next != NULL) 为什么不是 cur != NULL. 如果写成 cur != NULL, 循环会一直走到 cur 变成 NULL 才停, 那时 cur 是空指针, 再写 cur->next = n 就是解引用空指针, 直接崩. 要的是停在最后一个节点上, 所以判断的是它的 next

最后 cur->next = n 一句就够, 不用管 n->next. 因为 create 里已经把它设成 NULL 了

空链表那个分支不能省. *head 是 NULL 时进入循环, cur = *head 得到 NULL, 第一句 cur->next 就崩了

1
2
3
4
5
6
struct Node *head = NULL;
append(&head, 1);
append(&head, 2);
append(&head, 3); // 1 2 3

push_front(&head, 0); // 0 1 2 3

删除

先看普通写法为什么难受. 想删链表里的某个节点, 本质是让它前面那个节点的 next 跳过它:

1
2
3
4
5
6
删之前:  [1] -> [2] -> [3] -> NULL
↑ 想删这个

删之后: [1] ──────► [3] -> NULL
↑
要改的是 [1] 的 next, 不是 [2] 自己

所以要找的是"目标的前一个节点". 但这就分两种情况了: 如果删的是头节点, 它前面没有节点, 得改 head 本身; 如果删的是中间节点, 改的是某个 next. 两者代码不一样, 写起来就得特判:

1
2
3
4
5
if (head->data == v) {
/* 删头: 改 head */
} else {
/* 删中间: 找前一个, 改它的 next */
}

麻烦在于这两个分支的逻辑几乎一样, 只是"要改的那个东西"不同, 一个是 head, 一个是某节点的 next

next 字段和 head 其实是同类东西, 它们都存着指向某个节点的地址. 那能不能用一个指针, 同时管住这两种情况

能, 就是二级指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int remove_value(struct Node **head, int v)
{
struct Node **cur = head; /* cur 不是指向节点, 是指向"存节点地址的那个格子" */
struct Node *tmp;

while (*cur != NULL) {
if ((*cur)->data == v) {
tmp = *cur; /* 先记住要删的节点 */
*cur = (*cur)->next; /* 让格子里改存下一个节点 */
free(tmp); /* 再释放 */
return 1;
}
cur = &(*cur)->next; /* 格子往后挪一格 */
}
return 0;
}

cur 指的是"装节点地址的格子", 而不是节点本身. 这个格子可能是 head 变量, 也可能是某个节点的 next 字段. 一旦想通这点, 两种情况就合并了

拿链表 1 -> 2 -> 3 删 2 走一遍:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
初始:
head 变量 ┌────┐ 节点2 节点3
│ ●──┼──►[1|●]──►[2|●]──►[3|NULL]
└────┘
↑
cur ← cur 指着 head 这个格子

第 1 圈: *cur 是 [1], data=1, 不等于 2
cur = &(*cur)->next
cur 挪到 [1] 的 next 字段那里

第 2 圈: *cur 是 [2], data=2, 命中!
tmp = *cur 记住 [2]
*cur = (*cur)->next 把 [1] 的 next 改成指向 [3]
free(tmp) 释放 [2]

结束:
head ──►[1|●]──────────►[3|NULL]

命中时那两行是关键:

*cur = (*cur)->next 改的是格子的内容, 也就是让"某个 next"(或 head)指向下一个节点. 此时 [1] 的 next 从 [2] 变成了 [3], [2] 就被跳过了

free(tmp) 不能省, 也不能放在 *cur = ... 之前. 因为要先读出 (*cur)->next 来改, 如果先把 [2] 释放了, 再读它的 next 就是访问已释放的内存

删头节点的过程一模一样, 只是第一次循环就命中:

1
2
3
4
删 1:
*cur 是 [1], 命中
*cur = (*cur)->next 把 head 本身改成指向 [2]
free(tmp)

*cur 这时就是 head 变量, 所以 head 被直接改掉了. 这就是为什么删头不需要特判

cur = &(*cur)->next 这句容易看晕. 拆开读: (*cur) 是当前节点, (*cur)->next 是它的 next 字段, & 取这个字段的地址. 所以 cur 从"指着 head"变成"指着 [1] 的 next", 再下一圈就变成"指着 [2] 的 next"

实测:

1
2
3
4
/* 1 99 2 3 */
remove_value(&head, 2); /* 1, 变 1 99 3 */
remove_value(&head, 1); /* 1, 删掉头, 变 99 3 */
remove_value(&head, 404); /* 0, 没找到 */

这个写法在教科书里叫"二级指针法", 也有人叫"指向指针的指针". 它的价值不在炫技, 而在于把"边界情况"和"普通情况"合并成一条路径. 如果觉得绕, 先用特判版把功能写对, 能跑之后再换也行

整条释放

1
2
3
4
5
6
7
8
9
10
11
12
void free_all(struct Node **head)
{
struct Node *cur = *head;
struct Node *tmp;

while (cur != NULL) {
tmp = cur->next; // 先记住下一个
free(cur); // 再释放当前
cur = tmp;
}
*head = NULL;
}

顺序不能反. 先 free(cur) 再读 cur->next, 就是访问已经还回去的内存

最后那句 *head = NULL 别漏, 否则外面还留着个悬垂指针:

1
2
free_all(&head);
printf("%p\n", (void *)head); // 0000000000000000

12 完整示例

把这篇的东西串起来. 写一个程序, 要求:

  • 存 4 个学生, 每个有学号、姓名、成绩
  • 算出平均分
  • 按成绩从高到低排好再输出
  • 找出第一名, 单独打印

用到的都是前面讲过的: typedef 起别名、结构体数组装数据、const 指针传参、整体赋值来交换

示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#include <string.h>

typedef struct {
int id;
char name[20];
float score;
} Student;

void input(Student *s, int id, const char *name, float score)
{
s->id = id;
strcpy(s->name, name);
s->score = score;
}

void print_all(const Student *a, int n)
{
int i;
for (i = 0; i < n; i++)
printf("%3d %-8s %5.1f\n", a[i].id, a[i].name, a[i].score);
}

float average(const Student *a, int n)
{
float sum = 0.0f;
int i;
for (i = 0; i < n; i++)
sum += a[i].score;
return sum / n;
}

void sort_by_score(Student *a, int n)
{
int i, j;
Student t;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - 1 - i; j++)
if (a[j].score < a[j + 1].score) {
t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}

const Student *best(const Student *a, int n)
{
const Student *m = a;
int i;
for (i = 1; i < n; i++)
if (a[i].score > m->score)
m = &a[i];
return m;
}

int main()
{
Student cls[4];

input(&cls[0], 101, "Tom", 91.5f);
input(&cls[1], 102, "Jerry", 88.0f);
input(&cls[2], 103, "Spike", 95.5f);
input(&cls[3], 104, "Tyke", 72.0f);

printf("原始名单:\n");
print_all(cls, 4);
printf("平均分: %.2f\n", average(cls, 4));

sort_by_score(cls, 4);
printf("\n按分数降序:\n");
print_all(cls, 4);

printf("\n第一名: %s (%.1f)\n", best(cls, 4)->name, best(cls, 4)->score);

return 0;
}

输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
原始名单:
101 Tom 91.5
102 Jerry 88.0
103 Spike 95.5
104 Tyke 72.0
平均分: 86.75

按分数降序:
103 Spike 95.5
101 Tom 91.5
102 Jerry 88.0
104 Tyke 72.0

第一名: Spike (95.5)

sort_by_score 里交换的是整个结构体:

1
2
3
Student t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;

三个字段一起走, 不可能出现"学号换了名字没换"这种错位. 这正是结构体比三个平行数组强的地方. 用三个平行数组的话, 这里得写三次交换, 少写一次就错位

best 返回的是指针, 所以外面能直接 ->name. 如果返回下标, 调用处还得再写 cls[idx].name, 多绕一道

其余几个函数传进去的都是 const Student *, 只有 input 和 sort_by_score 没收 const, 因为它们真的要改数据

13 猎奇小点

结尾的分号: struct X { ... }; 少一个分号, 后面全部报错, 而且报的位置看起来毫不相关

标签和类型名的区别: struct Student 里 Student 是标签, Stu 才是 typedef 出来的类型名. C 里两者不能混, 写了 Stu 就必须有对应的 typedef. C++ 能省 struct, 这里是 C

能赋值不能比较: a = b 合法(逐成员拷贝), a == b 编译错误. 填充字节里可能有垃圾, 没法整体比

匿名结构体: struct { int x; } a; 可以声明变量, 但这个类型没有名字, 别处没法再用

不能包含自身, 能包含自身指针: 前者大小算不出来, 后者固定 4 或 8 字节

sizeof 不等于成员之和: 对齐会插填充, 推导见第 10 节

共用体也要对齐: union { char c; double d; } 是 16 不是 8, 因为要按 double 对齐

枚举不是真的限制: enum Color c = 99; 编得过, C 的枚举没有类型检查, 只是给人看的约束

枚举常量不能赋值: RED = 5; 报 lvalue required, 它是编译期定死的符号, 不是变量

位段: struct { unsigned a : 3; unsigned b : 5; } 按位分配, 是另一种省空间的办法. 考试一般只考结论

-> 的由来: 就是 (*p).x 的简写. 那对括号太容易漏, 漏了变成 *(p.x), 报错信息还看不懂