《第8章查找.ppt》由会员分享，可在线阅读，更多相关《第8章查找.ppt（48页珍藏版）》请在三一办公上搜索。
1、第8章 查 找,8.1 查找的基本概念,查找（Searching）是：给定一个关键字值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。,查找表的数据结构表示 若在查找的同时对表做修改操作（如插入和删除等），则相应的表称之为动态查找表（Dynamic Search Table）。否则称之为静态查找表(Static Search Table)。若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。,平均查找长度 ASL（Average Search Length）
2、为：,ASL=,其中：1、n是结点的个数；2、Pi是查找第i个结点的概率。若不特别声明，认为每个结点的查找概率相等，即 pl=p2=pn=1/n 3、ci是找到第i个结点所需进行的比较次数。（i=1,2,n）,顺序查找(Sequential Search)基本思想：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。,8.2线性表的查找,基于顺序结构的顺序查找算法,/类型说明 typedef struct KeyType key；/KeyType由用户定义 InfoType
3、 otherinfo；NodeType；typedef NodeType Seqlistn+1；/*0号单元用作监视哨*/,算法描述 int SeqSearch(Seqlist R，KeyType K)/*在顺序表R1.n中顺序查找关键字为K的结点，成功时返回找到的结点位置，失败时返回0*/int i；R0.key=K；/*设置监视哨*/for(i=n；Ri.key!=K;i-)；/*从表后往前找*/return i；/*若i为0，表示查找失败，否则Ri为要找的结点*/*SeqSearch*/,算法分析,查找成功时的顺序查找的平均查找长度：ASL=pi=np1+(n-1)p2+2pn-1+pn
4、 在等概率情况下，pi=1/n(1in)，故成功的平均查找长度为(n+2+1)/n=(n+1)/2即查找成功时的平均比较次数约为表长的一半。,顺序查找的优点 算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。顺序查找的缺点 查找效率低。,二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。,二分查找,基本思想：（1）首先确定该区间的中点位置：mid=（2）然后将待查的K值与Rmid.key比较：若相等，则查找成功并返回此位置
5、，否则须确定新的查找区间，继续二分查找。,算法描述int BinSearch(SeqList R，KeyType K)int low=1，high=n，mid；while(lowK)high=mid-1;else low=mid+1；return 0；,二分查找判定树 二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)。,二分查找判定树的组成,圆结点即树中的内部结点。树中圆结点内的数字表示该结点在有序表中的位置。
6、外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。当查找时找到外部节点时，表示查找的值没有在该有序表中。,算法分析,二分查找成功时的平均查找长度为：ASLbnlg(n+1)-1 二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为：,优点和缺点,虽然二分查找的效率高，但是要将表按关键字排序。二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。,分块查找,基本思想：1首先查找索引表 索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。2 然后在已确定的块中进
7、行顺序查找 由于块内无序，只能用顺序查找。,算法分析,分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。以二分查找来确定块，分块查找成功时的平均查找长度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),优点：1 在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。2 因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。,8.3 树表的查找,二叉
8、排序树（在第6章已经介绍，这里不再介绍）B-树,B-树的定义：一棵m(m3)阶的B-树是满足如下性质的m叉树：(1)每个结点至少包含下列数据域：(n，P0，Kl，P1，K2，Ki，Pi)其中：n为关键字总数 Ki(1ij)是关键字，关键字序列递增有序：K1 K2Ki。Pi(0ij)是孩子指针。对于叶结点，每个Pi为空指针。,B-树,(2)所有叶子是在同一层上，叶子的层数为树的高度h。(3)每个非根结点中所包含的关键字个数j满足：(4)若树非空，则根至少有1个关键字，故若根不是叶子，则它至少有2棵子树。根至多有m-1个关键字，故至多有m棵子树。,B-树的存储结构#define Max l000#
9、define Min 500 typedef int KeyType；typedef struct node int keynum；KeyType keyMax+1；struct node*parent；struct node*sonMax+1；BTreeNode；typedef BTreeNode*BTree；,B-树的查找 在B-树中查找给定关键字的方法类似于二叉排序树上的查找。不同的是在每个结点上确定向下查找的路径不一定是二路而是keynum+1路的。对结点内的存放有序关键字序列的向量keyl.keynum 用顺序查找或折半查找方法查找。若在某结点内找到待查的关键字K，则返回该结点的地址
10、及K在key1.keynum中的位置；否则，确定K在某个keyi和keyi+1之间的结点后，从磁盘中读soni所指的结点继续查找。直到在某结点中查找成功；或直至找到叶结点且叶结点中的查找仍不成功时，查找过程失败。,算法描述BTreeNode*SearchBTree(BTree T，KeyType K，int*pos)int i；Tkey0=k;for(i=T-keynum；Kkeyi;i-)；if(i0&T-keyi=1)*pos=i；return T；if(!T-soni)return NULL；DiskRead(T-soni)；return SearchBTree(T-Soni，k，pos
11、)；,8.4 散列表的查找,散列表(Hash Table)散列是一种重要的存储方法，也是一种常见的查找方法。散列的基本思想是：以结点的关键字K为自变量，通过一个确定的函数（即映射）关系h，计算出对应的函数值h(K)，然后把这个值解释为结点的存储地址，将结点存入h(K)所指的存储位置上。在查找时，根据要查找的关键字用同一函数h计算出地址，再到相应的单元里去取要找的结点。因此，散列方法又称为关键字-地址转换法，用散列方法存储的线性表称为散列表(Hash Table)，也称哈希表或杂凑表。上述的函数h称为散列函数，h(K)称为散列地址。,通常散列表的存储空间是一个一维数组，散列地址是该数组的下标。在
12、不会引起混淆的情况下，我们就将这个一维数组简称为散列表。例：以城市名或省名的拼音作为关键字K，散列函数h(K)为取K的首字母在字母表中的序号，可得散列地址如下：,散列表的冲突现象冲突 两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。安全避免冲突的条件 最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：1 关键字的个数小于或等于散列表的长度；2 选择合适的散列函数。,冲突不可能完全避免 通常情况下，由于关键字的个数大于散列表的长度，因此，无论怎样设计h，也不
13、可能完全避免冲突。我们只能做到，在设计h时尽可能使冲突最少，同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到散列表中。影响冲突的因素 冲突的频繁程度除了与h相关外，还与表的填满程度相关。设m表示散列表的表长，n表示表中填入的结点个数，则将=n/m定义为散列表的装填因子(Load Factor)。越大，表越满，冲突的机会也越大。通常取1。,常用散列函数,平方取中法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。,除留余数法 该方法是最为简单常用的一种方法。它是以表长m来
14、除关键字，取其余数作为散列地址，即 h(key)=keym该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数。,相乘取整法该方法包括两个步骤：首先用关键字key乘上某个常数A(0A1)，并抽取出key.A的小数部分；然后用m乘以该小数后取整。即：该方法最大的优点是选取m不再像除余法那样关键,随机数法选择一个随机函数，取关键字的随机函数值为它的散列地址，即 h(key)=random(key)其中random为伪随机函数，但要保证函数值是在0到m-1之间。,处理冲突的方法,（1）用开放地址法解决冲突做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成
15、一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。,1、开放地址法,（2）开放地址法的一般形式开放定址法的一般形式为：hi=(h(key)+di)m 1im-1（3）开放地址法堆装填因子的要求开放定址法要求散列表的装填因子l，实用中取为0.5到0.9之间的某个值为宜。,（4）形成探测序列的方法按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。线性探查法(Linear P
16、robing)该方法的基本思想是：将散列表T0.m-1看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：d，d+l，d+2，m-1，0，1，d-1即:探查时从地址d开始，首先探查Td，然后依次探查Td+1，直到Tm-1，此后又循环到T0，T1，直到探查到Td-1为止。,二次探查法(Quadratic Probing)二次探查法的探查序列是：hi=(h(key)+i*i)m 0im-1，即di=i2 即探查序列为d=h(key)，d+12，d+22，等。该方法的缺陷是不易探查到整个散列空间。,双重散列法(Double Hashing)该方法是开放定址法中最好的方
17、法之一，它的探查序列是：hi=(h(key)+i*h1(key)m 0im-1，即di=i*h1(key)即探查序列为：d=h(key)，(d+h1(key)m，(d+2h1(key)m，等。,2、拉链法处理冲突拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T0.m-1。凡是散列地址为i的结点，均插入到以Ti为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子可以大于1，但一般均取1。,例：已知一组关键字为（26，36，41，38，44，15，68，12，06，51），取表长为1
18、3，用拉链法解决冲突构造这组关键字的散列表，如右图所示。,拉链法的优点(1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；(3)开放定址法为减少冲突，要求装填因子较小，故当结点规模较大时会浪费很多空间。而拉链法中可取1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；(4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。,拉链法的缺点拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省
19、的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。,散列表上的运算,/散列表类型说明：#define NIL-1#define m 997 typedef struct KeyType key；InfoType otherinfo；NodeType；typedef NodeType HashTablem；,基于开放地址法的查找算法 散列表的查找过程和建表过程相似。假设给定的值为K，根据建表时设定的散列函数h，计算出散列地址h(K)，若表中该地址单元为空，则查找失败；否则将该地址中的结点与给定值K比较。若相等则查找成功，否则按建表时设定的处理冲
20、突的方法找下一个地址,如此反复进行，直到某个地址单元为空(查找失败)或者关键字比较相等(查找成功)为止。,开放地址法一般形式的函数表示int Hash(KeyType k，int i)return(h(K)+Increment(i)m；若散列函数用除留余数法构造，并假设使用线性探查的开放定址法处理冲突，则上述函数中的h(K)和Increment(i)可定义为：int h(KeyType K)return Km；int Increment(int i)return i;/,通用的开放定址法的散列表查找算法：int HashSearch(HashTable T，KeyType K，int*pos)
21、int i=0；do*pos=Hash(K，i)；if(T*pos.key=K)return l；if(T*pos.key=NIL)return 0；while(+im)return-1；,删除基于开放定址法的散列表不宜执行散列表的删除操作。若必须在散列表中删除结点，则不能将被删结点的关键字置为NIL，而应该将其置为特定的标记DELETED。一般情况下，当必须对散列表做删除结点的操作时，是采用拉链法来解决冲突。,性能分析因插入和删除的时间均取决于查找，故只要分析查找操作的时间性能。虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关键字的比较就可找到待查关键字。但是由于冲突的存在，散列表的查找过程仍是一个和关键字比较的过程，不过散列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的查找要小得多。,
