线上课 #10：结构体指针与链表结构

type

status

date

slug

summary

📝 课程大纲

结构体指针

结构体指针的定义与使用

自引用结构

链表结构

链表的定义

链表的结构、建立、输出

链表的遍历、搜索

链表结点的插入、删除

求链表的长度

双向链表

循环链表

🤗 整理归纳

链表入门

链表是复合类型，可以用 struct 定义它的每个结点

结点是递归类型，它的数据包含了指向本类型的指针

注意，只可以包含 Node* 类型的变量，不可以包含 Node next;

想想看，如果这样，sizeof(Node) = ????

结点的内存一般是动态申请的。

当增加数据的时候，申请内存。

删除数据的时候，释放内存。

对结点的常规操作

求链表的长度

这是个耗时的动作，可以想办法优化

增加

为什么要返回？

为什么不在尾巴上添加？

查找

删除

删除需要取得目标的前一个结点，原理：

实时效果反馈

1. 怎样在链表表尾添加新结点？____

A 首先让表头指针指向表尾

B 首先让表尾指针指向表头

C 首先根据表头，找到表尾结点

D 首先把表尾 next 置为 NULL

2. 当单向链表较长时，下列哪个操作特别耗时？：____

A 求链表的长度

B 在表头添加结点

C 删除表头

D 判断是否为空链表

答案

1=>C 2=>A

带表头的单链表

最简单链表的弱点：

在指定位置插入、删除，都需要该位置的前趋结点

为了方便查找后进一步处理，查找后返回目标的前趋，可是还要兼顾“找不到”这个信息

每次操作后都要返回新的头结点很不方便。

删除和查找，逻辑重复，坏味道。。。

删除所有结点怎么处理？

增加一个头结点，即可解决很多问题。

插入，插入为 p 的后继

任意位置的插入

删除并不负责释放空间。这样设计很灵活。

因为，使用者可能想把某个结点摘下来，挂到其它地方去

动态内存的管理

从这个实际的例子看到：

只要可行，就优先执行：谁申请，谁释放的原则

该原则，很难完全贯彻执行，分离的管理要小心、细致，很容易泄漏

照顾 API 设计的原则：尽量不要重复；不要冗余；尽量灵活；尽量易于使用

实时效果反馈

1. 下列哪个==不是== 增加表头结点，带来的好处：____

A 更方便地返回目标结点的前趋

B 可以减少 NULL 指针的判断

C 可以避免总是去更改 head

D 可以更快找到尾结点

2. 动态内存管理的一般原则是：____

A 谁申请，谁负责释放

B 被调方申请，主调方释放

C 一个被调函数中申请，在另一个被调函数中释放

D 较早申请的，较先释放

答案

1=>D 2=>A

双向循环链表

增加表头后，单向链表仍有缺点：

从当前结点找它的前趋很吃力

从表头找到表尾很吃力，因而在表尾添加很麻烦

插入、删除时，总是持有当前结点的前趋，这很不直观。

解决方案：

没有免费的午餐，

牺牲空间，换来方便……

增加了一个 prev 数据域，与 next 呈对称之势

在栈中创建头结点的正确姿势：

这是先让蛇咬住自己的尾巴，形成一个闭合的空环

在 p 结点之前，挂接 q 结点（插入）

先挂红指针，后挂粉色指针

删除当前结点

这里有个 API 设计技巧：

为什么要返回 p？p 是主调方送来的，我还原样送回去？

为了主调方的 接力写法

看这个删除所有结点的表达法：

实时效果反馈

1. 双向循环链表的好处，说法==错误==的是：____

A 可以快速找到尾结点

B 可以很方便在尾部添加

C 可以很快求出链表长度

D 可以很快找出当前结点的前趋和后继

2. 在双向循环链表中插入新结点 q，需要更改几个指针？：____

A 1

B 2

C 3

D 4

答案

1=>C 2=>D

约瑟夫环

【问题】

有 n 个小朋友排成一个圆圈，编号 1~n （顺时针）。

从 1 号开始，顺时针报数 1, 2, 3...，报到 3 的小朋友出列，下一个继续从 1 开始报。

求最后剩下的小朋友是几号？

【分析】

构建一个与问题相仿的模型：

单向循环链表，无表头

data 中存小朋友的编号

不断重复游戏规则，最后剩下一个小朋友时，输出它的号码

【构建的过程很重要】

自顶向下的风格

先不要陷入细节，从宏观上写，先写需求，后写实现

复杂的逻辑分解开，放在不同的函数里

测试驱动的风格

代码未动，测试先行

边写边测试，不要等全写完了，一堆的错误

实时效果反馈

1. 使用循环链表，我们==不可以==做？____

A 连续地在表头插入时，可以不用更改head指针

B 方便地从表尾回到表头

C 方便地找到前趋结点

D 方便地找到后继结点

2. free 与 delete 的区别是？____

A free 只是释放空间，并不知道类型，不会调用相应的析构函数

B delete 比 free 释放更规范，是新标准

C delete 效率更高

D delete 会进行碎片清理

答案

1=>C 2=>A