《数据结构第八章.ppt》由会员分享，可在线阅读，更多相关《数据结构第八章.ppt（84页珍藏版）》请在第壹文秘上搜索。
1、 数据结构数据结构 计算机科学与计算机科学与技术学院技术学院2第九章第九章 查找查找34567查找成功时查找成功时，顺序查找的平均查找长度为：，顺序查找的平均查找长度为：查找不成功时查找不成功时，关键码的比较次数总是，关键码的比较次数总是n+1n+1次次niiicpASL12/ ) 1() 1(11ninpcpASLniniiiisq891005 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 92查找查找K=85K=85的过程（查找失败）的过程（查找失败）05
2、 13 19 21 37 56 64 75 80 88 92 11从折半查找过程看，以表的中点为比较对象，并从折半查找过程看，以表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表继以中点将表分割为两个子表，对定位到的子表继续这种操作。因而对表中每个数据元素的查找过续这种操作。因而对表中每个数据元素的查找过程可用二叉树描述，称此描述查找过程的二叉树程可用二叉树描述，称此描述查找过程的二叉树为为判定树判定树。查找表中任一元素的过程，即是判定树中从根到查找表中任一元素的过程，即是判定树中从根到该元素结点路径上各结点关键码的比较次数，也该元素结点路径上各结点关键码的比较次数，也即该即该元素
3、结点在树中的层次数元素结点在树中的层次数。1205 13 19 21 37 56 64 75 80 88 92927537138864215801956判定树：判定树： 借助于判定树很容易求得二分查找的平均查找长度。借助于判定树很容易求得二分查找的平均查找长度。设结点总数为：设结点总数为： 树中第树中第 k 层上的结点个数不超过：层上的结点个数不超过：12 hn12k13因此，在等概率假设下，二分查找的平均查找长度为：因此，在等概率假设下，二分查找的平均查找长度为： 二分查找的算法复杂度为：二分查找的算法复杂度为： 优点：优点：查找的效率较高查找的效率较高 缺点：缺点：要求被查找序列事先按关键
4、字排好序，而排要求被查找序列事先按关键字排好序，而排序本身是一种很费时的运算；另外，二分查找只适用序本身是一种很费时的运算；另外，二分查找只适用于顺序存储结构。于顺序存储结构。1-) 1(log1) 1(log12.2221 1221110nnnnknCPASLnikiibn)logO(2n14IDi存放第存放第 i 块中的最大关键字块中的最大关键字及该块在查找表中的起始位置。由于表及该块在查找表中的起始位置。由于表Rn分块有序，分块有序，所以索引表所以索引表递增有序。递增有序。133920334244386080744986532212171322488624481 2 3 4 5 6 7
5、8 9 10 11 12 13 14 15 16 17 18 15首先查找索引表首先查找索引表ID ，以确定待查结点在哪一分块，以确定待查结点在哪一分块 (由于索引项按关键码字有序，可用顺序或折半查找由于索引项按关键码字有序，可用顺序或折半查找)然后，在已确定的那一块中进行顺序查找。然后，在已确定的那一块中进行顺序查找。数据结构定义：数据结构定义：长度为长度为 n 的查找表采用顺序表：的查找表采用顺序表： SSTable ST索引表的结构索引表的结构 typedef struct /* 索引表结点结构索引表结点结构 */ keytype key; int addr; IDtable; IDta
6、bel IDb; /* 索引表索引表 */16 分块查找由分块查找由索引表查找索引表查找和和子表查找子表查找两步完成，故两步完成，故整个算法的平均查找长度是两次查找的平均查找长整个算法的平均查找长度是两次查找的平均查找长度之和。度之和。 ASL=ASL索引表索引表+ASL子表子表 设查找表长为设查找表长为 n, 分为分为 b个子表个子表, 每块中均有每块中均有s = n/b 个元素个元素 若用若用二分查找二分查找来确定块，则分块查找的平均查找长度来确定块，则分块查找的平均查找长度约为：约为： 若用若用顺序查找顺序查找来确定块，则分块查找的平均查找长度来确定块，则分块查找的平均查找长度约为：约为
7、： 对于后一种情况，当对于后一种情况，当 时，平均查找长度为极小时，平均查找长度为极小值。在实用中，可根据表的具体情况进行分块。值。在实用中，可根据表的具体情况进行分块。2/ ) 1(1)/1 (log2ssn)2/()2(2/ ) 1(2/ ) 1(2snsssbns 17 分块查找的性能介于顺序查找和二分查找之间分块查找的性能介于顺序查找和二分查找之间，例如对长度为例如对长度为10000的线性表的线性表,它们的平均查找长度它们的平均查找长度分别是分别是: 顺序查找：顺序查找：ASL=(n+1)/2=5000 分块查找：分块查找：ASL= log2(b+1)-1+ (S+1) /2 57 或
8、或 ASL= (b+1)/2+ (S+1)/2 = 101 二分查找：二分查找：ASL=log2(n+1)-1 14 优点：优点：把线性表分成若干逻辑子表，提高了查找把线性表分成若干逻辑子表，提高了查找效率效率 缺点：缺点：增加了一索引存储空间，和将初始表进行增加了一索引存储空间，和将初始表进行分块的运算分块的运算181) 定义定义: 2) 存储结构存储结构: 二叉链表二叉链表19203) 二叉排序树上的查找算法二叉排序树上的查找算法21 二叉搜索树的搜索二叉搜索树的搜索 插入新结点插入新结点8822 查找过程走了一条从根到该元素结点路径，比较查找过程走了一条从根到该元素结点路径，比较次数等于
9、该结点所在层次数。其中次数等于该结点所在层次数。其中: Pi 查找某元素的概率查找某元素的概率, 等概率情况下等概率情况下 1/n Ci 该元素结点在二叉排序树中的层次该元素结点在二叉排序树中的层次数数 最坏情况最坏情况: 单支树单支树(树的高度达到最大树的高度达到最大) ASL=(n+1)/2 最好情况最好情况: 与二叉判定树相似与二叉判定树相似 ASL=log2(n+1)-1 平均：平均：O(nlog2n)1231111322233234) 查找分析查找分析niiiCPASL1235) 二叉排序树的插入二叉排序树的插入246）二叉排序树的删除）二叉排序树的删除2526SQPLP中序遍历：中
10、序遍历：Q S PL PSQPL中序遍历：中序遍历：Q S PL(2)SPPLQ中序遍历：中序遍历：PL P S QSPLQ中序遍历：中序遍历：PL S Q(1)27SQPRP中序遍历：中序遍历： Q S P PRSQPR中序遍历：中序遍历：Q S PR(4)SPPRQ中序遍历：中序遍历：P PR S QSPRQ中序遍历：中序遍历：PR S Q(3)中序遍历：中序遍历：CL C QL Q SL S P PR FFPCPRCLQQLSSLFSCPRCLQQLSL中序遍历：中序遍历：CL C QL Q SL S PR F(6)中序遍历：中序遍历：CL C PR F(5)中序遍历：中序遍历：CL C
11、 P PR FFCCLPRQQLSFPCPRCLQQLS291） AVL树的定义树的定义 30312) 如何构造平衡二叉排序树如何构造平衡二叉排序树32(a) (b) (c)h+1hhhACEBDhBACEDhhh+1CEABDh33EhhhACEBD(a) (b) (c)hhh+1BACEDhhh+1CABD34插入插入3536内存内存E.G: 用二叉树组织文件，当文件的记录个数为用二叉树组织文件，当文件的记录个数为 100000时时,要找到给定关键字的记录，需访问外存要找到给定关键字的记录，需访问外存17次次(log100000)502510751535609020304055708095
12、索索引引文文件件数数据据文文件件文件头，可常驻内存文件头，可常驻内存371，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第第 1 层层第第 2 层层第第 3 层层(L层层)第第 4 层层(L1层层)39 一棵一棵 5 阶的阶的 B- 树树 2 3 7 2 20 25 3 79 84 93 4 35 41 51 53 2 66 68 2 71 762 12 302 69 781 54tF F FFF FFFF FFF F FFF FFF FFabcdeghfi 4041 2 3 7 2 20 25 3 79 84 93 4 35 41 51 53 2 66 68 2 71 762 12 302 69 781 54tF F FFF FFFF FFF F FFF FFF FFabcdeghfi42434445464748 b) 495051525354555657585960 一棵一棵 4 阶的阶的B+树树 68 78 9320 253 7 84 9335 41 51 5366 6871 787 25 5353 93rootsqt 616263646566676869707172737475767778798081mn哈哈希希表表长长度度记记录录数数表表中中已已装装 入的 82 8384
