[计算机软件及应用]ds08-查找

《[计算机软件及应用]ds08-查找》由会员分享，可在线阅读，更多相关《[计算机软件及应用]ds08-查找（99页珍藏版）》请在金锄头文库上搜索。

1、基本概念 线性表的查找 树表的查找 散列(Hash)技术,第八章 查找,8.1查找的基本概念,查找（Searching）的定义是：在含有n条记录的表（文件）中找出关键字等于给定值K的记录。若找到，则查找成功，返回该记录的信息或该记录在表（文件）中的位置；否则查找失败，返回相关的指示信息。,若在查找的同时对表做修改操作（如插入和删除等），则相应的表称之为动态查找表（Dynamic Search Table）。否则称之为静态查找表(Static Search Table)。 若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找,查找表的数据结构表示,如何分析算

2、法优劣？主要分析算法运算时所需要的时间和其存储结构占用的内存空间。而对于查找算法，执行的时间通常取决于关键字的比较次数，所以本章经常用平均比较次数，即平均查找长度 ASL（Average Search Length）,其中： 1、n是结点的个数； 2、Pi是查找第i个结点的概率。若不特别声明 ，认为每个结点的查找概率相等，即 pl = p2 = pn = 1/n 3、ci是找到第i个结点所需进行的比较次数,ASL=,平均查找长度 ASL（Average Search Length）定义为 ：,一、顺序查找(Sequential Search) 基本思想是：从表的一端开始，顺序扫描线性表，依次将

3、扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。,8.2 线性表的查找,基于顺序结构的顺序查找算法,类型说明 typedef struct KeyType key； /*KeyType由用户定义*/ InfoType otherinfo； /*此类型依赖于应用*/ NodeType； typedef NodeType Seqlistn+1；,/*多出0号单元用作监视哨*/,具体算法 int SeqSearch(Seqlist R，KeyType K) /*在顺序表R1n中顺序查找关键字为K的结点，*/ /*

4、成功时返回找到的结点位置，失败时返回0*/ int i； R0.key=K； /*设置监视哨*/ for(i=n；Ri.key!=K;i-)；/*从表后往前找*/ return i； /*若i为0，表示查找失败，否则Ri为要找的结点*/ /*SeqSearch*/,算法分析,查找成功时的顺序查找的平均查找长度： 在等概率情况下，pi=1/n(1in)，故成功的平均查找长度为 ASL= =(n+2+1)/n=(n+1)/2 即查找成功时的平均比较次数约为表长的一半。,顺序查找的缺点 查找效率低。,顺序查找的优点 算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是

5、否按关键字有序，它都同样适用。,二分查找又称折半查找，它是一种效率较高的查找方法。 二分查找要求：要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。,二、二分查找,（1）首先确定该区间的中点位置 mid = （2）然后将中间位置记录的键值Rmid.key和所给关键字K进行比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。,二分查找的基本思想是：,例：设算法的输入实例中有序的关键字序列为： 05，13，19，21，37，56，64，75，80，88，92。查找的关键字K=21,第一步：这里的n=11,mid=(1+11)

6、/2=6 05，13，19，21，37，56，64，75，80，88，92,第二步：mid=(1+5)/2=3 05，13，19，21，37，56，64，75，80，88，92,第三步： mid=(4+5)/2=4 05，13，19，21，37，56，64，75，80，88，92 此时Rmid.keyK，return mid4。,二分查找算法 int BinSearch(SeqList R，KeyType K) int low=1，high=n，mid； while(lowK) high=mid-1; else low=mid+1； return 0； ,确定新的查找区间,二分查找过程可用二叉

7、树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)。,二分查找判定树,二分查找判定树的组成,如对表R3，7，11，19，30，115，136，141的查找过程：,3 7 11 19 30 115 136 141,3 7 11 19 30 115 136 141,Low mid high,Low mid high,如k=115的记录结点编号为6，处于第二层，则比较次数只有两次就可找到（这样的记录共有两个21=2）；查找第三层的记录需要

8、三次比较（这样的记录共有四个22=4 ）；查找第k层的记录需要k次比较（这样的记录共有2k-1个）;等等。假定每个记录的查找概率相等，即为1/n，则其平均查找次数为：,ASL= =1/n ci =1/n(1*20+2*21+3*22+k*2k-1+) = 1/n i*2i-1 ; 而 i*2i-1 =k2k-2k-1,k,又根据二叉树的性质：k=log2(n+1) 故： ASL=（n+1）/nlog2(n+1)-1 log2(n) 当n很大时,二分查找的平均查找长度,二分查找成功时的平均查找长度为： ASLbnlog2(n) 二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情

9、况下查找成功的比较次数也不超过判定树的深度。即为：,二分查找的优点和缺点,虽然二分查找的效率高，但是要将表按关键字排序（有序表）。 二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。,三、分块查找（索引顺序查找 ）,分块查找表存储结构 分块查找的特点是：按表内记录的某种属性把表（文件）分成b个块（子表），并建立一个相应的“索引表”，索引表中每个元素对应一个块，而在索引表中是按其关键字有序，但是每一块中的记录的存放是任意的，块与块之间必须是有序的。即分块查找的前提是：文件由“分块有序“的线性表和索引表组成。,分块查找表由“分块有序“的线性表和索引表组成。

10、（1）“分块有序“的线性表 将表（文件）R1.n平均分为b块；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是“分块有序“的。 （2）索引表 抽取各块中的最大关键字及其起始位置构成一个索引表IDlb，即：IDi(1ib)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。,1、分块查找表的存储结构,分块查找的基本思想是： （1）首先查找索引表 索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。 （2）然后在已确定的块中进行顺序查找 由于块内无序（也可有序），只能用顺序查找。,2、分块查找的基

11、本思想,例： 图8.2所示的表及其索引表是满足上述要求的分块查找表，其中R只有18个结点，被分成3块，每块中有6个结点，第一块中最大关键字22小于第二块中最小关键字24，第二块中最大关键字48小于第三块中最小关键字49。,ID,块内最大键值 块内第一个元素序号,（1）先在索引表中查找,来确定关键字等于给定值K=24的结点所在的块 因为索引表小，不妨用顺序查找方法查找索引表。即首先将K依次和索引表中各关键字比较，直到找到第1个关键字大小等于K的结点，由于K48，所以关键字为24的结点若存在的话，则必定在第二块中；然后，由ID2.addr找到第二块的起始地址7，从该地址开始在R712中进行顺序查找

12、，直到R11.key=K为止。 （2）在所确定的块内查找关键字等于给定值K=30的结点 在第二块内查找。因在该块中查找不成功，故说明表中不存在关键字为30的结点。,进行下列查找：,算法分析,分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。 以二分查找来确定块，分块查找成功时的平均查找长度(在索引表中用二分查找，在块内用顺序查找) ASLblk= ASLbn+ASLsqlog2(b+1)-1+(s+1)/2log2(n/s+1)+s/2 以顺序查找确定块，分块查找成功时的平均查找长度 ASLblk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s),在表

13、中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。 因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。,分块查找的优点,8.3 树表的查找,1、二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： （1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值； （2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值； （3）左、右子树本身又各是一棵二叉排序树。,（1） 二叉排序树中任一结点x，其左(右)子

14、树中任一结点y(若存在)的关键字必小(大)于x的关键字。 （2） 二叉排序树中，各结点关键字是惟一的。 （3） 按中序遍历该树所得到的中序序列是一个递增有序序列。,二叉排序树的特点,要查找键值等于k的记录，最先与根结点的键值比较，若二者相等，则查找成功 。若k值小于根结点的键值，则继续查找左子树，反之查找右子树。若沿某条路经碰到一个端点（叶子）还末查到，则查找不成功，这也是静态表的查找。,二叉排序树的查找算法：,二叉排序树的存储结构,typedef int KeyType； typedef struct node KeyType key； /*关键字类型*/ infoType otherinf

15、o； /*结点其它信息类型*/ struct node *lchild，*rchild； BSTNode； /*二叉排序树的结点类型*/ typedef BSTNode *BSTree；,在二叉排序树中插入新结点，要保证插入后仍满足BST性质。其插入过程是： 1)若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根； 2)若二叉排序树T不为空，则将key和根的关键字比较： (a)若二者相等，则说明树中已有此关键字key，无须插入。 (b)若keyTkey，则将它插入根的右子树中。,二叉排序树插入新结点的过程,二叉排序树插入新结点的算法 void InsertBST(BSTree Tptr，Keytype key) BSTNode *f，*p=Tptr； while(p) /*p不空*/ if(p-key=key) return； /*找到了，则不插入*/ f=p； /*f是p的双亲*/ p=(keykey)?p-lchild:p-rchild; ,p=(BSTNode*)malloc(sizeof(BSTNode)； p-key=key； p-lchild=p-rchild=NULL； if(TPtr=NULL) /*是空树*/ Tptr=p； /*新结点作为根插入*/ else