计算机统考重难点班讲义数据结构-第四讲

1、数据结构数据结构重难点串讲重难点串讲讲师：翔高教育一级培训师地点：上海第第6章章 查找查找重难点导航重难点导航v 静态查找表：顺序表、有序表和索引顺序表静态查找表：顺序表、有序表和索引顺序表v 动态查找表：二叉排序树、平衡二叉树动态查找表：二叉排序树、平衡二叉树v 哈希表以及解决冲突的方法哈希表以及解决冲突的方法3查找性能的评价指标：查找性能的评价指标：平均查找长度平均查找长度asl:asl: 在查找过程中，给定值在查找过程中，给定值k k与关与关键字比较次数的期望值键字比较次数的期望值 nipiciasl1n -n -查找表中记录个数查找表中记录个数ci-ci-查找到第查找到第i i条记录时

2、，条记录时，k k与关键字与关键字的比较次数的比较次数pi-pi-查找第查找第i i条记录的概率条记录的概率 顺序查找思想：顺序查找思想： 从表的一端开始，逐个将给定值从表的一端开始，逐个将给定值k k与关键字进行与关键字进行比较，直到找到记录或查找失败；比较，直到找到记录或查找失败；注意：注意：这里这里“顺序顺序”的含义不是查找表是顺序存储的的含义不是查找表是顺序存储的，而是顺着表的自然次序逐个比较。，而是顺着表的自然次序逐个比较。查找效率：查找效率：8查找成功时的查找成功时的asl：nininninpiciasl11211) 1(8 查找失败时的asl： asl=n+18 平均：asl3(

3、n+1)/4顺序查找小结：顺序查找小结：c最朴素的查找方法最朴素的查找方法c对表的限制最少对表的限制最少c不仅适用于顺序存储结构，而且适用于链式存不仅适用于顺序存储结构，而且适用于链式存储结构储结构c时间性能最差，时间性能最差，o(n) o(n) c等概情况下查找成功时等概情况下查找成功时aslasl(n+1)/2(n+1)/2折半查找折半查找(二分查找二分查找)c对表的限制：对表的限制： 1.1. 顺序存储；顺序存储； 2.2. 按关键字值有序排列按关键字值有序排列c查找方法：查找方法： 设查找区间为设查找区间为r low . . high 取取mid (low+high)/2 ，则，则 当

4、当krmid.key： 下一个查找区间为下一个查找区间为 r mid+1. . high 当当k=rmid.key： 查找成功，结束查找成功，结束 当当lowhigh： 查找失败，结束查找失败，结束021611222527334256778179013245687910111312lowmidhigh举例：k39k33low=mid+1midk56high=mid-1mid39经过与关键字33, 56, 39的比较，查找成功k=39查找成功 查找成功的过程是自树根沿树枝到达目标结点，k与关键字的最大比较次数不超过树高log2n+173101581224691113021611222527334

5、25677817901324568791011131239查找查找k k3939：73101581224691113查找成功: asl=(11+22+34+46) /13=41/13查找失败: asl=(32 + 412) / 14 = 54/14n=13折半查找的折半查找的aslasl 设设: n=2h-1-折半查找判定树是高为折半查找判定树是高为h h的满二的满二叉树叉树 h=log2(n+1) hjjnijnpiciasl111211) 1(log1) 1(log1122nnnnsnasl折半查找小结折半查找小结8 一种效率很高的查找方法，时间复杂度一种效率很高的查找方法，时间复杂度o(

6、logo(log2 2n)n)8 对表有严格的限制：有序的顺序表；对表有严格的限制：有序的顺序表；8 折半查找判定树是分析查找性能的有效工具，查折半查找判定树是分析查找性能的有效工具，查找每个结点所需的比较次数等于该结点在树上的找每个结点所需的比较次数等于该结点在树上的层次数；层次数；8 折半查找判定树是一棵理想平衡二叉树，树的高折半查找判定树是一棵理想平衡二叉树，树的高度为度为 loglog2 2n n +1+1；8 无论查找成功或失败，与关键字的最大比较次数无论查找成功或失败，与关键字的最大比较次数都不会超过树的高度。都不会超过树的高度。二叉排序树的查找二叉排序树的查找给定值给定值k k，

7、当当 kkey: 在在bt的左子树上继续查找的左子树上继续查找当当 kbt-key: 在在bt的右子树上继续查找的右子树上继续查找当当 k=bt-key: 查找成功查找成功3248263929563412441946bt查找分析：查找成功时：查找成功时： asl(1122344351) /11 = 34/11查找失败时：查找失败时： asl(354552) /12 = 45/12 asl值与树的形态有关3248263929563412441946构造散列函数时的几点要求：构造散列函数时的几点要求：须在须在 0到到m-1 之间（之间（m是散列表的容量）。是散列表的容量）。2. 散列函数计算出来的

8、地址应均匀分布在整个地址散列函数计算出来的地址应均匀分布在整个地址空间中：若空间中：若 key是从关键字集合中随机抽取的是从关键字集合中随机抽取的一个关键字，散列函数应能以同等概率取一个关键字，散列函数应能以同等概率取0到到m-1 中的每一个值。中的每一个值。3. 散列函数应是简单的，能在较短的时间内计算出散列函数应是简单的，能在较短的时间内计算出结果。结果。处理冲突的方法思路： 设在哈希值设在哈希值h0h(ri.key)上发生了冲突，我们要为上发生了冲突，我们要为ri另另找一个空闲的地址存放找一个空闲的地址存放1.开放定址法2.拉链法3.再哈希法4.建公共溢出区法增量增量di的三种取法：的三

9、种取法：(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为整数为整数思路：思路：将同义词链接成单链表。将同义词链接成单链表。拉链法拉链法keyh(key)260361041238124451526831212066

10、5112251201234567891011121526 41 68 44 06 36 25511238 拉链法的查找效率：拉链法的查找效率：01234567891011121526 41 68 44 06 36 25511238 查找成功时，asl(172234) / 11 = 18 / 11查找失败时，asl(061524) / 13 = 11 / 13用不同的方法溢出处理冲突时散列表的平均查找长度如用不同的方法溢出处理冲突时散列表的平均查找长度如图所示图所示各种方法处理溢出时的平均查找长各种方法处理溢出时的平均查找长度度经典例题分析经典例题分析v 【例【例1】（】（10分）将关键字序列（

11、分）将关键字序列（7，8，30，11，18，9，14）散列存储到散列表中）散列存储到散列表中,散列表的的散列表的的存储空间是一个下标从存储空间是一个下标从0开始的一维数据开始的一维数据,散列函数散列函数为：为：h(key)=(key3)mod7,处理冲突采用线处理冲突采用线性探测再散列法性探测再散列法,要求装填要求装填(载载)因子为因子为0.7。v （1） 请画出所构造的散列表。请画出所构造的散列表。v （2） 分别计算等概率情况下查找成功和查找不成分别计算等概率情况下查找成功和查找不成功的平均查找长度。功的平均查找长度。22v （7，8，30，11，18，9，14）v h(key)=(key

12、3)mod7v （1）首先根据要求）首先根据要求key3的装填因子的装填因子0.7，得出，得出所构造的散列表的长度为所构造的散列表的长度为10，下标从，下标从0到到9。根据。根据题目所给的散列函数和冲突所采用的线性探测再散题目所给的散列函数和冲突所采用的线性探测再散列法。列法。v 所构造的散列表如下：所构造的散列表如下：23下标0123456789关键字71481130189v 查找成功时探查次数分别如下表所示：查找成功时探查次数分别如下表所示：v 在等概率条件下，查找成功的平均查找长度为：（在等概率条件下，查找成功的平均查找长度为：（14+32+2）/7=12/7。v 在等概率条件下，查找不

13、成功的各位置对应的探查在等概率条件下，查找不成功的各位置对应的探查次数如下表：次数如下表：查找不成功的平均查找长度为：（查找不成功的平均查找长度为：（3+2+1+2+1+5+4）=18/724关键字78301118914散列地址0365560探查次数1111332下标0123456探查次数3212154第第7章内部排序章内部排序25重难点导航重难点导航v 各种排序算法的比较以及特点各种排序算法的比较以及特点v 各种排序算法时间复杂度的计算，以及最好和最坏各种排序算法时间复杂度的计算，以及最好和最坏性能分析性能分析v 堆排序算法的思想和原理堆排序算法的思想和原理26排序法排序法冒泡冒泡交换交换选

14、择选择插入插入基数基数shell快速快速归并归并堆堆平均时间平均时间o(n2)o(n2)o(n2)o(n2)o(logrb)o(nlogn)o(nlogn)o(nlogn)o(nlogn)最差情形最差情形o(n2)o(n2)o(n2)o(n2)o(logrb)o(ns)1sn12+n22+nk2 ( n=n1+n2+nk ) 所以对每个子表排序所耗费的时间之和要小于对整所以对每个子表排序所耗费的时间之和要小于对整个区间排序所耗费的时间个区间排序所耗费的时间8 通过对子表小范围的排序通过对子表小范围的排序,将排序区间调整成基本有将排序区间调整成基本有序的序列序的序列;8 不断减少子表的个数不断减

15、少子表的个数(即扩大子表的长度即扩大子表的长度), 直至子表直至子表的个数为的个数为1, 完成整个排序操作完成整个排序操作.冒泡排序冒泡排序( bubble sort )( bubble sort ) 自下而上自下而上(或上而下或上而下)扫描记录序列，扫描记录序列， 相邻的两条记录相邻的两条记录ri与与ri1(或或ri+1)如果是逆序，如果是逆序， 则交换位置则交换位置冒泡排序性能分析：冒泡排序性能分析：最好的情况：最好的情况：表的初态恰好是正序排列，第一趟扫描表的初态恰好是正序排列，第一趟扫描没有移动发生没有移动发生 比较次数：比较次数：cminn-1 移动次数：移动次数：mmin0最坏的情

16、况最坏的情况：表的初态恰好是逆序排列，需要进行表的初态恰好是逆序排列，需要进行n-1趟排序，每趟都要移动整个区间趟排序，每趟都要移动整个区间 比较次数：比较次数： 移动次数：移动次数：2) 1-(=) 1+-(=max2=nnincni2) 1-(3=3) 1+-(=max2=nninmni等概条件下平均情况：等概条件下平均情况：2minmax ccc平均比较次数：2minmax mmm平均移动次数：时间复杂度：o(n2)冒泡排序是一种稳定的排序方法 快速排序算法思想快速排序算法思想v设排序区间为设排序区间为r low . . high ；v在排序区间任选一个记录在排序区间任选一个记录rx做为

17、基准；做为基准；v经过一趟排序后，将排序区间分为左、右两个子经过一趟排序后，将排序区间分为左、右两个子区间：区间： r low . . i-1 rx r i+1 . . high v使得：使得：r low. .i-1 .key rx.keyr i+1. .high .keyv然后再用相同的方法分别对左、右区间进行排序然后再用相同的方法分别对左、右区间进行排序，直至每个区间长度都是，直至每个区间长度都是1为止。为止。快速排序性能分析：快速排序性能分析：最坏的情况：表的初态恰好是正序或逆序排列。每次最坏的情况：表的初态恰好是正序或逆序排列。每次分区时，基准都恰好是区间的最大或最小键值，分区分区时，

18、基准都恰好是区间的最大或最小键值，分区的结果是有一个区间为空的结果是有一个区间为空: 对于初态是正序或逆序排列的表，需要进行n1趟排序，每趟要进行ni次比较:快速排序退化成冒泡排序，时间复杂度达到o(n2).2) 1-(=)-(=max1 -1=nnincni最好的情况：每次分区时，基准都恰好是区间的最好的情况：每次分区时，基准都恰好是区间的中间中间值，分区的结果使得左、右两个区间长度一样，值，分区的结果使得左、右两个区间长度一样，同步地收敛到同步地收敛到1。就平均性能而言，快速排序的时间复杂度是就平均性能而言，快速排序的时间复杂度是o(nlogn)。快速排序被认为是所有快速排序被认为是所有o

19、(nlogn)级别的排序级别的排序方法中平均性能最好的。方法中平均性能最好的。快速排序由于是递归实现的，需要消耗运行栈快速排序由于是递归实现的，需要消耗运行栈的空间的空间简单选择排序算法思想：简单选择排序算法思想：8 设：排序区间设：排序区间r1.n;8 在排序的过程中，整个排序区间被分为两个子区在排序的过程中，整个排序区间被分为两个子区间：有序区间：有序区r1.i-1和无序区和无序区ri.n;8 共进行共进行n1趟排序，每趟排序都是选择无序区的趟排序，每趟排序都是选择无序区的最小记录最小记录rmin；将；将rmin与无序区的第一条记录位置与无序区的第一条记录位置互换，使得无序区长度减互换，使

20、得无序区长度减1，有序区长度增，有序区长度增1。r0r11r22ri-1i-1riiri+1i+1rn-1n-1rnn有序区无序区简单选择排序性能分析：简单选择排序性能分析：比较次数与表的初态无关：比较次数与表的初态无关： 最好的情况：表的初态恰好是正序排列最好的情况：表的初态恰好是正序排列 移动次数：移动次数：mmin0最坏的情况：每趟都有移动发生最坏的情况：每趟都有移动发生 移动次数：移动次数：mmax3(n-1)平均平均o(n2), 不稳定的排序方法不稳定的排序方法2111)/n(n-i)(nccn-i maxmin堆排序堆排序以大顶堆为例：以大顶堆为例：8堆顶是排序区间最大的元素堆顶是排序区间最大的元素8去掉堆顶，将堆顶与堆的最后一个元素交换位置：去掉堆顶，将堆顶与堆的最后一个元素交换位置： 最大元素归位；最大元素归位； 新树根不满足堆定义，需要通过筛选调整为堆新树根不满足堆定