2.2.2 链表的应用 课件（12张PPT）

(共12张PPT)
选择性必修1《数据与数据结构》
第二章 数组与链表
2.2.2 链表的应用：《约瑟夫问题》
讲一个故事
在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁死也不要被敌人抓到，于是决定了一个自杀方式：41个人排成一个圆圈，由第1个人开始报数，每报数到第3人，该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16与第31号位置，于是逃过了这场死亡游戏。
问题分析
如图所示，内层为作为编号，外层为自杀序号。
抽象与建模
该问题中的关键数据是n个参与人员的初始编号，1至n的序列。从编号1开始计数，每过一个编号加1，当计数到m时将该编号从数据序列中移除，并从该编号的后一编号从 1开始重新计数。而当计数到序列中最后一个编号，又从序列的开始编号继续计数，从而 将计数序列构成一个环。重复这个过程，直到序列中只剩一个编号，该编号即为最后剩下 人员的初始编号。
设计数据结构与算法
链表实现：
①创建一个由n个结点组成的单向循环链表，并使报数计数器i的初始化值为1，同时当前报数人的指针k指向链表中第一个结点。
②重复执行下列处理，直到链表中只剩下一个结点随着报数的进行，不断指向下一个结点，报数计数器i也随之增加，当i增加到淘汰数m时，将对应的链表结点删除，若删除的结点为头结点，则需同时修改头指针的指向；在删除结点的同时，需要重置报数计数器i的值为1。
③将链表中唯一结点，也就是头指针指向的结点中的数据（即初始编号）输出。
设计数据结构与算法
数组实现：
①创建一个数组含n个数组元素组成，使报数计数器i的初始化值为1，同时当前报数人的指针k指向数组中第一个元素。
②重复执行下列处理，直到数组中只剩下一个数组元素。随着报数的进行，不断指向下一个数据元素，报数计数器i，k（k=k%剩余人数+1）也随之增加，当i增加到淘汰数m时，将K之后的所有数组元素向前移动一位，k位置元素被覆盖删除；在k元素被删除的同时，需要重置报数计数器i的值为0，k的设为K-1。
③将数组中唯一数组元素，也就是K指向的数组元素（即初始编号）输出。
设计数据结构与算法
列表版实现：
①创建一个列表含n列表元素，使报数计数器i的初始化值为1，同时当前报数人的指针k指向链表中第一个列表元素。
②重复执行下列处理，直到列表中只剩下一个列表元素。随着报数的进行，不断指向下一个列表元素，报数计数器i，k（k=k%剩余人数+1）也随之增加，当i增加到淘汰数m时，直接删除K元素；在k元素被删除的同时，需要重置报数计数器i的值为0，k设为K-1。
③将列表中唯一列表元素，也就是K指向的列表元素（即初始编号）输出
编程实现
代码实现
组内2到3人可以围绕“链表”数据结构展开编程设计，程序实现能力较强的成员在“链表”外另选一种数据结构进行拓展学习。
调试运行
测试项目问题背景数据41,3 输出是否为31。
测试边界值18,1；99,1；999,1结果是否为前一个数。
组内数据对标：组内成员选择几组数据进行对标，查看是否一致。
效率测试
程序效率对比
自学“python time包”学习材料，使用time.clock（）对程序运行时间进行计时。
小组成员分别记录程序在不同数据规模下的运行时间，分析数据结构与算法设计对程序运行效率的影响。
课堂小结
①链表的基本概念与特性
②链表节点的访问与遍历
学习评价
对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）
评分项 自我评价 同学互评
掌握链表的基本操作 5 4 3 2 1 5 4 3 2 1
能合理利用链表编程实现约瑟夫问题 5 4 3 2 1 5 4 3 2 1
能使用time模块测试程序执行效率 5 4 3 2 1 5 4 3 2 1
课堂作业
思考与练习
1. 数组与链表作为存储相同类型数据的两种数据结构，拥有各自的应用场景、组织结构和操作特性，请根据教学内容进行简要概括并完善以下表格：
数组 链表
应用场景 适合数据规模确定且在处理过程中保持数据规模稳定的问题
组织结构 由结点构成，每个结点中包含数据区域和指针区域，相邻结点间通过指针链接
操作特性 优点：数据访问效率较高 缺点：使用前需限定最大空间，容易造成空间资源的浪费
②参考教材中单向链表的列表实现，请思考如何使用列表实现双向链表的结构及其基本操作，思考完善后编程实现双向链表节点的创建、增加、删除及显示等。