浙教版 (2019)选修1 数据与数据结构2.2 链表优秀导学案

这是一份浙教版 (2019)选修1 数据与数据结构2.2 链表优秀导学案，共4页。学案主要包含了学习任务一，学习任务二，学习任务三等内容，欢迎下载使用。

课程基本信息
学科
信息技术
年级
高三
学期
秋季
课题
2.2.1 链表的概念、特性及其基本操作
学习目标
1. 理解链表的概念和特性。
2. 掌握链表的基本操作。
课前学习任务
1. 复习教材中数组的概念、特性及其基本操作。
2. 结合数组的特性和基本操作，针对如下例子设计数组以组织和存储关键数据：
① 处理全班同学的信息，时常需要进行信息访问；
② 处理学校外来人员信息，进校时登记信息，出校时移除信息。
课上学习任务
【学习任务一】认识链表
为了满足链表能在两个方向都能进行遍历的需求，请在图1为每个节点补充正确的前驱指针。
存储地址
数据区域
前驱指针
后继指针
0
“黄刚”
1
1
“李丰”
-1
head
2
“王林”
0
3
“吴坚”
-1
2
图1 双向链表存储结构图
【学习任务二】链表基本操作
存储地址
数据区域
后继指针
head
0
“杜刚+1xx.”
2
1
“张强+1xx.”
3
2
“李彤+1xx.”
-1
3
“李丰+1xx.”
0
（1）“杜刚”出校，在下图修改节点指针链接，并在上述存储结构图中进行相应修改：
（2）“胡洁”在“张强”之前入校，在下图修改节点指针链接，并在上述存储结构图中进行相应修改：
（3）“李彤”出校，在下图修改节点指针链接，并在上述存储结构图中进行相应修改：
（4）“胡洁”出校，在下图修改节点指针链接，并在上述存储结构图中进行相应修改：
【小结】与数组的操作做比较，各自的操作效率（选填：较高/较低）
操作
数组
链表
访问
插入
删除
【学习任务三】实践巩固——约瑟夫问题
n个人排成一圈，从某个人开始，按照顺时针方向从1开始依次编号。从编号为1的人开始顺时针“1，2，3，···，m，1，2，3，···，m”报数，报到m（m大于1）的人退出圈子。这样不断循环下去，圈子里的人数将不断减少。由于人数是有限的（n个），因此最终会只剩下一个人，试问最后剩下的人的初始编号是多少？
分析上述问题，按照如下步骤进行实践：（在完成本任务时，可以在推荐学习资源处查阅相关知识）
（1）抽象与建模
该问题中的关键数据是： 。
简述问题解决的计算模型：
（2）设计链表与算法
链表设计：
链表中节点的数据区域保存 ，指针区域保存 。
算法设计
（3）模拟实现
① 共5个人围成圈，创建由5个节点组成的单循环链表，完善如下存储结构。
head
节点地址
数据区域
后继指针
0
1
1
2
2
3
3
4
4
5
② 从链表第一个节点开始顺时针循环报数，每报到3的节点从链接关系中删除。并在上述结构中及时修改相关节点的指针。最后留在圈子内的初始编号： 。