《数据结构》课程教学资源（教案设计）10 静态查找

编号：011 课程 章节 第七章查找 课程讲 数据结构 7.1概述 45分钟 名称 名称 7.2静态查找表 授学时 学习要求 知识点 识记理解 熟练 分析 应用 课堂 掌握 综合 查找表的基本概念 顺序表的查找 目的 有序表的杳找 √ √ 态度 积极主动学习 能力>查找的基本概念，各种直找技术的实现及分析 教学内容（教学过程设计） 教学安排 提出问题：(1)在日常生活中，人们几乎每天都要进行“查找”工作 5分钟 如在电话号码簿中查找“某人”的电话号码：在字典中查找“某个词 的含义等到。这里的"电话号码簿”和“字典”都可视为一张查找表 (2)在各种系统软件和应用软件中，查找表也是一种常见的结构之 如编译程序中符号表、信息处理系统中信息表等。 提出问题：查找表的应用范围如何？ 如何存储查战表？ 如何实现常见的对查找一的操作？ 20分钟 学生回答后，总结并导入新课 7.1概述 给出查找的定义，说明查找所基于的数据结构是集合 结合实例，给出关键码的有关概念 给出静态查找和动态查找的概念，说明适用情况 教学提示： 静态查找和动态查找是本章的两条主线，因此，本讲要使学生深刻理解 20分钟 这两个概念 从逻辑上说，查找所基于的数据结构是集合，即查找集合中的记录之间

编号：011 课程 名称 数据结构 章节 名称 第七章 查找 7.1 概述 7.2 静态查找表 课程讲 授学时 45 分钟 课堂 教学 目的 知 识 点 学 习 要 求 识记 理解 熟练 掌握 应用 分析 综合 查找表的基本概念 √ √ 顺序表的查找 √ √ √ √ √ 有序表的查找 √ √ √ √ √ 态度 积极主动学习 能力 ➢ 查找的基本概念，各种查找技术的实现及分析。 教学内容（教学过程设计） 教学安排 提出问题：（1）在日常生活中，人们几乎每天都要进行“查找”工作， 如在电话号码簿中查找“某人”的电话号码；在字典中查找“某个词” 的含义等到。这里的“电话号码簿”和“字典”都可视为一张查找表。 （2）在各种系统软件和应用软件中，查找表也是一种常见的结构之一， 如编译程序中符号表、信息处理系统中信息表等。 ↓ 提出问题：查找表的应用范围如何？ 如何存储查找表？ 如何实现常见的对查找一的操作？ ↓ 学生回答后，总结并导入新课 ↓ 7.1 概述 ↓ 给出查找的定义，说明查找所基于的数据结构是集合 ↓ 结合实例，给出关键码的有关概念 ↓ 给出静态查找和动态查找的概念，说明适用情况 教学提示： ➢ 静态查找和动态查找是本章的两条主线，因此，本讲要使学生深刻理解 这两个概念 ➢ 从逻辑上说，查找所基于的数据结构是集合，即查找集合中的记录之间 5 分钟 20 分钟 20 分钟

没有关系，但是为了获得较高的查找性能，存储时可以将查找集合组织 成表、树等查找结构 7.2静态查找表 给出静态查找表的抽象数据类型定义 设置哨兵，运行实例，分别考察在查找成功和直找不成功的情况下哨兵 所起的作用 写出改进的顺序查找算法，并与改进前的算法进行比较 分析顺序查找技术的优缺点、活用情况 给出折半查找的基本思想，运行实例，写出折半查找的非递归算法 给出折半查找判定树的定义及构造方法，分析查找成功和查找不成功情 况下的查找性能 教学提示： 对改进的顺序查找，注意引出“哨兵”的方式，引申“哨兵”的作用， 引导学生掌握这种程序设计的技巧 对于折半查找，不要急于给出算法，在运行实例提出并解决关键问题的 基础上，引导学生自己写出算法，从而深刻领会折半查找技术 重点： （1)顺序表的查找： 重点 (2)有序表的查找。 与 难点 难点 折半查找的过程及性能分析。 对策 教学策略： 在授课过程中采用多煤体教学，首先还原问题的本来面目一提出问题，引导学生 积极参与 一尝试解决问题，在讨论的基础上给出结论 —讲授教学内容、解法 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 教学 教学方法：导入，配合图形、实例讲解，提问、讨论 方法 教学手段：PPT课件，板书，动画演示 与 手段 作业 作业： 及 课外 (1)假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95 进行折半查找，试回答下列问题：

没有关系，但是为了获得较高的查找性能，存储时可以将查找集合组织 成表、树等查找结构 ↓ 7.2 静态查找表 ↓ 给出静态查找表的抽象数据类型定义 设置哨兵，运行实例，分别考察在查找成功和查找不成功的情况下哨兵 所起的作用 写出改进的顺序查找算法，并与改进前的算法进行比较 分析顺序查找技术的优缺点、适用情况 ↓ 给出折半查找的基本思想，运行实例，写出折半查找的非递归算法 给出折半查找判定树的定义及构造方法，分析查找成功和查找不成功情 况下的查找性能 教学提示： ➢ 对改进的顺序查找，注意引出“哨兵”的方式，引申“哨兵”的作用， 引导学生掌握这种程序设计的技巧 ➢ 对于折半查找，不要急于给出算法，在运行实例提出并解决关键问题的 基础上，引导学生自己写出算法，从而深刻领会折半查找技术 重点 与 难点 对策 重点： （1）顺序表的查找； （2）有序表的查找。 难点： 折半查找的过程及性能分析。 教学策略： 在授课过程中采用多媒体教学，首先还原问题的本来面目——提出问题，引导学生 积极参与——尝试解决问题，在讨论的基础上给出结论——讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 教学 方法 与 手段 教学方法：导入，配合图形、实例讲解，提问、讨论 教学手段：PPT 课件，板书，动画演示 作业 及 课外 推荐 资源 作业： （1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95） 进行折半查找，试回答下列问题：

①画出描述折半查找过程的判定树 ②若直找元素54，需依次与哪些元素比较？ ③若查找元素90，需依次与哪些元素比较？ ④假定每个元素的查找概率相等，求查找成功时的平均查找长度。课后导读： 查找的同义词是检索，在不严格区分的情况下，二者的含义相同。请参见 《数据结构与算法》（许卓群清华大学出版社）中对检索的定义。 关于折半查找判定树性质的证明，以及斐波那契查找的具体算法请参见 《数据结构与算法》（文德寻清华大学出版汁） 如果查找集合中各记录的查找概率不等，则最优二叉树能保证查找效率 具体内容参见《算法设计与分析》（王红梅清华大学出版社） 教学 后记

① 画出描述折半查找过程的判定树； ② 若查找元素 54，需依次与哪些元素比较？ ③ 若查找元素 90，需依次与哪些元素比较？ ④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。课后导读： ➢ 查找的同义词是检索，在不严格区分的情况下，二者的含义相同。请参见 《数据结构与算法》（许卓群 清华大学出版社）中对检索的定义。 ➢ 关于折半查找判定树性质的证明，以及斐波那契查找的具体算法请参见 《数据结构与算法》（齐德昱 清华大学出版社） ➢ 如果查找集合中各记录的查找概率不等，则最优二叉树能保证查找效率。 具体内容参见《算法设计与分析》（王红梅 清华大学出版社） 教 学 后记