2.2.2 链表的应用 课件-2021-2022学年高中信息技术浙教版（2019）选修1 数据 与数据结构

选择性必修1《数据与数据结构》 第二章 数组与链表 2.2.2 链表的应用：《约瑟夫问题》 1 讲一个故事 在罗马人占领乔塔帕特后，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，同