《数据结构 C语言版 第2版 教学课件 ppt 李云清 杨庆红 揭安全 第9章_检索》由会员分享，可在线阅读，更多相关《数据结构 C语言版 第2版 教学课件 ppt 李云清 杨庆红 揭安全 第9章_检索（163页珍藏版）》请在金锄头文库上搜索。
1、数据结构,李云清 杨庆红 揭安全,高等学校精品课程,人民邮电出版社,（第2版）,数据结构,揭安全,江西省高等学校精品课程,E_mail: ,江西师范大学计算机信息工程学院,第9章 检索,检索的基本概念,线性表的检索,最佳二叉排序树,散列表检索,二叉排序树,B-树,丰满树和平衡树,Huffman树,9.1 检索的基本概念,检索是确定数据元素集合中是否存在数据元素等于特定元素或是否存在元素满足某种给定特征的过程。,要进行检索，必须知道待检索对象的特征，也就是要知道待检索数据元素的关键字。,我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字。,静态检索表：检索的前
2、后不会改变查找表的内容。,动态检索表：检索过程中可能会改变数据元素的存储位置。,检索算法的评价标准：平均查找长度ASL（Average Search Length），也就是为确定某一结点在数据集合中的位置，给定值与集合中的结点关键字所需进行的比较次数。,对于具有n个数据元素的集合，查找某元素成功的平均查找长度为：,ASL,9.2 线性表的检索,线性结构是数据元素间最常见的数据结构，基于线性表的检索运算在各类程序中应用非常广泛，本节介绍三种在线性表上进行检索的方法，它们分别是顺序检索、二分法检索与分块检索。为简化问题，本节所介绍的检索方法均视为是基于静态查找表上的操作。,9.2.1顺序检索,从表
3、的一端开始，顺序（逐个）扫描线性表，依次将扫描到的结点关键字和给定值Key相比较，若当前扫描到的结点关键字与Key相等，则检索成功；若扫描结束后，仍未找到关键字等于Key的结点，则检索失败。,存储结构：顺序存储或链式存储,本节介绍基于顺序表的顺序检索算法。,/*/ /* 线性表检索用的头文件 文件名:seqlist.h */ /*/ #include #define maxsize 100 /*预定义最大的数据域空间*/ typedef int datatype; /*假设数据类型为整型*/ typedef struct datatype datamaxsize; /*此处假设数据元素只包含一
4、个整型的关键字域*/ int len; /*线性表长度*/ seqlist; /*预定义的顺序表类型*/,算法9.1给出了基于顺序查找表的顺序检索方法。 /* 顺序检索算法 文件名:s_search.c */ /* 函数名: seqsearch1()、seqsearch2() */ #include “seqlist.h“ /*-顺序查找的非递归实现-*/ int seqsearch1(seqlist l,datatype key) int k=l.len-1; while (k=0 ,/*-顺序查找的递归实现-*/ int seqsearch2(seqlist l,int n,datatyp
5、e key) int k=0; if (n=-1) k=-1; else if (l.datan=key) k=n; else k=seqsearch2(l,n-1,key); return(k); 算法9.1 线性表的顺序检索（顺序存储）,顺序检索的缺点是查找时间长。假设顺序表中每个记录的查找概率相同，即Pi=1/n（i=0，1，n-1），查找表中第i个记录所需的进行的比较次数Ci=n-i。因此，顺序查找算法查找成功时的平均查找长度为：,算法分析：,ASLseq=,查找失败时，算法的平均查找长度为：,ASLseq=,9.2.2二分法检索,二分法检索又称为折半查找，采用二分法检索可以大大提高查
6、找效率，它要求线性表结点按其关键字从小到大（或从大到小）按序排列并采用顺序存储结构。,采用二分搜索时，先求位于搜索区间正中的对象的下标mid，用其关键码与给定值x比较: lmid. Key = x，搜索成功； lmid. Key x，把搜索区间缩小到表的前半部分，再继续进行对分搜索； lmid. Key x，把搜索区间缩小到表的后半部分，再继续进行对分搜索。,每比较一次，搜索区间缩小一半。如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜索失败。,有一组有序的线性表如下： （10，14，20，32，45，50，68，90，100，120）,例,下面分析在其中二分检索关键字20的过程。,
7、下面分析二分检索关键字95的过程:,下面给出二分检索法的非递归与递归实现算法，算法中使用seqlist.h中定义的顺序查找表。,/*/ /* 二分查找算法 文件名：b_search.c */ /* 函数名：binsearch1()、binsearch2() */ /*/ /*-二分查找的非递归实现-*/ int binsearch1(seqlist l,datatype key) int low=0,high=l.len-1,mid; while (low=high) mid=(low+high)/2; /*二分*/,if (l.datamid=key) return mid; /*检索成功返
8、回*/ if (l.datamidkey) high=mid-1; /*继续在前半部分进行二分检索*/ else low=mid+1; /*继续在后半部分进行二分检索*/ return -1;/* 当lowhigh时表示查找区间为空，检索失败*/ ,binsearch2(l,key,mid+1,high);,/*-二分查找的递归实现-*/ int binsearch2(seqlist l,datatype key,int low,int high) int mid,k; if (lowhigh) return -1; /*检索不成功的出口条件*/ else mid=(low+high)/2;
9、/*二分*/ if (l.datamid=key) return mid; /*检索成功返回*/ if (l.datamidkey) return /*递归地在前半部分检索*/ else return /*递归地在后半部分检索*/ ,binsearch2(l,key,low,mid-1);,搜索成功的情形 搜索不成功的情形,从有序表构造出的二叉搜索树(判定树),若设 n = 2h-1，则描述对分搜索的二叉搜索树是高度为 h-1 的满二叉树。2h = n+1, h = log2(n+1)。 第0层结点有1个，搜索第0层结点要比较1次；第1层结点有2个，搜索第1层结点要比较2次；，,ASLbins
10、=,在假定每个结点的查找概率相同的情况下，二分检索的平均查找次数为：,用数学归纳法容易证明：,ASLbins=,=,= log2(n+1)-1,9.2.3分块检索,分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。,1、 查找表存储结构 查找表由“分块有序”的线性表和索引表组成。 （1）“分块有序”的线性表 线性表R被均分为若干块，每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是“分块有序“的。,（2）索引表 抽取各块中的最大关键字及其起始位置构成一个索引表IDlb，即： IDi(1ib)中存放第
11、i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。,【例】例如，图9.2就是一个带索引的分块有序的线性表。其中线性表L共有20个结点，被分成3块，第一块中最大关键字25小于第二块中的最小关键字27，第二块中最大关键字55小于第三块中的最小关键字60。,图9.2 分块有序表的索引存储表示,2、分块查找的基本思想 分块查找的基本思想是： （1）首先查找索引表 索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。,（2）然后在已确定的块中进行顺序查找 由于块内无序，只能用顺序查找。,分块检索方法通过将查找缩小在某个块中从而提高了检索的效率，其
12、查找的效率由两部分组成，一是为确定某一块对索引表的平均查找长度El，二是块内查找所需的平均查找长度Eb 。,若以顺序检索来确定块，则分块查找成功时的平均查找长度为：,ASLids=El+Eb=,当 时，ASLids取最小值 +1,若以二分检索来确定块，则分块检索查找成功时的平均查找长度为： ASLids=El+Eb log2（b+1）-1+（s+1）/2 log2（n/s+1）+s/2,/*/ /* 分块查找算法 */ /* 文件名：i_search.c 函数名：indexseqsearch() */ /*/ #include “seqlist.h“ typedef struct /*索引表结
13、点类型*/ datatype key; int address; indexnode;,/*-分块查找-*/ int indexseqsearch(seqlist l,indexnode index,int m,datatype key) /*分块查找关键字为Key的记录，索引表为index0m-1*/ int i=0,j,last; while (iindexi.key) i+; if (i=m) return -1; else /*在顺序表中顺序检索*/ if (i=m-1) j=l.len-1;,else j=indexi+1.address-1; /*j初始时指向本块的最后一个结点*/
14、 while (j=indexi.address 算法9.3 分块检索,9.3 二叉排序树,在线性表的三种检索方法中二分检索法具有最高的查找效率，但是它只适合于顺序存储结构，这给查找表中数据的增、删带来不便。,1、二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 左、右子树本身又各是一棵二叉排序树。 上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树,9.3 二叉排序树,2、二叉排序树的特点 由BST性质可得： （1） 二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。 （2） 二叉排序树中，各
