配套资源下载
第8章 查找
可以参考改网站
8.1 概述
所谓查找,就是根据给定的某个值,在一组记录集合中确定某个特定的数据元素(记录)或 者找到属性值符合特定条件的某些记录。
其中,由同一类型的数据元素(或记录)构成的集合称为“查找表”,也就是查找对象的集合。 关键字是查找表中“特定的"数据元素(或记录)的某个数据项的值,用来识别一个数据元素(或 记录)。若关键字可以唯一地识别一个记录,则称其为“主关键字”;若关键字能识别若干个记录,则称其为“次关键字”
通常,对查找表进行的操作有以下几种。
①查询某个特定的数据元素是否在查找表中
②检索某个特定的数据元素的各种属性，
③在查找表中插入某个数据元素
④从查找表中删除某个数据元素
一般前两项称为“静态查找”,后两项称为“动态查找”
如果在查找表中存在待查记录,则查找成功,并输出该记录的相关信息,或指示该记录在查找表中的位置;否则查找不成功,给出空记录或空指针。
平均查找长度:为确定某元素在查找表中的位置,需要和给定值进行比较的关键字个数的期望值,称为该查找算法查找成功时的“平均查找长度”(average search length,ASL)。
对于长度为n的查找表,查找成功时的平均查找长度为ASL= ∑ni=1PiCi。其中Pi为查找第i个记录的概率, 且 ∑ni=1p=1。Ci为找到该记录时，曾经和给定值比较过的关键字的个数。
8.2 基于线性表的查找
8.2.1顺序查找
顺序查找表的数据类型描述如下。
#define MAXSIZE 1000 //顺序查找表记录数目 typedef int KeyType; //假设关键字类型为整型 typedef int OtherType; typedef struct{ KeyType key; //关键字项 //其他数据项,类型OtherType依赖于具体应用而定义 OtherType other_data; }RecordType;//记录类型 typedef struct{ RecordType r [MAXSIZE+1]; int length; //序列长度,即实际记录个数 }SeqRList; //记录序列类型,即顺序表类型
为符合C语言标准,记录序列的下标都从0开始,但下标为0的位置一般作为“监视哨"或
空闲不用,实际的记录序列都从下标为1的记录开始，
例如，一个顺序查找表的记录序列的关键字分别为21,37,88,19,92,5,64,56,80,72,13,待查找记录的关键字为64。
由于整个记录序列是无序的,所以查找时只能从前向后或从后向前进行,从概率的角度来说选择哪种进行都是可以的。
算法8-1为从后向前进行顺序查找的实现。
相关代码请看配套资源
1-顺序查找.c
int main(){ SeqRList L; input(&L); int s=SeqSearch(L,64); printf("s:%d\n",s); int s2=SeqSearch2(L,64); printf("s2:%d\n",s2); // output(&L); return 0; }
显然,该算法的时间代价主要消耗在while循环处,即两个循环判断条件的执行。其中,第
个循环条件i>=1是保证循环的结束,即边界条件的判定。事实上,在保证查找成功的情况下，该条件的执行只是白白浪费时间。有实验表明,在查找记录超过1000条时,该条语句的执行时间占到了整个算法执行时间的60%。
算法8-2为改进后(即加“监视哨")的顺序查找实现。
相关代码请看配套资源
1-顺序查找.c
int main(){ SeqRList L; input(&L); int s=SeqSearch(L,64); printf("s:%d\n",s); int s2=SeqSearch2(L,64); printf("s2:%d\n",s2); // output(&L); return 0; }
可以看出,算法利用了0号位管作为“监视哨”,人为地将其关键字设置为待查记录的键字K。这样从后向前进行查找时,省去了边界条件的判断,无论查找成功或失败都能找到
该条记录在查找表中的位置。如果是i>0的位置,则在找成功;如果是i=0的位置,则查找失败。
对顺序表,其平均查找长度为ASL=nP1+(n-1)P2+2Pn-1+Pn
在等概率查找的情况下,Pi=1/n,Ci=n-i+1
顺序表查找成功时的平均查找长度为ASLSUCC-=1/n ∑ni=1(n-i+1)= (n+1)/2
也就是说,香找成功时的平均比较次数是表长的一半,那么当表长很大时,查找的效率比较低。但是,顺序查找的优势在于对表的特性没有要求,数据元素可以任意排列,插入元素可以直接加到表尾。
如果查找不成功,则需要讲行n+1次比较才能确定查找失败。假设被查找的关键字记录在线性表中(即查找成功)的概率为p，不在线性表中(即查找失败)的概率为1-p。那么,成功和失败的查找都考虑在内时的平均比较次数为
ASL=p(n+1)/2+(1-p)(n+1)=(n+1)(1-p/2)
可以看出，(n+1)/2<ASL<(n+1)
通常情况下,查找概率无法事先测定,为了加快查找速度,可以建立自组织线性表。自组织 线性表是根据实际的记录访问模式在线性表中修改记录顺序,主要使用启发式规则决定如何重 新排列线性表。一般管理自组织线性表的启发式规则有以下三种。
①最不频繁使用法(least frenquently used,LFU),也叫做“计数法”。。
②最近最少使用法(least recently used,LRU),也叫做“移至前端法”。
③转置(transpose)方法,也叫做“调换方法”。
8.2.2 折半查找
【算法 8-3】折半查找的非递归实现
相关代码请看配套资源
2-折半查找.c
int main(){ SeqRList L; input(&L); printf("查找的索引：\n"); int s=BinSrch(L,3); printf("s:%d\n",s); output(&L); return 0; }
运行结果如下：
查找成功时，关键字的比较次数最多不超过⌊log2n⌋+1
查找失败时，关键字的比较次数最多不超过⌊log2n⌋+1
折半查找成功时的平均查找长度为
ASL=∑ni=1PiCi=1/n ∑ni=1Ci=1/n ∑hj=1 x2j-1=(n+1)/n log2(n+1)-1
当n>50时，可得近似结果ASL≈ log2(n+1)-1
折半查找适用于一些建立就很少改动，而且与需要经常查找的有序查找表
8.2.3 索引查找
略
8.3 基于树的查找
8.3.1 二叉排序树
二叉排序树(binary search tree,BST),又称为“二叉查找树",是一种高效的数据结构。二叉排序树或者是一棵空树,或者是具有如下特性的二叉树。
①若它的左子树不空,则左子树上所有结点的值均小于根结点的值
②若它的右子树不空,则右子树上所有结点的值均大于根结点的值
③它的左、右子树也都分别是二叉排序树
显然,这是一个递归定义,首先要保证结点的值之间具有可比性,另外,关键字之间不允许重复出现。在实际应用中,不能保证被查找记录的关键字互不相同,可将 ①中的“小于"改为“小于等于”,或将②中的“大于"改为“大于等于”,甚至可同时修改这两个性质。
中序遍历二叉排序树便得到递增的有序序列。
二叉排序树可以使用二叉链表作为存储结构,数据类型描述如下。
typedef int KeyType; //假设的关键字类型 typedef int OtherType; typedef struct Node{ KeyType key; OtherType other_data; struct Node* Lchild,* Rchild; }BSTNode,* BSTree;
相关代码请看配套资源
3-二叉排序树.c
代码运行结果如下
1.二叉排序树的查找
由于二叉排序树可以看成是一个有序表,所以在二叉排序树上进行查找类似于折半查找,即逐步缩小查找范围的过程。具体如下 。
①若给定值等于根结点的关键字,则查找成功。
②若给定值小于根结点的关键字,则继续在左子树上进行查找。
③若给定值大于根结点的关键字,则继续在右子树上进行查找。
由图8-9可以看出,整个查找过程类似于在折半查找的判定树上进行折半查找。从根结点出发,沿着左子树或右子树逐层向下直至关键字等于给定值的结点——查找成功;从根结点出发,沿着左子树或右子树逐层向下直至指针指向空结点(方块处)为止——查找失败。
基于二叉排序树查找的非递归实现见算法8-4.
相关代码请看配套资源
代码运行结果如下
显然,根据递归特性,算法也可以用递归实现,见算法8-5。
相关代码请看配套资源
代码运行结果如下
2.二叉排序树的插入
首先查找待插入的记录是否在树中,如果存在则不允许插入重复关键字；如果直到找到叶子结点仍没有发现重复关键字,则把待插结点作为新的叶子结占插入。具体地,若二叉排序树为空树,则新插入的结点为新的根点:否则,新插入的结点必为一个新的叶子结点,其插入位置由查找不成功的位置确定。
[算法8-6]二叉排序树的插入
相关代码请看配套资源
代码运行结果如下
3.二叉排序树的建立
二叉排序树的建立是基于插人算法进行的,根据给定的关键字顺序依次插入得到。
可以看出，二叉排序树的形态完全由输入顺序决定,相同的关键字不同的输人顺序会产生不同的二叉排序树
[算法8-7] 二叉排序树的建立
相关代码请看配套资源
代码运行结果如下
4.二叉排序树的删除
由于二叉排序树要求关键字之间满足一定的大小关系,这就使得从中删除一个结点的算法相对复杂。具体地,首先在二叉排序树中查找待删结点,如果不存在则不做任何操作;否则,分以下三种情况进行讨论。
①待删结点是叶子结点:
②待删结点只有左子树或只有右子树。
③待删结点既有左子树也有右子树。
先看第①种情况
可以看出,此种情况只需将待删结点的父亲结点的相应孩子城置空，
再来看第②种情况
可以看出,此种情况只需将待删结点的父亲结点的相应孩子域置为该孩子对应的左子树可右子树。
最后来看第③种情况,待删结点既有左子树又有右子树。从二义排序树中删除这样一个 点时,要保持剩下结点之间依然满足排序树的特征,就不能在二义排序树中留下一个空位置，因此需要用另一个结点来补充这个位置。那么应该用哪个结点来补充呢?而日为了保证删除的高效性,应该尽量保证其他元素的移动量是最小的。前面已经分析过,二叉排序树的中序遍历结果恰好是一个有序序列,那么可以利用这个结果找到替换待删结点的位置,其实就是待删结点的前驱结点或后继结点。关键是这两个结点在二叉排序树的什么位置。
综合前面提到的三种情况，算法8-8 为二叉排序树的算法实现。
[算法8-8] 二叉排序树的删除
相关代码请看配套资源
代码运行结果如下
