收藏 分销(赏)

重难点-数据结构-第四讲.ppt

上传人:仙人****88 文档编号:14747562 上传时间:2026-11-13 格式:PPT 页数:44 大小:2.83MB 下载积分:10 金币
下载 相关
重难点-数据结构-第四讲.ppt_第1页
第1页 / 共44页
重难点-数据结构-第四讲.ppt_第2页
第2页 / 共44页


点击查看更多>>
资源描述
,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,数据结构,重难点串讲,讲师:翔高教育一级培训师,地点:上海,第,6,章 查找,重难点导航,静态查找表:顺序表、有序表和索引顺序表,动态查找表:二叉排序树、平衡二叉树,哈希表以及解决冲突的方法,3,查找性能的评价指标:,平均查找长度,ASL:,在查找过程中,给定值,K,与关键字比较次数的期望值,n-,查找表中记录个数,Ci,-,查找到第,i,条记录时,,K,与关键字,的比较次数,Pi-,查找第,i,条记录的概率,顺序查找思想:,从表的一端开始,逐个将给定值,K,与关键字进行比较,直到找到记录或查找失败;,注意:,这里,“顺序”,的含义不是查找表是顺序存储的,而是顺着表的自然次序逐个比较。,查找效率:,查找成功时的,ASL,:,查找失败时的,ASL,:,ASL=n+1,平均:,ASL,3(n+1)/4,顺序查找小结:,最朴素的查找方法,对表的限制最少,不仅适用于顺序存储结构,而且适用于链式存储结构,时间性能最差,,O(n,),等概情况下查找成功时,ASL,(n+1)/2,折半查找,(,二分查找,),对表的限制:,1.,顺序存储;,2.,按关键字值有序排列,查找方法:,设查找区间为,R low.high,取,mid,(low+high)/2,,则,当,K,Rmid.key,:下一个查找区间为,R mid+1.High,当,K=,Rmid.key,:查找成功,结束,当,lowhigh,:查找失败,结束,02,16,11,22,25,27,33,42,56,77,81,79,0,1,3,2,4,5,6,8,7,9,10,11,13,12,low,mid,high,举例:,K,39,K33,low=mid+1,mid,K56,high=mid-1,mid,39,经过与关键字,33,56,39,的比较,查找成功,K=39,查找成功,查找成功的过程是自树根沿树枝到达目标结点,,K,与关键字的最大比较次数不超过树高,log2n,+1,7,3,10,1,5,8,12,2,4,6,9,11,13,02,16,11,22,25,27,33,42,56,77,81,79,0,1,3,2,4,5,6,8,7,9,10,11,13,12,39,查找,K,39,:,7,3,10,1,5,8,12,2,4,6,9,11,13,查找成功,:,ASL=(11+22+34+46)/13=41/13,查找失败,:,ASL=(32+412)/14=54/14,n=13,折半查找的,ASL,设,:n=2,h,-1-,折半查找判定树是高为,h,的满二叉树,h=log,2,(n+1),折半查找小结,一种效率很高的查找方法,时间复杂度,O(log,2,n),对表有严格的限制:有序的顺序表;,折半查找判定树是分析查找性能的有效工具,查找每个结点所需的比较次数等于该结点在树上的层次数;,折半查找判定树是一棵理想平衡二叉树,树的高度为,log,2,n,+1,;,无论查找成功或失败,与关键字的最大比较次数都不会超过树的高度。,二叉排序树的查找,给定值,K,,,当,Kkey:,在,bt,的左子树上继续查找,当,K,bt,-key:,在,bt,的右子树上继续查找,当,K=,bt,-key:,查找成功,32,48,26,39,29,56,34,12,44,19,46,bt,查找分析:,查找成功时:,ASL,(11,22,34,43,51)/11=34/11,查找失败时:,ASL,(35,45,52)/12=45/12,ASL,值与树的形态有关,32,48,26,39,29,56,34,12,44,19,46,构造散列函数时的几点要求:,散列函数的定义域必须包括需要存储的全部关键码;散列函数的值域必,须在,0,到,m-1,之间(,m,是散列表的容量)。,散列函数计算出来的地址应均匀分布在整个地址空间中:若,key,是从关键字集合中随机抽取的一个关键字,散列函数应能以同等概率取,0,到,m-1,中的每一个值。,散列函数应是简单的,能在较短的时间内计算出结果。,处理冲突的方法,思路:,设在哈希值,H,0,H(Ri.key,),上发生了冲突,我们要为,Ri,另找一个空闲的地址存放,开放定址法,拉链法,再哈希法,建公共溢出区法,增量,di,的三种取法:,(1),线性探测再散列,di,=1,2,3,m-1,(2),二次探测再散列,di,=1,2,-1,2,2,2,-2,2,k,2,-k,2,(km/2),特别注意:要求表长,m,为形如,4*j+3,的素数,(3),伪随机探测再散列,di,=,伪随机数序列,,说明:,如果,Hi=m,,则,Hi=Hi-m*n;,其中,n,为整数,如果,Hi0,则,Hi=,Hi+m,*n;,其中,n,为整数,思路:,将同义词链接成单链表。,拉链法,key,26,36,41,38,44,15,68,12,06,51,25,H(key,),0,10,2,12,5,2,3,12,6,12,12,0,1,2,3,4,5,6,7,8,9,10,11,12,15,26,41,68,44,06,36,25,51,12,38,拉链法的查找效率:,0,1,2,3,4,5,6,7,8,9,10,11,12,15,26,41,68,44,06,36,25,51,12,38,查找成功时,,ASL,(17,22,3,4)/11=18/11,查找失败时,,ASL,(06,15,2,4)/13=11/13,用不同的方法溢出处理冲突时散列表的平均查找长度如图所示,各种方法处理溢出时的平均查找长度,经典例题分析,【,例,1】,(,10,分)将关键字序列(,7,,,8,,,30,,,11,,,18,,,9,,,14,)散列存储到散列表中,散列表的的存储空间是一个下标从,0,开始的一维数据,散列函数为:,H(key,)=(key3)MOD7,处理冲突采用线性探测再散列法,要求装填,(,载,),因子为,0.7,。,(,1,)请画出所构造的散列表。,(,2,)分别计算等概率情况下查找成功和查找不成功的平均查找长度。,22,(,7,,,8,,,30,,,11,,,18,,,9,,,14,),H(key,)=(key3)MOD7,(,1,)首先根据要求,key3,的装填因子,0.7,,得出所构造的散列表的长度为,10,,下标从,0,到,9,。根据题目所给的散列函数和冲突所采用的线性探测再散列法。,所构造的散列表如下:,23,下标,0,1,2,3,4,5,6,7,8,9,关键字,7,14,8,11,30,18,9,查找成功时探查次数分别如下表所示:,在等概率条件下,查找成功的平均查找长度为:(,14+32+2,),/7=12/7,。,在等概率条件下,查找不成功的各位置对应的探查次数如下表:,查找不成功的平均查找长度为:(,3+2+1+2+1+5+4,),=18/7,24,关键字,7,8,30,11,18,9,14,散列地址,0,3,6,5,5,6,0,探查次数,1,1,1,1,3,3,2,下标,0,1,2,3,4,5,6,探查次数,3,2,1,2,1,5,4,第,7,章内部排序,25,重难点导航,各种排序算法的比较以及特点,各种排序算法时间复杂度的计算,以及最好和最坏性能分析,堆排序算法的思想和原理,26,排序法,平均时间,最差情形,稳定度,额外空间,备注,冒泡,O(n,2,),O(n,2,),稳定,O(1),n,小时较好,交换,O(n,2,),O(n,2,),不稳定,O(1),n,小时较好,选择,O(n,2,),O(n,2,),不稳定,O(1),n,小时较好,插入,O(n,2,),O(n,2,),稳定,O(1),大部分已排序时较好,基数,O(log,R,B,),O(log,R,B),稳定,O(n),B,是真数,(0-9),,,R,是基数,(,个十百,),Shell,O(nlogn),O(n,s,)1sn,1,2,+n,2,2,+n,k,2,(n=n,1,+n,2,+n,k,),所以对每个子表排序所耗费的时间之和要小于对整个区间排序所耗费的时间,通过对子表小范围的排序,将排序区间调整成基本有序的序列,;,不断减少子表的个数,(,即扩大子表的长度,),直至子表的个数为,1,完成整个排序操作,.,冒泡排序,(Bubble Sort),自下而上,(,或上而下,),扫描记录序列,,相邻的两条记录,R,i,与,R,i,1,(,或,R,i+1,),如果是逆序,,则交换位置,冒泡排序性能分析:,最好的情况:,表的初态恰好是正序排列,第一趟扫描,没有移动发生,比较次数:,Cmin,n-1,移动次数:,Mmin,0,最坏的情况,:,表的初态恰好是逆序排列,需要进行,n-1,趟排序,每趟都要移动整个区间,比较次数:,移动次数:,等概条件下平均情况:,平均比较次数:,平均移动次数:,时间复杂度:,O(n,2,),冒泡排序是一种,稳定的,排序方法,快速排序算法思想,设排序区间为,R low.high,;,在排序区间任选一个记录,Rx,做为基准;,经过一趟排序后,将排序区间分为左、右两个子区间:,R low.i-1,Rx,R i+1.high,使得:,R low.i-1.key,Rx.key,R i+1.high.key,然后再用相同的方法分别对左、右区间进行排序,直至每个区间长度都是,1,为止。,快速排序性能分析:,最坏的情况:表的初态恰好是正序或逆序排列。每次,分区时,基准都恰好是区间的最大或最小键值,分区的结果是有一个区间为空,:,对于初态是正序或逆序排列的表,需要进行,n,1,趟排序,每趟要进行,n,i,次比较,:,快速排序退化成冒泡排序,时间复杂度达到,O(n,2,).,最好的情况:每次分区时,基准都恰好是区间的中间,值,分区的结果使得左、右两个区间长度一样,同步地收敛到,1,。,就平均性能而言,快速排序的时间复杂度是,O(nlogn),。,快速排序被认为是所有,O(nlogn),级别的排序方法中平均性能最好的。,快速排序由于是递归实现的,需要消耗运行栈的空间,简单选择排序算法思想:,设:排序区间,R1.n;,在排序的过程中,整个排序区间被分为两个子区间:有序区,R1.i-1,和无序区,Ri.n;,共进行,n,1,趟排序,每趟排序都是选择无序区的最小记录,R,min,;将,R,min,与无序区的第一条记录位置互换,使得无序区长度减,1,,有序区长度增,1,。,R,R,1,R,2,R,i-1,R,i,R,i+1,R,n-1,R,n,0,1,2,i-1,i,i+1,n-1,n,有序区,无序区,简单选择排序性能分析:,比较次数与表的初态无关:,最好的情况:表的初态恰好是正序排列,移动次数:,M,min,0,最坏的情况:每趟都有移动发生,移动次数:,M,max,3(n-1),平均,O(n,2,),不稳定的排序方法,堆排序,以大顶堆为例:,堆顶是排序区间最大的元素,去掉堆顶,将堆顶与堆的最后一个元素交换位置:,最大元素归位;,新树根不满足堆定义,需要通过筛选调整为堆,归并排序,(Merging sort),算法思想,:,一种基于将两个有序表异地归并成一个有序表的排序策略。,初态是将排序表中的每个元素看成是一个有序的子表,共有,n,个子表。,经过一趟排序,将两个相邻的有序子表归异地并成一个有序子表;,共进行,log,2,n,趟这样的归并,整个排序表就被归并成了一个有序表。,经典例题分析,【,例,1】,对一组数据(,2,,,12,,,16,,,88,,,5,,,10,)进行排序,若前三者趟排序结果如下:,第一趟排序结果:,2,,,12,,,16,,,5,,,10,,,88,第二趟排序结果:,2,,,12,,,5,,,10,,,16,,,88,第三趟排序结果:,2,,,5,,,10,,,12,,,16,,,88,则采用的排序方法可能是,A.,起泡排序,B.,希尔排序,C.,归并排序,D.,基数排序,【,解析,】,本题考查起泡排序算法的执行过程。第一趟排序后,把最大数,88,放到了最终位置,第二趟排序后,把次大的,16,放到了最终位置,显然是起泡排序。,44,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 教育专区 > 其他

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服