《计算机统考重难点班讲义(数据结构）-第四讲.ppt》由会员分享，可在线阅读，更多相关《计算机统考重难点班讲义(数据结构）-第四讲.ppt（44页珍藏版）》请在三一文库上搜索。
1、数据结构 重难点串讲,讲师：翔高教育一级培训师 地点：上海,第6章 查找,重难点导航,静态查找表：顺序表、有序表和索引顺序表 动态查找表：二叉排序树、平衡二叉树 哈希表以及解决冲突的方法,3,查找性能的评价指标： 平均查找长度ASL: 在查找过程中，给定值K与关键字比较次数的期望值,n -查找表中记录个数 Ci-查找到第i条记录时，K与关键字的比较次数 Pi-查找第i条记录的概率,顺序查找思想： 从表的一端开始，逐个将给定值K与关键字进行比较，直到找到记录或查找失败； 注意：这里“顺序”的含义不是查找表是顺序存储的，而是顺着表的自然次序逐个比较。,查找效率： 查找成功时的ASL：,查找失败时的
2、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,7
3、7,81,79,举例：K39,K33 low=mid+1,K56 high=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/1
4、4,n=13,折半查找的ASL 设: n=2h-1-折半查找判定树是高为h的满二叉树 h=log2(n+1),折半查找小结,一种效率很高的查找方法，时间复杂度O(log2n) 对表有严格的限制：有序的顺序表； 折半查找判定树是分析查找性能的有效工具，查找每个结点所需的比较次数等于该结点在树上的层次数； 折半查找判定树是一棵理想平衡二叉树，树的高度为log2n+1； 无论查找成功或失败，与关键字的最大比较次数都不会超过树的高度。,二叉排序树的查找,给定值K， 当 Kkey: 在bt的左子树上继续查找 当 Kbt-key: 在bt的右子树上继续查找 当 K=bt-key: 查找成功,查找分析： 查
5、找成功时： ASL(1122344351) /11 = 34/11 查找失败时： ASL(354552) /12 = 45/12 ASL值与树的形态有关,构造散列函数时的几点要求： 散列函数的定义域必须包括需要存储的全部关键码；散列函数的值域必须在 0到m-1 之间（m是散列表的容量）。 散列函数计算出来的地址应均匀分布在整个地址空间中：若 key是从关键字集合中随机抽取的一个关键字，散列函数应能以同等概率取0到m-1 中的每一个值。 散列函数应是简单的，能在较短的时间内计算出结果。,处理冲突的方法 思路： 设在哈希值H0H(Ri.key)上发生了冲突，我们要为Ri另找一个空闲的地址存放 开放
6、定址法 拉链法 再哈希法 建公共溢出区法,增量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,用不同的
7、方法溢出处理冲突时散列表的平均查找长度如图所示,各种方法处理溢出时的平均查找长度,经典例题分析,【例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，下标
8、从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之前； 经排序后若R
9、i的位置仍然排列在Rj之前，则是稳定排序 若不能保证这一点则是非稳定排序算法。,排序方法： 插入排序 直接插入排序、折半插入排序、2路插入排序 希尔排序 交换排序 冒泡排序、快速排序 选择排序 简单选择排序、堆排序 归并排序 2路归并排序 基数排序,直接插入排序算法思想：,排序区间R1.n； 在排序的过程中，整个排序区间被分为两个子区间： 有序区R1.i-1和无序区Ri.n； 共进行n1趟排序，每趟排序都是把无序区的第一条记录Ri插到有序区的合适位置上。,直接插入排序性能分析： 最好的情况：表的初态恰好是正序排列 比较次数： 移动次数：Mmin0 最坏的情况：表的初态恰好是逆序排列 比较次数：
10、 移动次数：,等概条件下平均情况：,平均比较次数：,平均移动次数：,时间复杂度：O(n2),直接插入排序是一种稳定的排序方法,希尔排序算法思想：,在排序的过程中，整个排序区间被分为几个子表; 对每个子表分别进行直接插入排序 由于n2n12+n22+nk2 ( n=n1+n2+nk ) 所以对每个子表排序所耗费的时间之和要小于对整个区间排序所耗费的时间 通过对子表小范围的排序,将排序区间调整成基本有序的序列; 不断减少子表的个数(即扩大子表的长度), 直至子表的个数为1, 完成整个排序操作.,冒泡排序( Bubble Sort ) 自下而上(或上而下)扫描记录序列， 相邻的两条记录Ri与Ri1(
11、或Ri+1)如果是逆序， 则交换位置,冒泡排序性能分析： 最好的情况：表的初态恰好是正序排列，第一趟扫描 没有移动发生 比较次数：Cminn-1 移动次数：Mmin0 最坏的情况：表的初态恰好是逆序排列，需要进行n-1趟排序，每趟都要移动整个区间 比较次数： 移动次数：,等概条件下平均情况：,平均比较次数：,平均移动次数：,时间复杂度：O(n2),冒泡排序是一种稳定的排序方法,快速排序算法思想 设排序区间为R low . . high ； 在排序区间任选一个记录Rx做为基准； 经过一趟排序后，将排序区间分为左、右两个子区间： R low . . i-1 Rx R i+1 . . high 使得
12、：R low. .i-1 .key Rx.keyR i+1. .high .key 然后再用相同的方法分别对左、右区间进行排序，直至每个区间长度都是1为止。,快速排序性能分析： 最坏的情况：表的初态恰好是正序或逆序排列。每次 分区时，基准都恰好是区间的最大或最小键值，分区的结果是有一个区间为空:,对于初态是正序或逆序排列的表，需要进行n1趟排序，每趟要进行ni次比较: 快速排序退化成冒泡排序，时间复杂度达到O(n2).,最好的情况：每次分区时，基准都恰好是区间的中间 值，分区的结果使得左、右两个区间长度一样，同步地收敛到1。 就平均性能而言，快速排序的时间复杂度是O(nlogn)。 快速排序被
13、认为是所有O(nlogn)级别的排序方法中平均性能最好的。 快速排序由于是递归实现的，需要消耗运行栈的空间,简单选择排序算法思想：,设：排序区间R1.n; 在排序的过程中，整个排序区间被分为两个子区间：有序区R1.i-1和无序区Ri.n; 共进行n1趟排序，每趟排序都是选择无序区的最小记录Rmin；将Rmin与无序区的第一条记录位置互换，使得无序区长度减1，有序区长度增1。,有序区,无序区,简单选择排序性能分析： 比较次数与表的初态无关： 最好的情况：表的初态恰好是正序排列 移动次数：Mmin0 最坏的情况：每趟都有移动发生 移动次数：Mmax3(n-1) 平均O(n2), 不稳定的排序方法,
14、堆排序 以大顶堆为例： 堆顶是排序区间最大的元素 去掉堆顶，将堆顶与堆的最后一个元素交换位置： 最大元素归位； 新树根不满足堆定义，需要通过筛选调整为堆,归并排序(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,