成都东软信息技术学院教案.doc

成都东软信息技术学院教案 学院部门： 计算机系 任课教师： 编号：_______________ 周 次 第 7 章， 第 1 次课 年月 日 章 节 名 称 第7章 查找 授 课 方 式 课堂讲授（2）；实践课（0） 教　学 时　数 2 时间分配 授 课 要 点 查找的相关概念（20分钟） 查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素 关键码——是数据元素中某个数据项的值，它可以标识一个数据元素 查找表—— 具有同一类型（属性）的数据元素（记录）组成的集合。 静态查找表 动态查找表 查找方法评价ASL 二、 静态查找表的结构定义（15分钟） typedef struct { KeyType key； …… }ElemType typedef struct { ElemType *elem； /* 数组基址 */ int length； /* 表长度 */ }S_TBL； 三、 顺序查找（15分钟） 1、查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。 2、算法描述 3、顺序查找的ASL计算 四、 折半查找（40分钟） 1、查找过程：每次将待查记录所在区间缩小一半 2、适用条件：采用顺序存储结构的有序表 3、算法实现 4、折半查找的ASL计算 教 学 重 点 与 难 点 重点 1、顺序查找的算法 2、折半查找的思想和算法 难点： 静态查找表的结构定义 ASL的计算 课 堂 讨 论 与 练 习 讨论 为什么静态查找表的第0号单元不存放元素？ 折半查找的局限性 练习： 参 考 资 料 《数据结构（C语言版）》，严蔚敏、吴伟民著，清华大学出版社 《计算机程序设计技巧1.基本算法》，（美）唐.欧.克努特著，国防大学出版社 《计算机程序设计技巧3.排序查找》，（美）唐.欧.克努特著，国防大学出版社 作业布置情况 1、定义一静态查找表，通过顺序查找的算法显示元素所在的位置。 2、定义一静态查找表，通过折半查找的算法显示元素所在的位置。 3、习题7，7.2 备注