数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源12静态查找

8.2静态查找,静态查找是指在静态查找表上进行的查找操作，查找满足条件的数据元素的存储位置或各种属性。,顺序查找 折半查找 分块检索,一、顺序查找 基本思想 查找表的存储结构是线性表（顺序表或链表） 查找过程是依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较 若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。,顺序表的类型定义 #define MAX_NUM 100 /用于定义表的长度 typedef struct elemtype keytype key; RecordTypeMaxSize； 数据元素个数为n(nMAX_NUM) 分别存放在数组的下标变量a1an中,下面我们给出顺序查找的完整算法 int SeqSearch(RecordType r, int n, KeyType k) /*返回关键字值等于k的数据元素在表r中的位置，n为表中元素的个数*/ i=n； r0.key=k； /*监视哨*/ while (ri. key!=k) i-； if (i0) return （i）； /*查找成功*/ else return （-1）； /*查找失败*/ /* SeqSearch */,二、折半查找 折半查找只适用于对有序顺序表进行查找。 折半查找的基本思想是 每进行一次折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如此重复 直到查找成功或查找范围缩小为空即查找失败为止。,例如，假设给定有序表中关键字为（3，6，12，23，30，43，56，64，78，85，98） ，查找23,图8.1 折半查找初始示意图,图8.2 折半查找中low、mid、high的变动情况,折半查找算法描述如下： int BinSearch(RecordType r, int n, KeyType k) /*在有序表r中折半查找关键字值等于k的数据元素*/ int low,high,mid; low=1；high=n； /置初始查找范围的低、高端指针 while (low=high) mid=(low+high)/2； /*取表的中间位置*/ if (k=rmid.key) return （mid）； /*查找成功*/ else if (krmid.key) high=mid-1； /*在左子表中查找*/ else low=mid+1； /*在右子表中查找*/ return （-1）； /*查找失败*/ /* BinSearch */,小结 二分查找算法平均查找长度为 log2n，比较次数少，查找速度快。 只能应用于有序的顺序表。 二分查找适用于那种一经建立就很少改动，而又经常需要查找的顺序表。,分块检索,分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。 1、 查找表存储结构 查找表由“分块有序”的线性表和“有序的”索引表组成,（1）“分块有序”的线性表 线性表R被均分为若干块，每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是“分块有序“的。 （2） “有序的”索引表 抽取各块中的最大关键字及其起始位置和长度构成一个索引表ID中，即：,2、分块查找的基本思想 （1）首先查找索引表 索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。 （2）然后在已确定的块中进行顺序查找,索引表中的数据元素由两个域构成，key域为被索引的若干个数据元素中关键字的最大值，link域为被索引的若干个数据元素中第一个数据元素的位置编号。,索引表结构图,小结,