(
课件网) 选择性必修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 ... ...
