线上课前学习

（课前）

线下课堂教学

（课中）

教学活动

教学方法

设计意图

提问：如何设计一套加密编码用于日常生活中的交流？

例：H公司有两个骨干员工，下班后也需要经常交流工作上的事情，两位员工都很谨慎，他俩根据聊天中常见字符的频率，编制了一套加密编码，在聊天过程中，对于一些关键信息，会用自己设计的编码加密后再发送给对方。

问题导向

通过导入问题，留下悬念，引发学生对编码的兴趣，同时引导学生要遵守职业道德和规范，保守企业机密；并进一步引导学生要爱自己的国家，保守国家秘密，维护国家安全，人人有责。

介绍哈夫曼的生平事迹、哈夫曼算法产生的背景，让学生意识到创新可以出现在老师布置的期末大作业中，创新也可以出现在我们的日常生活中。

创设情境

通过了解哈夫曼的一些生平事迹，引导学生发现生活处处有创新，创新无处不在；要养成多动脑，勤思考的习惯，以激发自身的创新意识；同时，还需丰富知识储备，提升自身的创新能力。

哈夫曼树的应用：约翰修篱笆的最少费用方案。

哈夫曼树的构造过程可以看成是木头的拼接过程，而木头的切割方案则可以看成是木头拼接过程的逆过程，所以可以利用哈夫曼树的构造过程来描述切割木条的方案。

案例分析

引导学生要打破常规，从逆向思维的角度分析问题、解决问题。同时引导学生解决问题要寻求最佳方案，以最小大代价达到最大的效益。

利用超星学习通发布分组任务：从代码实现的角度，详细描述约翰修篱笆问题的算法实现思路。通过生讲生评的方式，增强学生之间的互动，帮助提升学生的自信心和表达能力。

约翰修篱笆问题的算法实现思路，可以用数组也可以用链表作为存储结构，还可以利用堆来改进算法的效率。

分组研讨

培养学生的团队意识，加强小组成员的沟通交流，群策群力，提出解决问题的多种思路，从中找寻解决问题的最佳方案。引导学生算法设计时要追求更高效率，要有精益求精、追求卓越的工匠精神。

对课前布置的成绩评定讨论题进行分析。

在软件开发中，经常会遇到解决大量判定问题的时候，在解决这类问题的时候，习惯做法是按照判定条件的连贯性自上而下逐个判断，而实际上大量的判定问题普遍存在满足中间条件多、两头条件少的现象。引导学生在哈夫曼树的构造过程中增加约束条件，通过建立最佳判定树得到比较次数最小的成绩评定方案，这也意味着站在用户的角度，响应时间会更短，会给用户带来更好的体验。

问题探究

鼓励学生勇于创新、大胆尝试，创新就在我们身边。引导学生把哈夫曼树的构造过程通过增加约束条件创新应用到成绩评定的比较环节。并再次对学生强调编写程序要养成注重细节，追求更高效率的良好习惯，以加强学生工匠精神的培养。

课后实践与拓展

（课后）

1.       课后拓展：数据结构中有很多算法因为其独特的创新思路，故而以算法提出者的名字命名。通过查阅资料，谈谈你所知道的一些以人名命名的算法，简单介绍一下算法产生的背景及功能。

2.       课后任务：编程实现约翰修篱笆问题的切割方案，需给出算法思路分析、代码及执行结果截图。

线上课前学习

（课前）

1.阅读教材3.5节，观看视频3.7.1～3.7.3。

知识点：队列的特点，循环队列，链队列。

2.完成练习6 队列。

3.完成讨论：简述队列、栈、线性表三者之间的关联和区别。并列举出你在生活中发现的“栈”、“队列”和“线性表”。

线下课堂教学

（课中）

教学活动

教学方法

设计意图

通过引入日常生活中的排队现象：食堂打饭、超市购物结账、进火车站、核酸检测等，引出队列的基本概念，通过观察现实生活中的排队现象，了解队列“先进先出”的特点及队列的作用。

在讲解队列的过程中，让学生意识到秩序的重要性，课堂上要遵守课堂秩序才能保证教学的有序进行，企业员工要遵守企业的规章制度才能保证生产的正常进行，行人、车辆只有遵守交通法规才能保证交通有序、安全地运行。

创设情境

引导学生意识到排队制度使公共场所有了秩序，使得各项工作能高效地运行，进一步引申学校和企业的规章制度，让大家的学习和工作能安定有序地进行，国家制定的各种法律法规，能让人们的生活有安全保障。

引导学生既要尊重社会公德，遵守公共秩序，同时也要遵守学校规章制度，遵守交通规则，遵守国家法律法规。

针对基础和重点知识，进行随机抽查、随堂检测，讲解课前布置作业；收集问题，答疑解惑。

对课前布置的讨论题进行分析，总结线性表、栈和队列三种结构的异同点，栈和队列可以看作操作受限制的线性表。

问题探究

检查学生线上自学情况，查漏补缺。 引导学生辩证看待线性表、栈和队列三者之间的关系，线性表的优点在于插入和删除位置不受限制，而栈和队列的优点在于可以高效模拟实际应用中的类似场景。

国际足联世界杯小组赛出线规则如下：32支参赛队通过抽签分为八个小组，每个小组分别有四只球队进行比赛，每支球队都必须和其他三支球队进行且只进行一场比赛，已知2022年卡塔尔世界杯32强分组名单如下，请利用队列的基本操作，编写算法，打印各组内的循环比赛对战名单。

指导学生利用队列的出队、入队、判队空、遍历等操作，解决上述问题。

算法实现思路：将小组内的球队依次入队，只要队列不为空，队头元素出队，再遍历队列中的元素，直到队列为空为止。

分组讨论

指导学利用队列解决实际问题的同时，讲解卡塔尔世界杯上出现的中国元素，从体育场馆建设到电力保障，从赛场内体育用品和企业品牌到赛场外的保障设施等等，中国制造、中国建造、中国品牌，为世界杯提供了强有力的支持。体现出中国经济强大的竞争力、影响力。增强学生对中华民族的认同感、自豪感，培养学生的家国情怀。

情境导入：在排队等待红绿灯时，正在执行任务的救护车和消防车拥有优先通过的权利。

通过跟学生讲解《道路交通安全法》第53条引出优先队列的概念。优先队列中的元素被赋予了优先级，优先级最高的元素最先删除，优先队列具有“优先级最高先出”的特征。

优先队列的算法实现，可以用排序、查找、直接插入等操作，也可以用堆提高算法的性能。

创设情境

讲解优先队列思想的同时，引导学生，遇到正在执行任务的消防车和救护车时，要主动避让，为生命让道。进一步引导学生处理任何问题必须遵循必要的规矩，但是面对具体问题和工作中的复杂性，又要敢于打破常规，勇于创新，守规矩但不墨守陈规。

课后实践与拓展

（课后）

课后任务：约瑟夫环（约瑟夫问题）是一个数学的应用问题，已知 n 个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出圈；他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。请利用所学的数据结构（如：顺序表、链表、队列等）解决约瑟夫问题，尽可提供多种解决方案，给出算法设计思路，算法效率分析、代码及运行结果截图。

2.课后讨论：