【大学数据结构课件】 查找

《【大学数据结构课件】 查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、内容提要8.1查找的基本概念8.2静态查找表无序表查找有序表查找分块查找8.3动态查找表B树B+树8.4哈希表8.1查找的基本概念关键字：表示数据元素的数据项查找：寻找关键字满足特定条件的数据元素的过程查找表：用于查找的数据结构，可能是线性结构，也可能是非线性结构静态查找：查找过程中，不会修改查找表的查找操作动态查找：查找的目的是为了修改查找表，通常是查找成功则删除结点，查找失败则插入结点平均查找长度：查找过程中的平均比较次数，它是比较查找算法优劣的依据2、静态查找表(1)无序表的查找intsqsearch(SQLISTL,intaidkey){intj

2、;for(j=0;j

3、LISTL,intaidkey){intlow,high,mid;low=0;high=L.len-1;while(low<=high){mid=(low+high)/2;if(L.elem[mid]==aidkey)returnmid;elseif(L.elem[mid]>aidkey)high=mid-1;elselow=mid+1;}return-1;}12233334441+2*2+4*3+3*4=29O(29/10)123456789102、静态查找表(cont’d)(2)有序表的查找III.斐波那契查找：根据斐波那契序列的特点对有序表分割0.6

4、18法斐波那契序列1235813213455······f(n)······f(n+2)=f(n)+f(n+1)从20个数的数表中查找一个纪录先找比较第13个，如果小，再比较第8个，····如果大比较后几个数的第5个······每次都比较位于这个数列的黄金分割点0.618处比如12345678910111213141516查找15的位置2、静态查找表(cont’d)(2)有序表的查找IV.插值查找：应用条件：查找表中关键字分布均匀查找失败时，确定下一个比较对象的方法：2、静态查找表(cont’d)(3)分块查找将查找表分成若干块，块的大小可以不等，块内可以

5、是无序的，但块间是有序的。比如，前面块内的所有关键字都比后面的小。利用索引表记录每个块的起点和终点和块内的最大关键字。查找时先在索引表中搜索确定，需要在哪个块内查找，然后，在到查找表特定区间内去搜索。365443284925587463657694101138146...012345678910111213145494154……..最大关键字0612……..块起始地址3、动态查找表(1)B树(B-树)I.B树的定义：一棵m叉(或称m阶)B树，或者是空树，或者是满足下面特性的m叉排序树(lchild

6、如根结点不是叶，至少有两棵子树，③除根之外，所有非终端结点至少有┌m/2┐(m/2向上取整)棵子树,以后记为[m/2]④所有的非终端结点含有信息最多[m/2]-1个关键字Ai是子树指针，Ki是关键字，结点内部关键字有序⑤所有叶结点都在同一层次，叫做失败结点。AVL树、B树和B+树都是常用的动态查找表AnKn······K2A1K1A0n3、动态查找表(cont’d)(1)B树(B-树)II.B树的查找：过程演示·35·1·18·1·78·43·2·11·1·27·1·39·1·99·1·53·47·2FFFFFFFFFFF533、动态查找表(cont’d)

7、(1)B树(B-树)III.B树的插入：先查找插入的位置，必然在最低一层结点有序插入！但结点的插入可能会导致结点被撑破，需要分两种情况处理：(1)如果插入关键字后,叶子结点中的关键字数量<=m-1，则插入操作完毕。(2)如果插入后，叶子结点中的关键字数量是m，则需要将叶子结点一分为2，成为2个叶子，中间的关键字携带着新叶子结点的指针上升到双亲结点中。这就转化为在双亲结点中插入一个关键字的问题了。这个问题的处理仍需要按照(1)(2)两种情况处理，一直到增加关键字的结点未满或者新生成根结点为止。·35·1·18·1·78·43·2·11·1·27·1·39·1

8、·99·1·53·47·2FFFFFFFFFFF向一棵3阶B树增加