返回到本节首页
返回到本节首页
返回到本节首页
2．折半查找的算法 ．
所示。 （1）折半查找的算法如算法 ）折半查找的算法如算法7.3所示。 所示 算法7.3 算法 int BinSearch(LineList r[], int n, KeyType k) { int low,high,mid; low=1; high=n; /*置区间初值 置区间初值 */ while(low<=high) /*查找区间 查找区间 不为空时*/ 不为空时 { mid=(low+high)/2;
【例7.1】有关键字序列 ，4，6，9，10， 】有关键字序列{2， ， ， ， ， 13，15，27，29}，采用折半查找法查找 ， ， ， ， 6和17的具体过程。 的具体过程。 和 的具体过程 为低位指针， 为高位指针， 解：设low为低位指针，high为高位指针， 为低位指针 为高位指针 mid为中间位置指针。其中 为中间位置指针。 为中间位置指针 其中mid= ，若 mid所指元素大于关键字 时，这时令 所指元素大于关键字k时 所指元素大于关键字 high=mid-1，向mid前一半的表中继续 ， 前一半的表中继续 查找。 所指元素小于关键字k时 查找。若mid所指元素小于关键字 时，这 所指元素小于关键字 时令low=mid+1，向mid后一半的表中 时令 ， 后一半的表中 继续查找。 继续查找。当high<low时，表示不存在这 时 样的查找子表空间，查找失败。 样的查找子表空间，查找失败。
返回到本节首页
算法7.2 算法 int SeqSearch1(LineList r[],int n,KeyType k) { int i=n; r[0]=k; while(r[i].key!=k) /*若k不等于所比 若 不等于所比 较关键字时*/ 较关键字时 i--; return(i); }
返回到本节首页
顺序查找的线性表定义如下： 顺序查找的线性表定义如下： #define MaxSize 1000 大存储容量*/ 大存储容量 typedef int KeyType; 域为整型*/ 域为整型 typedef int ElemType; 类型为整型，可为其它类型*/ 类型为整型，可为其它类型 /*顺序表的最 顺序表的最 /*重定义关键字 重定义关键字 /*重定义数据域 重定义数据域
返回到本节首页
if(k==r[mid].key) return(mid); /*找到待查元素 找到待查元素 */ else if(k<r[mid].key) high=mid-1; /*未找到，继续 未找到， 未找到 在前半区间进行查找*/ 在前半区间进行查找 else low=mid+1; /*未找到，继续 未找到， 未找到 在后半区间进行查找*/ 在后半区间进行查找 } return (0); }
（a）以数组的下标作为二叉判定树结点的关键字（b）以序列中的值作为二叉判定树结点的关键字 以数组的下标作为二叉判定树结点的关键字（ 图7 - 4 9个结点的二叉判定树 9个结点的二叉判定树
返回到本节首页
7.2.3 分块查找
分块查找又称为索引顺序查找，是顺序查找的一种改 分块查找又称为索引顺序查找， 进，其性能介于顺序查找和折半查找之间。 其性能介于顺序查找和折半查找之间。 分块查找把查找表分成若干块， 分块查找把查找表分成若干块，每块中的元素存储顺 序是任意的，但块与块之间必须按关键字大小有序 序是任意的， 排列。即前一块中的最大关键字小于（或大于） 排列。即前一块中的最大关键字小于（或大于）后 一块中的最小（最大）关键字值。 一块中的最小（最大）关键字值。另外还需要建立 一个索引表，索引表中的一项对应线性表的一块， 一个索引表，索引表中的一项对应线性表的一块， 索引项由关键字域和指针域组成， 索引项由关键字域和指针域组成，关键字域存放相 应块的块内最大关键字，指针域存放指向本块第一 应块的块内最大关键字， 个和最后一个元素的指针（即数组下标值）。 ）。索引 个和最后一个元素的指针（即数组下标值）。索引 表按关键字值递增（或递减）顺序排列。 表按关键字值递增（或递减）顺序排列。
2．顺序查找的算法 ．
（2）顺序查找的改进算法 ） 我们可以使用监视哨来改进算法。 我们可以使用监视哨来改进算法。主要思路 顺序表中数据元素存放在数组下标为1 是：顺序表中数据元素存放在数组下标为 的位置， 到n的位置，而下标为 的位置空出来作为监 的位置 而下标为0的位置空出来作为监 视哨。在查找之前， 视哨。在查找之前，先将要查找的关键字存 放到数组下标为0的位置 的位置， 放到数组下标为 的位置，从顺序表的最后 一个记录开始， 一个记录开始，从后至前依次进行给定值与 记录关键字的比较， 记录关键字的比较，若某记录的关键字与给 定值k相同 则查找成功， 相同， 定值 相同，则查找成功，返回该记录在表 中的存储位置；若查找不成功，返回0。 中的存储位置；若查找不成功，返回 。相 应的算法如算法7.2。 应的算法如算法 。
2．顺序查找的算法 ．
（1）顺序查找的基本算法如下： ）顺序查找的基本算法如下： 算法7.1 算法 int SeqSearch(LineList r[],int n,KeyType k) { int i=1;/*为与其改进算法匹配，方便在主函数 为与其改进算法匹配， 为与其改进算法匹配 调用，查找表存储范围为下标1..n*/ 调用，查找表存储范围为下标 while(i<=n &&r[i].key!=k) i++; if(i>n) return(0); else return(i); } 返回到本节首页
7.2.2 折半查找
折半查找又称为二分查找。这种查找方法的前 折半查找又称为二分查找。 提条件是要求待查找的查找表必须是按关键 字大小有序排列的顺序表。 字大小有序排列的顺序表。 1．折半查找的主要步骤为： ．折半查找的主要步骤为： （1）置初始查找范围：low=1，high=n; ）置初始查找范围： ， （2）求查找范围中间项：mid= (low + high)/2 ）求查找范围中间项： （3）将指定的关键字值 与中间项的关键字比 ）将指定的关键字值k与中间项的关键字比 较： 若相等，查找成功， 若相等，查找成功，找到的数据元素为此时 mid 指向的位置； 指向的位置；
结束
2
3 4
5
7.1 基本概念
1．查找表 ． 用于查找的数据元素集合称为查找表。 用于查找的数据元素集合称为查找表。查找表 由同一类型的数据元素构成。 由同一类型的数据元素构成。 2．静态查找表 ． 在查找过程中查找表本身不发生变化， 在查找过程中查找表本身不发生变化，称为静 态查找表。对静态表的查找称为静态查找。 态查找表。对静态表的查找称为静态查找。 3．动态查找表 ． 若在查找过程中可以将查找表中不存在的数据 元素插入， 元素插入，或者从查找表中删除某个数据元 则称这类查找表为动态查找表。 素，则称这类查找表为动态查找表。对动态 查找表进行的查找称为动态查找。 查找表进行的查找称为动态查找。
返回到本节首页
7.2 静态查找
静态查找主要有顺序查找、折半查找、分块 静态查找主要有顺序查找、折半查找、 查找三种。 查找三种。 7.2.1顺序查找 顺序查找 7.2.2 折半查找 7.2.3 分块查找
返回到总目录
7.2.1顺序查找 顺序查找
1．顺序查找的主要思想 ． 顺序查找是一种最简单的查找方法， 顺序查找是一种最简单的查找方法，它的基本 思路是：从表的一端开始， 思路是：从表的一端开始，用所给定的关键 字依次与顺序表中各记录的关键字逐个比较， 字依次与顺序表中各记录的关键字逐个比较， 若找到相同的，查找成功；否则查找失败。 若找到相同的，查找成功；否则查找失败。
返回到本节首页
折半查找过程可用一个二叉树来描述，把当前 折半查找过程可用一个二叉树来描述， 查找区间的中间位置上的记录作为根， 查找区间的中间位置上的记录作为根，左子 表和右子表中的记录分别作根的左子树和右 子树。树中每个结点表示一个记录， 子树。树中每个结点表示一个记录，结点中 的值为该记录在表中的位置， 的值为该记录在表中的位置，则称该二叉树 为折半查找的判定树。例如例7.1关键字序 为折半查找的判定树。例如例7.1关键字序 列有9个 列有 个，关键字与数据下标的关系对应表 如图7-3所示。若用数组下标作为判定树中 所示。 如图 所示 结点的值，所对应的判定树如图7-4（a） 结点的值，所对应的判定树如图 （ ） 所示， 所示，若用查找表中的关键字作为判定树中 的结点的值，所对应的判定树如图7-4（b） 的结点的值，所对应的判定树如图 （ ） 所示。 所示。 返回到本节首页
数据结构实用教程（C语言版）
Байду номын сангаас
中国水利水电出版社
第7章 查找
本章主要介绍以下内容： 本章主要介绍以下内容： 静态查找方法，主要介绍顺序查找、折半查找和 静态查找方法，主要介绍顺序查找、 分块查找 动态查找方法， 动态查找方法，主要介绍二叉排序树查找 哈希表查找
本章目录
1
7.1 基本概念 7.2 静态查找 7.3 二叉排序树查找 7.4 哈希表查找 7.5 小结
返回到本节首页
小于中间项关键字， 若k小于中间项关键字，查找范围的低端数 小于中间项关键字 据元素指针low不变，高端数据元素指针 不变， 据元素指针 不变 high更新为 更新为mid-1; 更新为 大于中间项关键字， 若k大于中间项关键字，查找范围的高端数 大于中间项关键字 据元素指针high不变，低端数据元素指针 不变， 据元素指针 不变 low更新为 更新为mid+1; 更新为 ）、（3） （4）重复步骤（2）、（ ）直到查找成功或 ）重复步骤（ ）、（ 查找范围为空（ ），即查找失败 查找范围为空（low>high），即查找失败 ）， 为止。 为止。 （5）如果查找成功，返回找到元素的存放位 ）如果查找成功， 即当前的中间项位置指针mid；否则返 置，即当前的中间项位置指针 ； 返回到本节首页 回查找失败标志。 回查找失败标志。