链表(一)

官方信息技术老师·25 页·深入(追求细节与边界)·0 次浏览·2 天前
struct底层内存对齐链表基石

链表(一):结构体与联合

看完你能亲手画出 struct 内存布局并讲透 union 共用原理

按 空格/→ 演示下一步

1 / 25 页

全部页面点击任意一页,跳回舞台从这页播放

struct底层内存对齐链表基石

链表(一):结构体与联合

看完你能亲手画出 struct 内存布局并讲透 union 共用原理

1第 1 页 · 链表(一):结构体与联合

为什么需要结构体

假设你是班长,老师递给你一张表:全班姓名、学号、年龄、高考总分各一栏。四个数组分开存?插入转班同学时怎么保证四份数据对齐?聚合需求就从这里冒出来了。

平行存储之痛
相关字段分多个数组或变量,逻辑上同一人却被物理拆散
同步性难题
增删改任何一项都要四处同步,错一处即数据永久错位
语义内聚
同一实体的字段应绑定成单一变量,作为整体传入函数
户籍登记卡对应 →结构体

卡上姓名籍贯绑定一人不可拆,结构体把同实体的多字段捆成一个变量

2第 2 页 · 为什么需要结构体

结构体的定义与声明

c

struct 三种定义写法 + typedef 别名写法同台对比,标签命名一目了然。

代码高亮加载中…

Student、Point 只是类型标签,不是变量;形式二、三只能在定义处声明变量;typedef 把 struct Node 简写成 Node,是链表代码里最常用的形态。

3第 3 页 · 结构体的定义与声明

结构体变量的创建与初始化

上页画好了'学生档案'的空白模板,但模板不会自动装数据。要存小明的各科成绩,得真正'建档'——创建结构体变量,再用初始值把字段填上。

点号访问成员
用 . 读或写某字段,如 s.math = 90
顺序初始化
按声明顺序依次给值,例 {90, "Tom", 1}
指定初始化 C99
用 .成员名 = 值 形式,顺序无关、可读性高
整体清零 ={0}
首个槽写 0 时,其余字段全部自动置 0
户型图与房屋对应 →结构体定义与变量

户型图对应定义、房子对应变量、点号对应拿钥匙开某一间房

4第 4 页 · 结构体变量的创建与初始化

结构体变量的使用示例

c

看一段完整示例:顺序初始化、整体赋值、. 与 ->、嵌套成员、复合字面量五种典型操作。

代码高亮加载中…

演示结构体可整体赋值(数组不行)、. 与 -> 的等价关系、嵌套成员的链式访问,以及 C99 复合字面量。

5第 5 页 · 结构体变量的使用示例

结构体的内存布局

内存对齐规则与 sizeof 计算边界情况

结构体的内存布局
内存对齐规则与 sizeof 计算边界情况
6第 6 页 · 结构体的内存布局

为什么需要结构数组

上一页我们能用一个结构体装下「学号+姓名+成绩」——但一个班有 50 个学生,难道要手写 50 个变量吗?这正是结构数组要解决的问题。

结构数组的声明
struct Student stu[50]; 一行装下整班学生
内存连续排列
每个元素紧挨着放,像座位表一样连续
下标批量访问
stu[i].score 直接拿到第 i 个人的成绩
适合数量固定的场景
班级人数不变时最合适,查询遍历都很快
插入删除是痛点
中间插入一人,后面所有人要整体后移
教室固定座位对应 →结构数组

座位号对应下标,每人占一格连续排开

7第 7 页 · 为什么需要结构数组

结构数组的定义与初始化

c

三种常见写法:先声明再赋值、按位批量初始化、指定下标初始化。

代码高亮加载中…

外层 { } 装数组的 N 个元素,内层 { } 装该元素的成员——嵌套两层大括号是结构数组初始化的标志。

8第 8 页 · 结构数组的定义与初始化

结构数组的内存布局

横向箭头表示内存从低到高,每格是一个结构体,字段紧凑排列

图解渲染中…
ddata 字段,4 字节nnext 指针,8 字节Ssizeof(Node)=16|字段边界,无填充
9第 9 页 · 结构数组的内存布局

结构数组的遍历与操作

c

用三种写法遍历同一个 Student 数组——下标、指针算术、指针自增,输出完全一致。

代码高亮加载中…

三段循环打印同一片内存:arr[i] 与 *(arr+i) 同义;p++ 的真实步长是 sizeof(Student) 字节——这就是「指针算术」比裸 +1 聪明的地方。

10第 10 页 · 结构数组的遍历与操作

结构指针的概念与意义

结构体变量作为实参传递时,整个结构会被复制一份。大结构体复制既费内存又费时间,而且函数内改不到外面。这些问题,正好由指针来解决。

传值复制的代价
结构体作参数时整块复制,字段越多越耗时
传址修改原值
传指针只传 8 字节地址,函数内修改可见于外部
动态分配与链表
malloc 返回结构体指针;节点之间靠指针串联
-> 运算符
p->field 等价于 (*p).field,指针访问成员语法
酒店房卡对应 →结构体指针

房卡只是张小卡片,不复制房间,却能定位并改到原房间

pfield(p).fieldp\to\text{field} \equiv (*p).\text{field}
11第 11 页 · 结构指针的概念与意义

结构体指针的定义与解引用

c

对比 . 与 -> 两种访问方式,看清取地址与解引用在结构体上怎么工作。

代码高亮加载中…

L12 用 & 取 s 的地址赋给结构体指针 p;L14 的 p->name 是语法糖,等价于 L18 的 (*p).name;L20 是 . 高于 * 的优先级陷阱;L23 证明指针能改原变量成员。

12第 12 页 · 结构体指针的定义与解引用

结构体成员的指针访问

前一页拿到指向结构体的指针 p,紧接着的问题是:怎么拿到结构体里的成员?两种写法结果完全一样,但写法上有个让人栽跟头的优先级陷阱。

解引用后访问
(*p).member:把 *p 当结构体变量,再用 . 取成员
箭头运算符
p->member:C 为这种场景专门设计的简写
优先级陷阱
. 优先级高于 *,*p.member 被解析成 *(p.member)
酒店房间号对应 →结构体指针 p

先走进房间(*p)再找物品(.member),等价于前台按房号直接取物(p->member)

pmember(p).memberp\to\text{member} \equiv (*p).\text{member}
13第 13 页 · 结构体成员的指针访问

结构指针的内存示意图

左边的盒子是指针变量 p(装着地址);右边是被指向的结构体对象,在堆上是一段连续内存。

图解渲染中…
a1指针变量本身,占 8 字节,内容是地址值b1被指向的结构体实体,占 sizeof(Struct) 字节c1成员相对 b1 起始地址有固定偏移
14第 14 页 · 结构指针的内存示意图

结构体作为函数参数的问题

值传递的复制开销与边界场景分析

结构体作为函数参数的问题
值传递的复制开销与边界场景分析
15第 15 页 · 结构体作为函数参数的问题

结构体值传递示例

c

演示把结构体按值传入函数时,函数内修改的是副本,原变量不受影响。

代码高亮加载中…

形参按值接收,函数内修改的是栈上的副本;这是结构体作为参数时的默认行为,也是上一节"参数问题"的根因。

16第 16 页 · 结构体值传递示例

结构体指针作为函数参数

上页看到值传递有两个痛点:拷贝整块结构浪费空间,函数内改不动原数据。这页看指针参数怎么一次解决——但它也带来新的注意事项。

传指针写法
形参写 struct Node *p,调用时传 &node
解决拷贝开销
只传 8 字节地址,不再整块复制结构体
可改原数据
函数内通过 *p 直接读写原结构体的字段
const 只读保护
参数加 const 表示不会改原数据,更安全
选指针还是值
指针需判空防崩溃;小结构(如 2 个 int)值传递反而更快
酒店房卡对应 →结构体指针

房卡小、指向房间,能进房改东西;指针小、指向结构体,能改原数据

17第 17 页 · 结构体指针作为函数参数

结构体指针传递示例

c

三个函数演示 in / out / in-out 三种契约:malloc 产出、const 只读、裸指针就地改写。

代码高亮加载中…

L11 是 out 契约(malloc 产出新节点指针);L19–L21 是 in 契约(const 指针只读,写会报错);L26 是 in/out 契约(裸指针允许改原节点)。三种签名对应副作用的三档边界。

18第 18 页 · 结构体指针传递示例

结构体作为函数返回值

上一页把结构体『送进去』时——值传递是副本、指针传递共享原对象。今天反过来:函数把结构体『算出来』再『送出来』,调用方拿到的是副本还是地址?

值返回是副本
返回时把整个结构体复制到调用方的栈帧,修改互不影响
局部指针会失效
函数内局部变量随栈帧销毁,返回它的地址就是野指针
static/堆可返回
static 变量或 malloc 的内存生命周期独立于函数,可安全返回指针
大结构考虑效率
字段很多时复制整块开销大,优先用返回指针或出参
复印一份带回家对应 →值返回结构体

原版随办公室销毁(局部变量),带回家的是独立副本(调用方栈帧)

19第 19 页 · 结构体作为函数返回值

联合体的引入

前面用结构体把多个相关字段合成一个对象,返回时每个成员各占一处、互不干扰。若同一时刻只需保留其中一种结果,能否让这些成员共用一份空间?这就引出联合体。

重叠存储
各成员从同一偏移开始,对同一空间作不同类型解释。
成员覆盖
任一时刻只应激活一个成员,写入其他成员会改写共享表示。
空间大小
大小至少容纳最大成员,并按成员对齐要求扩展。
读取边界
读取非最近写入成员缺乏可移植保证,可能产生陷阱表示。
可换牌子的信箱格对应 →联合体存储区

同一格口对应共同地址,换牌子对应改用不同成员解释

sizeof(U)max1insizeof(mi)\operatorname{sizeof}(U)\ge\max_{1\le i\le n}\operatorname{sizeof}(m_i)
20第 20 页 · 联合体的引入

联合体的定义与使用

c

以 IP 地址为例,看联合体如何让同一段内存被解读为两种不同形态。

代码高亮加载中…

union 定义 IPAddress,addr 与 bytes 共享 4 字节内存;用 . 访问成员,-> 用于指针;sizeof 等于最大成员。

21第 21 页 · 联合体的定义与使用

联合体的内存布局

左右对比:结构体成员错开铺,联合体成员全部从偏移 0 重合,总大小天差地别。

图解渲染中…
Sstruct:成员依次摆放,各占独立区间Uunion:所有成员共享同一段内存ss结构体大小=各成员大小之和us联合体大小=最大成员的大小
22第 22 页 · 联合体的内存布局

结构体 vs 联合体

语法像、内存语义却截然不同:struct 让所有成员同时存活,union 让所有成员共用同一块内存——这是初学者最常踩的概念混淆。

结构体 struct
  • 所有成员同时有效,互不干扰
  • 总大小 = 各成员大小相加(含对齐)
  • 适合组织多个独立字段并存
联合体 union
  • 所有成员共享同一块内存
  • 总大小 = 最大成员的大小
  • 适合同一变量的多形态切换
需要多个字段同时存活选 struct;同一数据有多种互斥类型时选 union,常嵌套在 struct 中实现 tagged union。
23第 23 页 · 结构体 vs 联合体

本章要点

  • 结构体本质是固定布局打包异构字段
  • 大结构体传参用指针,避免整块内存拷贝
  • 结构体与联合体内存模型相反:并存vs互斥
  • 内存对齐与填充让sizeof可能大于成员之和
  • p->x等价于(*p).x,前提是p合法
延伸主题:结构体的自引用与嵌套动态内存分配malloc/free位域与精确内存控制
24第 24 页 · 本章要点

课后思考

先别翻参考答案,给每题留一两分钟认真想——再对照下一段提示看自己想到哪一层。

1如果结构体没有名字(匿名结构体),它和普通结构体有什么本质区别?能独立声明它的变量或作为函数参数吗?

参考答案匿名结构体只能在定义时直接定义变量,标准 C 里无法再声明新实例。没有类型名就没法写函数参数——这是 C 类型系统的硬约束。

2用位域表示 IPv4 地址的 4 段,能节省多少内存?为什么现代代码里几乎看不到这种写法?

参考答案理论上能压到 32 bit,但编译器对齐可能让它和一个 int 一样大。少见是因为可移植性差、字节访问慢、调试不直观、IPv4 也正被 IPv6 替代。

3假如 C 没有指针,只能用数组下标'编号'节点,能不能实现链表?和真指针链表相比缺了什么?

参考答案能,这就是静态链表,用 next[] 数组存下一个节点的下标。但下标空间有限、插入删除要维护空闲池——指针让节点能真正'动态生长'在堆上。

25第 25 页 · 课后思考