《《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第8章 检索》由会员分享，可在线阅读，更多相关《《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第8章 检索（80页珍藏版）》请在金锄头文库上搜索。
1、8.1 检索的基本概念 8.2 线性表的检索 8.3 树表的检索 8.4 B树 8.5 散列检索技术,第8章 检索,8.1 检索的基本概念 1、检索定义 （1）关键字 关键字（Key）是数据元素（或记录）中某个数据项的值，用它可以标识（或识别）一个数据元素（或记录）。在一个记录中，每个数据项都可作为该记录的关键字。 主关键字是指在一个记录众多的关键字中能唯一地标识一个数据元素（或记录）的关键字，其它的关键字称为从关键字，也叫辅助关键字。 （2）检索表 检索表是由同一类型的数据元素（或记录）组成的集合，是检索操作所依赖的数据结构。 （3）检索定义 检索，又叫查找，是根据给定的某个值，在一个检索表
2、中确定一个其关键字等于给定值的记录或数据元素的操作运算。若检索表中存在这样的一条记录，则称检索是成功；若表中不存在这样的记录，则称检索是不成功的，是失败的，此时检索的结果在静态环境下可给出不存在此记录的提示信息；在动态环境下，可插入此关键字等于给定值的记录。,2、检索方法 依据数据的存储方式的不同，我们将检索分为线性表检索、树表检索和散列表检索等。 3、平均检索长度 将“为检索到具有给定关键字值的数据元素或记录所需要关键字的比较次数的平均值”作为衡量检索算法好坏的依据，即通过平均检索长度来衡量。具体地说，即指为确定欲检索的记录在表中的位置，需与给定值进行比较的关键字个数的期望值，称为检索算法在
3、检索成功时的平均检索长度（Average Search Length）。,其中，pi为检索第i个记录的概率，且 。若不特别说明，均认为每个记录的检索概率相等（即为等概率情形），从而有p1 =p2=pn=1/n，ci为检索到第i个记录需要和给定关键值比较的关键字个数。一般情形下，ci依赖于所采用的检索方法。,线性表的检索按照检索方法的不同可分为顺序检索、折半检索和分块检索。 8.2.1 顺序检索 1、基本思想 基本思想是：从表的第n个记录开始，用给定的值与表中各个记录的关键字逐个地进行比较，如果检索到某一个记录的关键字与给定值相等，则检索成功；若整个表中的记录均比较过，仍未检索到关键字等于给定值
4、的记录，则检索失败。,8.2 线性表的检索,2、类型定义与算法实现 typedef struct keytype key ; /*关键字类型 */ elemtype other ; /*其他的域 */ sqlist ; sqlist Rn+1 ; /* 顺序表 */ 顺序检索算法： int seqsrch (sqlist R ， keytype k) int i ; R0.key = k ; /* 将R0作为监视哨 */ i = n ; /* 从第n个记录起向前扫描 */ while (Ri.key! =k) i- ; if (i= =0) return(0) ; else return i
5、; /*seqsrch */,3、顺序检索性能分析 在等概率情况下，顺序检索的平均检索长度为：,顺序检索成功时的平均比较次数约等于表长的一半。若所检索的给定值k不在表中，则需进行n+1次比较才可确定检索失败。其算法简单，且适用面广，对表的存储结构、记录是否按关键字有序等方面不作要求。,8.2.2 折半检索 1、基本思想 折半检索又称二分检索，其基本思想是：先将待检索的给定值和检索表的中间位置上的记录的关键字值进行比较，若相等，则检索成功，否则，若给定值比该中间位置上记录的关键字值大，则只要在右半部分中继续进行折半检索，否则，只要在左半部分中继续进行折半检索。这样，经过一次关键字比较就缩小一半的
6、检索区间，如此进行下去，直到检索到关键字值为给定值的记录，或者未检索到，即检索失败。需注意的是，作为折半检索对象的表必须是顺序存储方式的有序表。,2、折半检索过程示例 已知一个含11个记录的有序表，其关键字序列为 （ 08，10，12，19，25，31，39，42，47，52，57 ） （1）检索k=12：,此时mid = 5，由于k = 12 Rmid-1.key，只要在其左子表R0R4中继续检索中继续进行折半检索。,此时mid = 2，由于 k =12 = Rmid.key，说明检索成功。,此时mid=5，由于k = 42 Rmid.key，所以只要在其右子表中继续进行折半检索，即在R6R
7、10中继续检索。,此时mid = 8，由于k = 52 Rmid.key，可缩小检索区间，即缩小为R9R10。此时mid = 9 , 且有 k = 52 = Rmid.key，则检索成功。,（2）检索k=52的记录过程：,此时，k = 87 Rmid.key，则下一步为：,此时，k87Rmid.key，则下一步为：,此时，mid =9，k Rmid.key ，则又缩小区间为R10R10，此时mid =10，由于此时k Rmid.key，又缩小区间，但此时low =10+1high，区间的下界大于上界，不能构成区间，说明检索失败。,（3）检索k=87的记录,3、折半检索算法 int binsrc
8、h（ sqlist R ， keytype k） int low , high ,mid ； low = 0；high = n-1； 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 (0) ; /* binsrch */,4、折半检索判定树 折半检索过程可以借助二叉树进行描述。把当前检索区间的中间位置上的记录或结点作为二叉树的根，
9、左半区间和右半区间中的记录分别作为根的左子树和右子树，由此就可得到一棵二叉树，称为折半检索判定树。 如图8.1所示为具有11个记录的有序表的折半检索判定树表示。,5、折半检索的平均检索长度 折半检索的过程恰好是在判定树中走了一条从二叉树树根到被检索结点的路径，经历比较的关键字个数恰为该结点在树中的层数。折半检索成功时所进行的关键字比较的次数至多为 次。 在等概率情况下（即表中每个记录检索的概率相等，pi=1/n），检索成功时的折半检索的平均检索长度为：,当n很大时，如n100时，则可得近似公式： ASLlog2(n+1)-1 折半检索的效率比顺序检索要高得多，但它只能适用于有序表，它一般只适用
10、于那些有序表，且一旦建立后很少变动而又需要经常检索的线性表。,ASL= (1+22+34+48)3.3,例如，一棵具有15个结点的判定树和其检索成功时的平均检索长度如图8.2所示。,8.2.3 分块检索 1、定义 分块检索又称索引顺序检索，属于索引检索，是一种介于顺序检索与折半检索之间的检索方法。分块检索要求将表中数据元素分成很多子表（块）后，数据元素的关键字在块与块之间是有序，而在块内不一定有序。 2、分块检索的基本思想 首先依据待检索的给定值在索引表中进行检索，由于索引表是一个有序表，所以可采用折半检索（也可采用顺序检索）以确定待检索记录属于哪一块；然后在已确定的那一块内进行顺序检索，如图
11、8.3。,图8.3 表及索引表,3、分块检索算法 （1）当顺序检索索引表时： #define M 99 typedef struct keytype key ; int stadr ; int len ; indexlist ; /*索引表的类型定义*/ indexlist IDM ; /*ID为具有indexlist类型的R上的一个索引表*/,int Blocksrch( R，ID，m，k ) sqlist R ; indexlist ID ; /* 索引表ID */ keytype k ; int m ; int i, j i = 0 ; while(i IDi.key) /* 顺序检索索
12、引表 */ i + +; if ( im-1 ) retutn(0) /* 检索失败 */ else j = Ri.stadr； /* 待检索块的第一个记录的下标 */ while(j IDi.stadr+IDi.len) /* 检索成功 */ /* Blocksrch */,（2）当折半检索索引表时： indexlist IDM ; /*ID为具有indexlist类型的R上的一个索引表*/ int Blocksrch(sqlist R ，indexlist ID ，int m，keytype k ) int i，j，low1，low2，mid，high1，high2； low1=0; hi
13、gh1=m-1; /*置折半检索区间的下、上界的初值*/ while ( low1=high1 ) /*在索引表中检索*/ mid =(low1+high1)/2 ; /* 求当前区间的中间位置 */ if (k=IDmid.key) high1 = mid-1 ; /*在左区间上检索*/ else low1=mid+1 ; /*在右区间上检索*/ /*检索结束，low1为块号*/ if (low1m) low2=IDlow1.stadr; /*块起始地址*/ if (low1= =m-1) high2=n-1; /*块末地址*/,else high2=IDlow1+1.stadr-1; fo
14、r (i=low2；i=high2；i+) /* 块内顺序检索*/ if (Ri.key= =k) return (i); /* 检索成功 */ retutn(0) /* 检索失败 */ /* Blocksrch */,ASL = Lb + Lw,其中，pbj = ，pwi = ，Cbj = j ，Cwi = i；,则有：,4、分块检索的平均检索长度 （1）若用顺序检索确定所在的块时：,（2）若用折半检索确定所在块时： ASL = Lb + Lw = log2( +1)-1+ log2( +1) + 分块检索平均检索长度界于折半检索和顺序检索之间。 只要一个检索表的数据分布特性符合分块后有序，
15、即可采用分块检索，且其对表的存储结构没有特殊要求。,在线性表的检索中，折半检索方法效率最高，但要求表以顺序存储方式存储，不能用链表作存储结构，而且表中元素按关键字有序。由于在顺序存储结构中，若要频繁地进行插入和删除结点运算时，必须移动大量的元素，而这会花费相当多的时间。利用二叉搜索树作为表的数据组织方式就可以既能把链式存储结构的优点和折半检索方法的高效率结合在一起，又不要求表为有序表。,8.3 树表的检索,8.3.1 二叉检索树 1二叉检索树的定义与性质 二叉搜索树又称二叉排序树，它或者是一棵空树，或者是一棵具有下列特性的非空二叉树： （l）若它的左子树非空，则左子树上所有结点的值均小于根结点的值； （2）若它的右子树非空，则右子树上所有结点的值均大
