线性表的查找技术教案

线性表的查找技术线性表的查找技术 教学目标 教学目标 理解顺序查找和二分查找的基本思想 教学重点教学重点 顺序查找和折半查找的思想 算法 教学难点教学难点 折半查找的思想和算法 授课方法授课方法 讲授 示例 教学安排教学安排 1 课时 教学手段教学手段 板书 课件 教学过程教学过程 教学教学 环节环节 教教 学学 内内 容容 教师教师 活动活动 学生活学生活 动动 导入 新课 日常生活举例引入查找的概念 导入学生思 考 查找的 基本概 念 顺序查 找 顺序表 查找的基本概念查找的基本概念 查找是在具有相同类型的记录构成的集合中找出 满足给定条件的记录 为了便于讨论 把查找条件限制为 匹配 即查找关键码等于给定 值的记录 查找分为静态查找和动态查找 静态查找通常采用顺序查找和折半查找 在线性表中进行的查找通常属于静态查找 一 顺序查找一 顺序查找 顺序查找 又称线性查找 主要用在线性结构中进行查找 若表中有 n 个对象 则顺序查找从表的一端开始 用各对象的关键码 与给定值 k 进行比较 直到找到与其值相等的对象 则查找成功 给 出该对象在表中的位置 若整个表都已检测完仍未找到关键码与 k 相等的对象 则查找失败 给出失败信息 1 1 顺序表按值查找 顺序表按值查找 讲述思考 按值查 找 顺序表 的顺序 查找 演示 顺序查 找算法 二分查 找 二分查 找的步 骤 int serch int r int n int k int i for i 0 i n i if r i k return i 1 下标为 i 的元素等于 x 返回其序号 i 1 return 0 退出循环 说明查找失败 2 2 顺序表的顺序查找 演示 顺序表的顺序查找 演示 0 1 2 3 4 5 6 7 8 9 K10152461235409855 哨兵i 查找方向 3 3 顺序查找算法 顺序查找算法 int SeqSearch1 int r int n int k r 0 k i n while r i k i return i 二 二分查找 折半查找 二 二分查找 折半查找 现在有 50 个小圆球 其大小 颜色等完全相同 其中有一个小球比 其它 49 个小球重 5 克 现给你一天平 无具体刻度 要求将该小于 找出来 我们应该怎么办 有序表 有序表 以递增 或递减 顺序排列的表 基本思想 基本思想 给定值 k 与中间位置的记录的关键字比较 若相等则查找 成功 若给定值大于中间位置记录的关键字值 则在表的后半部分继 续二分查找 否则在表的前半部分进行二分查找 直至查找成功或不 成功 1 1 二分查找的步骤 二分查找的步骤 1 计算中间位置 mid low high 2 取整 2 k 与 R mid 比较 展示 课件 提出 一个 问题 思考并 理解 思考解 决这个 问题的 方法 二分查 找的示 例 若 k R mid 则查找成功 若 kR mid 则 low mid 1 转 3 3 若 low high 则重复 1 否则 查找不成功 结束 2 2 二分查找的示例 二分查找的示例 1 1 用二分查找法在顺序表中查找关键字为 用二分查找法在顺序表中查找关键字为 8080 的纪录 的纪录 第 1 步 1826324552668091 lowmidhigh 第 2 步 lowmidhigh 第 3 步 8091 lowhigh mid 查找成功 2 2 查找关键字为 查找关键字为 1010 的纪录 的纪录 第 1 步 1826324552668091 第 2 步 1826324552668091 mid 第 3 步 1826324552668091 第 4 步 1826324552668091 52668091 解释 查找 的过 程 跟着查 找过程 一步一 步思考 lowmidhigh lowhigh lowhigh mid 二分查 找算法 总结 此时 high 1 low 0 high low 所以查找失败 不存在该数据 3 3 二分查找算法 二分查找算法 int binsearch elemtype r int n int key int low high mid low 0 high n 1 while low r mid key low mid 1 else high mid 1 return 1 作业布置作业布置 给定 11 个数据元素的有序表 2 3 10 15 25 28 29 30 35 40 采用折半查找 试问 若查找给定值为 20 的元素 将依次与表中哪些元素比较 前面一节课我们学习了顺序查找 如果查找的数据较多或频繁进行查 找 顺序查找效率会比较低 而使用二分法查找则可以提高查找的效 率