高中信息技术浙教版 (2019)选修1 数据与数据结构2.2 链表课文配套ppt课件

这是一份高中信息技术浙教版 (2019)选修1 数据与数据结构2.2 链表课文配套ppt课件，共12页。PPT课件主要包含了讲一个故事，问题分析，抽象与建模，设计数据结构与算法，编程实现，效率测试，课堂小结，学习评价等内容，欢迎下载使用。

在罗马人占领乔塔帕特后，39个犹太人与Jsephus及他的朋友躲到一个洞中，39个犹太人决定宁死也不要被敌人抓到，于是决定了一个自杀方式：41个人排成一个圆圈，由第1个人开始报数，每报数到第3人，该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。Jsephus要他的朋友先假装遵从，他将朋友与自己安排在第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结果是否为前一个数。组内数据对标：组内成员选择几组数据进行对标，查看是否一致。
程序效率对比自学“pythn time包”学习材料，使用time.clck（）对程序运行时间进行计时。小组成员分别记录程序在不同数据规模下的运行时间，分析数据结构与算法设计对程序运行效率的影响。
①链表的基本概念与特性②链表节点的访问与遍历
对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）