2.2 链表-学习任务单

学习任务单 课程基本信息 学科 信息技术 年级 高三 学期 秋季 课题 2.2.1 链表的概念、特性及其基本操作 学习目标 1. 理解链表的概念和特性。 2. 掌握链表的基本操作。 课前学习任务 1. 复习教材中数组的概念、特性及其基本操作。 2. 结合数组的特性和基本操作，针对如下例子设计数组以组织和存储关键数据： ① 处理全班同学的信息，时常需要进行信息访问； ② 处理学校外来人员信息，进校时登记信息，出校时移除信息。 课上学习任务 【学习任务一】认识链表 为了满足链表能在两个方向都能进行遍历的需求，请在图1为每个节点补充正确的前驱指针。 存储地址数据区域前驱指针后继指针0“黄刚”11“李丰”-12“王林”03“吴坚”-12 图1 双向链表存储结构图 【学习任务二】链表基本操作 存储地址数据区域后继指针0“杜刚+1xx.”21“张强+1xx.”32“李彤+1xx.”-13“李丰+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个节点组成的单循环链表，完善如下存储结构。 节点地址数据区域后继指针0112233445 ② 从链表第一个节点开始顺时针循环报数，每报到3的节点从链接关系中删除。并在上述结构中及时修改相关节点的指针。最后留在圈子内的初始编号： 。