计算机统考重难点班讲义数据结构第四讲.ppt
数据结构重难点串讲,讲师：翔高教育一级培训师地点：上海,乔悼懦氖傈邱坠礼款跨典茫战睬猖娘重小负箩票兰糊棚洋垦正则袁慷穿壳计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,第6章 查找,络优氯诗姐尔汲晰胃潜叁渣塌敞臃莆晓醒钞厩购抖喧棋臼麦拇贤养绦街斧计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,重难点导航,静态查找表：顺序表、有序表和索引顺序表动态查找表：二叉排序树、平衡二叉树哈希表以及解决冲突的方法,3,碘毒靖臆野至燕舵缆退镶重嘎石硫侈宝倡戏精祁奥核砂吸除验际妥储卿贰计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,查找性能的评价指标：平均查找长度ASL:在查找过程中，给定值K与关键字比较次数的期望值,n-查找表中记录个数Ci-查找到第i条记录时，K与关键字的比较次数Pi-查找第i条记录的概率,臣婚钎职摆欲速界绦刻为谢洼砍蠢硼绳蝴厄卿傍侄用铜姑绩藉过芒冰疏编计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,顺序查找思想：从表的一端开始，逐个将给定值K与关键字进行比较，直到找到记录或查找失败；注意：这里“顺序”的含义不是查找表是顺序存储的，而是顺着表的自然次序逐个比较。,长姐矫丘脏嘛醋棵痈砧碧孽位卯熊备咏娥饱象嗡掇浩阴揉比屑哨纳榨铀奔计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,查找效率：查找成功时的ASL：,查找失败时的ASL：ASL=n+1平均：ASL3(n+1)/4,却诸涝今搂自简陕镭寞擒霖试劫崇准硫抱沥搂匠宙姬驾匈杉阵烃温扼稿毋计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,顺序查找小结：,最朴素的查找方法对表的限制最少不仅适用于顺序存储结构，而且适用于链式存储结构时间性能最差，O(n)等概情况下查找成功时ASL(n+1)/2,侧凳颜阅此信殊蛔贯行淬吭钉缉邑屹凉受镇蟹烁段部鸡藏梢展锹回浑鬼囊计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,折半查找(二分查找),对表的限制：1.顺序存储；2.按关键字值有序排列查找方法：设查找区间为R low.high 取mid(low+high)/2，则 当KRmid.key：下一个查找区间为 R mid+1.High 当K=Rmid.key：查找成功，结束 当lowhigh：查找失败，结束,堑杖边拭艺序捧蔑谈盎湛瞬示嚼洽罪洼羽决鼻蘸拭铃衅呈猖隙呛盆弯伎像计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,02,16,11,22,25,27,33,42,56,77,81,79,举例：K39,K33low=mid+1,K56high=mid-1,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,39,查找K39：,腻敷拇秸齐夺铬僧哀橇斥蓬佣刷除超若拾啼添眠鸭亩均轴炕痪蓄访缀啪抡计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,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=2h-1-折半查找判定树是高为h的满二叉树 h=log2(n+1),骡关署捻币笛依忆樱计把蝇坚宦芯辈泞辨的淮汹丸帐别昭乃委扎鞋狐暖颁计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,折半查找小结,一种效率很高的查找方法，时间复杂度O(log2n)对表有严格的限制：有序的顺序表；折半查找判定树是分析查找性能的有效工具，查找每个结点所需的比较次数等于该结点在树上的层次数；折半查找判定树是一棵理想平衡二叉树，树的高度为log2n+1；无论查找成功或失败，与关键字的最大比较次数都不会超过树的高度。,铭醉猾切酮桥维敷适兰凶撩畅闸唇兽龋糊涟祁政踢埔丰掌吉豌憎袍尾分朗计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,二叉排序树的查找,给定值K，当 Kkey:在bt的左子树上继续查找当 Kbt-key:在bt的右子树上继续查找当 K=bt-key:查找成功,柳乡掖牢迂卷诣现苑炽子怎戳骂磕擅呛杠蜕彦诛府僵辫殉机免麦棒尚钨承计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,查找分析：查找成功时：ASL(1122344351)/11=34/11查找失败时：ASL(354552)/12=45/12 ASL值与树的形态有关,筑纲虐淹懒彤疥疲尖撞斥阴辛锐锌茁武妨宜高眷女志哦劫甫若拦淳铣劈狮计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,构造散列函数时的几点要求：散列函数的定义域必须包括需要存储的全部关键码；散列函数的值域必须在 0到m-1 之间（m是散列表的容量）。散列函数计算出来的地址应均匀分布在整个地址空间中：若 key是从关键字集合中随机抽取的一个关键字，散列函数应能以同等概率取0到m-1 中的每一个值。散列函数应是简单的，能在较短的时间内计算出结果。,久寇浅娥吕鸭靛障衅某戴务鉴拐剩雌堤钨增森侣呛铂雌炯慨峦炙怯睫渍肥计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,处理冲突的方法思路：设在哈希值H0H(Ri.key)上发生了冲突，我们要为Ri另找一个空闲的地址存放开放定址法拉链法再哈希法建公共溢出区法,干夺至泅文丸叫喜扬纺升者镁芭驱厄懂曹秩粒掏卡檀川彤旬漓隙孟份讲介计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,增量di的三种取法：(1)线性探测再散列di=1,2,3,m-1(2)二次探测再散列di=12,-12,22,-22,k2,-k2(km/2)特别注意：要求表长m为形如4*j+3的素数(3)伪随机探测再散列 di=伪随机数序列，说明：如果Hi=m，则Hi=Hi-m*n;其中n为整数如果Hi0,则Hi=Hi+m*n;其中n为整数,隔遣掳骨堪拾邱栈拂适耽旅筋堤闺搜囤绎渗芍陨畏帝奢砌寥鹏纱恋衍辫焚计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,思路：将同义词链接成单链表。,拉链法,卯包矮使花配旱瑰废跃竟赘宗狼场暖汞牺冗墒翰堤觉执转劣羊苟剁桌朔痘计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,拉链法的查找效率：,查找成功时，ASL(172234)/11=18/11查找失败时，ASL(061524)/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,囤大规麓缨亚赘漫斋滋赞侩重储阻业芋谤猜泅髓咎饼乖玻佃盒佳缚攒伤龚计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,查找成功时探查次数分别如下表所示：在等概率条件下，查找成功的平均查找长度为：（14+32+2）/7=12/7。在等概率条件下，查找不成功的各位置对应的探查次数如下表：查找不成功的平均查找长度为：（3+2+1+2+1+5+4）=18/7,24,港默褂肇农邪击忘局助施帜菩替龙欢偶喝芦灰秤贡睡菇弃害煤垃十歧胁蹲计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,第7章内部排序,25,胸升士墓菏噎谊巳喝段说凸迎慰圃迢哭精母筛隆膝篮呼颅闷班载衙骋票体计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,重难点导航,各种排序算法的比较以及特点各种排序算法时间复杂度的计算，以及最好和最坏性能分析堆排序算法的思想和原理,26,往痛乐印削边泪掩殷胰簿愉烷函东撕姬酵纽敏雇全煞栋磐殊蓟嗜玻螺兼堰计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,27,硅韭韭稠奎坟碎承仟柔窿郑丽佬蕊窍生芋翌斜筐焕川突助贝窗阜欣账肇刚计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,稳定排序与非稳定排序：设：Ri.key=Rj.key 假设排序前Ri的位置排列在Rj之前；经排序后若Ri的位置仍然排列在Rj之前，则是稳定排序若不能保证这一点则是非稳定排序算法。,酷宙映申凰毁僳钥翻戚夏咎洼秤衣轨慑丈待跨己脏盂挪累红闭微夹案椽赠计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,排序方法：插入排序 直接插入排序、折半插入排序、2路插入排序希尔排序 交换排序 冒泡排序、快速排序 选择排序 简单选择排序、堆排序 归并排序 2路归并排序 基数排序,肝贮氏赋碗揭骡谦歹锤橙唯主蹿篆傻军屡手镍困卜垢期怎档综译腆扮举纲计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,直接插入排序算法思想：,排序区间R1.n；在排序的过程中，整个排序区间被分为两个子区间：有序区R1.i-1和无序区Ri.n；共进行n1趟排序，每趟排序都是把无序区的第一条记录Ri插到有序区的合适位置上。,东断钩略勘眩疽雁狙栓叭广催赎畦祈淹超肠惧霖秧酗脸奔狂原擎宜恐泥棕计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,直接插入排序性能分析：最好的情况：表的初态恰好是正序排列 比较次数：移动次数：Mmin0最坏的情况：表的初态恰好是逆序排列 比较次数：移动次数：,趣遏龄山蝶扇侨踊雇凸裤糟恿痕穗搁鹊搁试尉狮贴谋端篇渐藻辊堤蔼隆嚷计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,等概条件下平均情况：,平均比较次数：,平均移动次数：,时间复杂度：O(n2),直接插入排序是一种稳定的排序方法,悟忻脯柔淌蔷作糕冯沧炉殷谆沙呸堰侣盾倦股棉嘉跌园壕脏栅淤谤况蒙锭计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,希尔排序算法思想：,在排序的过程中，整个排序区间被分为几个子表;对每个子表分别进行直接插入排序由于n2n12+n22+nk2(n=n1+n2+nk)所以对每个子表排序所耗费的时间之和要小于对整个区间排序所耗费的时间通过对子表小范围的排序,将排序区间调整成基本有序的序列;不断减少子表的个数(即扩大子表的长度),直至子表的个数为1,完成整个排序操作.,洒逸现狡栖措衙庭课盏桶腿轮壬靠芝母哟补踞孜醇摘屋防宁螟绞肥返睁胺计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,冒泡排序(Bubble Sort)自下而上(或上而下)扫描记录序列，相邻的两条记录Ri与Ri1(或Ri+1)如果是逆序，则交换位置,甩回靡篆锤狗笔寐旋功喧谱帐败钞艇捏润斜颠灸痈拴跨诸利所铃匿师牧秉计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,冒泡排序性能分析：最好的情况：表的初态恰好是正序排列，第一趟扫描没有移动发生 比较次数：Cminn-1 移动次数：Mmin0最坏的情况：表的初态恰好是逆序排列，需要进行n-1趟排序，每趟都要移动整个区间 比较次数：移动次数：,谋捅奄跑颜躺辰语被斯烷恐留咯末盯锦托镜月宏惮哈沙蓄岸赎烘习往顾存计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,等概条件下平均情况：,平均比较次数：,平均移动次数：,时间复杂度：O(n2),冒泡排序是一种稳定的排序方法,棱床桥妙究佐晒剿共横厨皆绳坛命殿势逃犹壬讲伊暇从泻胎啡释菊咆嘶脚计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,快速排序算法思想设排序区间为R low.high；在排序区间任选一个记录Rx做为基准；经过一趟排序后，将排序区间分为左、右两个子区间：R low.i-1 Rx R i+1.high 使得：R low.i-1.key Rx.keyR i+1.high.key然后再用相同的方法分别对左、右区间进行排序，直至每个区间长度都是1为止。,钒悍烹崎骑紧猖屠颖镜酣筛透妨栅挺椅弟彬祝网昧宠缆谐萄垣船牛慕却岩计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,快速排序性能分析：最坏的情况：表的初态恰好是正序或逆序排列。每次分区时，基准都恰好是区间的最大或最小键值，分区的结果是有一个区间为空:,对于初态是正序或逆序排列的表，需要进行n1趟排序，每趟要进行ni次比较:快速排序退化成冒泡排序，时间复杂度达到O(n2).,郴弊耀虎妨昧羌饵扬佩椒剁荆尝踞姥锄弘惋拟脏贾乳姆乙麻双否祷割盎市计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,最好的情况：每次分区时，基准都恰好是区间的中间值，分区的结果使得左、右两个区间长度一样，同步地收敛到1。就平均性能而言，快速排序的时间复杂度是O(nlogn)。快速排序被认为是所有O(nlogn)级别的排序方法中平均性能最好的。快速排序由于是递归实现的，需要消耗运行栈的空间,渣狠蹦埂斤艳载蒂鸟讹皋腰纹适舌受邦奢捏竿惶琉辉赵顿急搭缓祷虞天巨计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,简单选择排序算法思想：,设：排序区间R1.n;在排序的过程中，整个排序区间被分为两个子区间：有序区R1.i-1和无序区Ri.n;共进行n1趟排序，每趟排序都是选择无序区的最小记录Rmin；将Rmin与无序区的第一条记录位置互换，使得无序区长度减1，有序区长度增1。,有序区,无序区,冻嫂瘴驰舍歧羹舜芦唬拘某拍亩子瓮酬拴择揉拟纳河伯青汾牧晦松浦竹扫计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,简单选择排序性能分析：比较次数与表的初态无关：最好的情况：表的初态恰好是正序排列 移动次数：Mmin0最坏的情况：每趟都有移动发生 移动次数：Mmax3(n-1)平均O(n2),不稳定的排序方法,炸适钾毁内倪专政济煽慨昼盲劳护诉彩貌于选控傣眼速闹冠妇屉吊趾奉继计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,堆排序以大顶堆为例：堆顶是排序区间最大的元素去掉堆顶，将堆顶与堆的最后一个元素交换位置：最大元素归位；新树根不满足堆定义，需要通过筛选调整为堆,责扔擎淬嫩贞饱择眷咒烯羚外昌首姓晦座爱伴乱迟诀唯砖阅易暑礼硝爽铲计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,归并排序(Merging sort)算法思想:一种基于将两个有序表异地归并成一个有序表的排序策略。初态是将排序表中的每个元素看成是一个有序的子表，共有n个子表。经过一趟排序，将两个相邻的有序子表归异地并成一个有序子表；共进行log2n趟这样的归并，整个排序表就被归并成了一个有序表。,信妹馋训写汉纂款正滓适蹄装前将陈茂宵榔报横禽狡颜曼肘迪好穗矿歼意计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,经典例题分析,【例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,歹巷睬酪嘱积姚举剑棠蹬庚尤慧爱呜畜派叁磨剖偷富嫩狸偶窒奇隧哲搓撵计算机统考重难点班讲义(数据结构）-第四讲计算机统考重难点班讲义(数据结构）-第四讲,
