资源简介

(共29张PPT)
2.2 链表
课前学习任务
结合数组的特性和基本操作，针对如下例子设计数组以组织和存储关键数据：
① 处理全班同学的信息，时常需要进行信息访问；
② 处理学校外来人员信息，进校时登记信息，出校时移除信息。
链表基本概念
链表是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。
节点结构
数据区域 指针区域
保存数据元素
保存相邻节点的存储地址
某节点
后继节点
前驱节点
链表基本概念
根据节点中指针的数量可以分为:
单向链表：
双向链表：
循环链表：
data next
prev data next
data next
datan nextn
···
链表的特性
① 链表占用的空间不固定；
② 每个链表中一般要有一个头指针，以实现链表的引用和边界处理；
③ 同一链表中每个节点的结构均相同。
存储地址 数据区域 后继指针
0 “黄刚” 1
1 “李丰” -1
2 “王林” 0
3 “吴坚” 2
单链表存储结构
head
单链表示意图
吴坚
2
第一个节点
head
王林
0
第二个节点
黄刚
1
第三个节点
李丰
-1
第四个节点
（尾节点）
请同学们暂停视频，尝试并完成“学习任务单”中的“学习任务一”。
【学习任务一】认识链表
为了满足链表能在两个方向都能进行遍历的需求，请在图1为每个节点补充正确的前驱指针。
存储地址 数据区域 前驱指针 后继指针
0 “黄刚” 1
1 “李丰” -1
2 “王林” 0
3 “吴坚” -1 2
图1 双向链表存储结构图
head
单链表示意图
吴坚
2
第一个节点
地址3
head
王林
0
第二个节点
地址2
黄刚
1
第三个节点
地址0
李丰
-1
第四个节点
地址1
3
2
0
【小要求】与数组的相关操作进行比较，各自的操作效率谁优谁劣？为什么？
链表的基本操作
链表创建
节点访问
节点插入
节点删除
链表的基本操作——链表创建
数据区域 后继指针
链表结构：
“姓名+手机号”
头指针head：指向第一个节点
单向链表
校外人员进出登记：信息插入和删除
链表的基本操作——节点插入
data1 next1
data2 next2
data3 next3
修改新节点和前驱节点的指针
data1 next1
data3 next3
data2 -1
data3 next3
head
插入到第一个节点之前
插入尾节点之后
-1
next2
修改新节点指针和头指针
修改新节点和前驱节点的指针
插入到两个节点之间
①“李彤”入校；
存储地址 数据区域 后继指针
0 “杜刚+1xx.” -1
1 “张强+1xx.” 0
head
2 “李彤+1xx.” -1
2
张强
0
head
杜刚
-1
李彤
-1
新节点
2
链表的基本操作——节点插入
②“李丰”在“杜刚”之前入校；
存储地址 数据区域 后继指针
0 “杜刚+1xx.” 2
1 “张强+1xx.” 0
2 “李彤+1xx.” -1
head
3 “李丰+1xx.” 0
3
张强
0
head
杜刚
2
链表的基本操作——节点插入
李彤
-1
李丰
0
新节点
3
data1 next
data2 next
data3 next
删除中间节点
修改前驱节点的后继指针，让待删节点的前驱和后继直接相连
链表的基本操作——节点删除
data2 next
data3 next
data1 next
data2 next
删除第一个节点
head
删除最后一个节点
请同学们暂停视频，尝试并完成“学习任务单”上“【学习任务二】链表基本操作”。
【学习任务二】链表基本操作
存储地址 数据区域 后继指针
0 “杜刚+1xx.” 2
1 “张强+1xx.” 3
2 “李彤+1xx.” -1
3 “李丰+1xx.” 0
（1）“杜刚”出校，请在如下绘制节点链接关系，并在上述存储结构图中进行相应修改：
head
张强
3
head
杜刚
2
李彤
-1
李丰
0
2
2
【学习任务二】链表基本操作
存储地址 数据区域 后继指针
1 “张强+1xx.” 3
2 “李彤+1xx.” -1
3 “李丰+1xx.” 2
（2）“胡洁”在“张强”之前入校，请在如下修改节点链接关系，并在上述存储结构图中进行相应修改
head
张强
3
head
李彤
-1
李丰
2
4 “胡洁+1xx.” 1
胡洁
1
head
【学习任务二】链表基本操作
（3）“李彤”出校，请在如下修改节点链接关系，并在上述存储结构图中进行相应修改：
胡洁
1
head
李丰
2
李彤
-1
张强
3
存储地址 数据区域 后继指针
1 “张强+1xx.” 3
2 “李彤+1xx.” -1
3 “李丰+1xx.” 2
4 “胡洁+1xx.” 1
head
-1
-1
【学习任务二】链表基本操作
（4）“胡洁”出校，请在如下修改节点链接关系，并在上述存储结构图中进行相应修改：
胡洁
1
head
李丰
-1
张强
3
存储地址 数据区域 后继指针
1 “张强+1xx.” 3
3 “李丰+1xx.” -1
4 “胡洁+1xx.” 1
head
head
操作 数组 链表
访问
插入
删除
较高
与数组的操作做比较，各自的操作效率（选填：较高/较低）
较高
较高
较低
较低
较低
【学习任务二】链表基本操作
请同学们暂停视频，尝试并完成“学习任务单”上“【学习任务三】实践巩固——约瑟夫问题”。
【学习任务三】实践巩固——约瑟夫问题
n个人排成一圈，从某个人开始，按照顺时针方向从1开始依次编号。从编号为1的人开始顺时针“1，2，3，···，m，1，2，3，···，m”报数，报到m（m大于1）的人退出圈子。这样不断循环下去，圈子里的人数将不断减少。由于人数是有限的（n个），因此最终会只剩下一个人，试问最后剩下的人的初始编号是多少？
分析上述问题，按照如下步骤进行实践：
（1）抽象与建模
该问题中的关键数据是：
简述问题解决的计算模型：
所有人员的初始编号
① 形成1.2.3...n的循环序列
② 从编号1开始计数，每过1个编号计数值加1，当计数到m时将该编号从循环序列中移除；并从该编号循环后一编号从1开始重新计数。重复这个过程，直到循环序列中只剩下一个编号，该编号即为最后剩下人员的初始编号。
分析上述问题，按照如下步骤进行实践：
（2）设计链表与算法
链表设计：
链表中节点的数据区域保存
指针区域保存
【学习任务三】实践巩固——约瑟夫问题
初始编号
后继节点地址
单向循环链表
尾节点指针区域指向第一个节点
头指针指向编号1所在节点
（2）设计链表与算法
算法设计
【学习任务三】实践巩固——约瑟夫问题
①从第一个节点开始报数，每过1个节点报数值加1，将计到m的链表节点删除；继续从后继节点开始，重新从1报数。重复这个过程，直至链表中只剩下一个节点。
②此时头指针所指节点中的数据区域即保存了最终留下的初始编号。
存储地址 数据区域 后继指针
0 1
1 2
2 3
3 4
4 5
1
2
3
4
0
head
（3）模拟实现
①共5个人围成圈，创建由5个节点组成的单循环链表，完善如下存储结构。
【学习任务三】实践巩固——约瑟夫问题
②从链表第一个节点依次报数，每报到3的节点从链接关系中删除。并在上述结构中及时修改相关节点的指针。最后留在圈子内的初始编号： 。
存储地址 数据区域 后继指针
0 1 1
1 2 2
2 3 3
3 4 4
4 5 0
←报数值：1
←报数值：2
←报数值：3
3
←报数值：1
←报数值：2
←报数值：3
1
←报数值：1
←报数值：2
←报数值：3
1
←报数值：1
←报数值：2
←报数值：3
3
head
head
【学习任务三】实践巩固——约瑟夫问题
4
head
课堂小结
链表
概念
特性
基本操作
应用链表解决实际问题的一般步骤
第一节
课后作业
完成课后作业练习

展开更多......

收起↑