链表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=不太理想)
大数据处理PPT课件免费下载: 浙教版(2019)高中信息技术必修1数据与计算课文《大数据处理》,完整版PPT课件免费下载,优秀PPT背景图搭配,精美的免费ppt模板。轻松备课,欢迎免费下载使用。
数据排序PPT课件免费下载: 浙教版(2019)高中信息技术选修1数据与数据结构课文《数据排序》,完整版PPT课件免费下载,优秀PPT背景图搭配,精美的免费ppt模板。轻松备课,欢迎免费下载使用。
数组PPT课件免费下载: 浙教版(2019)高中信息技术选修1数据与数据结构课文《数组》,完整版PPT课件免费下载,优秀PPT背景图搭配,精美的免费ppt模板。轻松备课,欢迎免费下载使用。