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

《计算机统考重难点班讲义(数据结构)-第四讲.ppt》由会员分享，可在线阅读，更多相关《计算机统考重难点班讲义(数据结构)-第四讲.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、关键字的比较次数的比较次数Pi-Pi-查找第查找第i i条记录的概率条记录的概率 顺序查找思想：顺序查找思想：从表的一端开始，逐个将给定值从表的一端开始，逐个将给定值K K与关键字进行与关键字进行比较，直到找到记录或查找失败；比较，直到找到记录或查找失败；注意：注意：这里这里“顺序顺序”的含义不是查找表是顺序存储的，的含义不是查找表是顺序存储的，而是顺着表的自然次序逐个比较。而是顺着表的自然次序逐个比较。查找效率：查找效率：8查找成功时的查找成功时的ASLASL：8查找失败时的ASL：ASL=n+18平均：ASL3(n+1)/4顺序查找小结：顺序查找小结：c最朴素的查找方法最朴素的查找方法c对

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

4、间为下一个查找区间为 R mid+1.R mid+1.High High 当当K=K=Rmid.keyRmid.key：查找成功，结束查找成功，结束 当当lowhighlowhigh：查找失败，结束查找失败，结束02161122 2527 334256778179013245687910111312lowmidhigh举例：K39K33low=mid+1midK56high=mid-1mid39经过与关键字33,56,39的比较，查找成功K=39查找成功 查找成功的过程是自树根沿树枝到达目标结点，K与关键字的最大比较次数不超过树高log2n+17310158122469111302161122

5、252733425677817901324568791011131239查找查找K K3939：73101581224691113查找成功:ASL=(11+22+34+46)/13=41/13查找失败:ASL=(32+412)/14=54/14n=13折半查找的折半查找的ASLASL 设设:n=2:n=2h h-1-1-折半查找判定树是高为折半查找判定树是高为h h的满二叉的满二叉树树 h=logh=log2 2(n+1)(n+1)折半查找小结折半查找小结8一种效率很高的查找方法，时间复杂度一种效率很高的查找方法，时间复杂度O(logO(log2 2n)n)8对表有严格的限制：有序的顺序表；对

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

7、ey:在在bt的右子树上继续查找的右子树上继续查找当当 K=bt-key:查找成功查找成功3248263929563412441946bt查找分析：查找成功时：查找成功时：ASL(1122344351)/11=34/11查找失败时：查找失败时：ASL(354552)/12=45/12 ASL值与树的形态有关3248263929563412441946构造散列函数时的几点要求：构造散列函数时的几点要求：1.1.1.1.散列函数的定义域必须包括需要存储的全部关键散列函数的定义域必须包括需要存储的全部关键散列函数的定义域必须包括需要存储的全部关键散列函数的定义域必须包括需要存储的全部关键码；散列函数

8、的值域必码；散列函数的值域必码；散列函数的值域必码；散列函数的值域必须在须在 0 0到到m-1 m-1 之间（之间（mm是散列表的容量）。是散列表的容量）。2.2.散列函数计算出来的地址应均匀分布在整个地址散列函数计算出来的地址应均匀分布在整个地址空间中：若空间中：若 keykey是从关键字集合中随机抽取的一是从关键字集合中随机抽取的一个关键字，散列函数应能以同等概率取个关键字，散列函数应能以同等概率取0 0到到m-1 m-1 中的每一个值。中的每一个值。3.3.散列函数应是简单的，能在较短的时间内计算出散列函数应是简单的，能在较短的时间内计算出结果。结果。处理冲突的方法思路：设在哈希值设在哈

9、希值H0H(Ri.key)上发生了冲突，我们要为上发生了冲突，我们要为Ri另另找一个空闲的地址存放找一个空闲的地址存放1.开放定址法2.拉链法3.再哈希法4.建公共溢出区法增量增量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,则

10、则Hi=Hi+m*n;其中其中n为整数为整数思路：思路：将同义词链接成单链表。将同义词链接成单链表。拉链法拉链法key 26 36 41 38 44 15 68 12 06 51 25H(key)0 10 2 12 523 12 6 12 1201 234 567 8 9 1011 121526 41 68 44 06 36 25511238 拉链法的查找效率：拉链法的查找效率：01 234 567 8 9 1011 121526 41 68 44 06 36 25511238 查找成功时，ASL(172234)/11=18/11查找失败时，ASL(061524)/13=11/13用不同的方法

11、溢出处理冲突时散列表的平均查找长度如用不同的方法溢出处理冲突时散列表的平均查找长度如图所示图所示各种方法处理溢出时的平均查找长各种方法处理溢出时的平均查找长度度经典例题分析经典例题分析v【例例1 1】（1010分）将关键字序列（分）将关键字序列（7 7，8 8，3030，1111，1818，9 9，1414）散列存储到散列表中）散列存储到散列表中,散列表的的存散列表的的存储空间是一个下标从储空间是一个下标从0 0开始的一维数据开始的一维数据,散列函数为：散列函数为：H(key)=(key3)MOD7,H(key)=(key3)MOD7,处理冲突采用线性探测处理冲突采用线性探测再散列法再散列法,

12、要求装填要求装填(载载)因子为因子为0.70.7。v（1 1）请画出所构造的散列表。请画出所构造的散列表。v（2 2）分别计算等概率情况下查找成功和查找不成分别计算等概率情况下查找成功和查找不成功的平均查找长度。功的平均查找长度。22v（7 7，8 8，3030，1111，1818，9 9，1414）v H(key)=(key3)MOD7H(key)=(key3)MOD7v（1 1）首先根据要求）首先根据要求key3key3的装填因子的装填因子0.70.7，得出所，得出所构造的散列表的长度为构造的散列表的长度为1010，下标从，下标从0 0到到9 9。根据题目。根据题目所给的散列函数和冲突所采

13、用的线性探测再散列法。所给的散列函数和冲突所采用的线性探测再散列法。v所构造的散列表如下：所构造的散列表如下：23下标0123456789关键字71481130189v查找成功时探查次数分别如下表所示：查找成功时探查次数分别如下表所示：v在等概率条件下，查找成功的平均查找长度为：在等概率条件下，查找成功的平均查找长度为：（14+32+214+32+2）/7=12/7/7=12/7。v在等概率条件下，查找不成功的各位置对应的探查在等概率条件下，查找不成功的各位置对应的探查次数如下表：次数如下表：查找不成功的平均查找长度为：查找不成功的平均查找长度为：（3+2+1+2+1+5+43+2+1+2+1

14、+5+4）=18/7=18/724关键字78301118914散列地址0365560探查次数1111332下标0123456探查次数3212154第第7 7章内部排序章内部排序25重难点导航重难点导航v各种排序算法的比较以及特点各种排序算法的比较以及特点v各种排序算法时间复杂度的计算，以及最好和最坏各种排序算法时间复杂度的计算，以及最好和最坏性能分析性能分析v堆排序算法的思想和原理堆排序算法的思想和原理26排序法排序法平均时间平均时间最差情形最差情形稳定度稳定度额外空间额外空间备注备注冒泡冒泡O(n2)O(n2)稳定稳定O(1)n小时较好小时较好交换交换O(n2)O(n2)不稳定不稳定O(1)

15、n小时较好小时较好选择选择O(n2)O(n2)不稳定不稳定O(1)n小时较好小时较好插入插入O(n2)O(n2)稳定稳定O(1)大部分已排大部分已排序时较好序时较好基数基数O(logRB)O(logRB)稳定稳定O(n)B是真数是真数(0-9)，R是基数是基数(个个十百十百)ShellO(nlogn)O(ns)1snn1 12 2+n+n2 22 2+n+nk k2 2 (n=n (n=n1 1+n+n2 2+n+nk k)所以对每个子表排序所耗费的时间之和要小于对整所以对每个子表排序所耗费的时间之和要小于对整个区间排序所耗费的时间个区间排序所耗费的时间8通过对子表小范围的排序通过对子表小范围

16、的排序,将排序区间调整成基本有将排序区间调整成基本有序的序列序的序列;8不断减少子表的个数不断减少子表的个数(即扩大子表的长度即扩大子表的长度),),直至子表直至子表的个数为的个数为1,1,完成整个排序操作完成整个排序操作.冒泡排序冒泡排序(Bubble Sort)(Bubble Sort)自下而上自下而上(或上而下或上而下)扫描记录序列，扫描记录序列，相邻的两条记录相邻的两条记录R Ri i与与R Ri i1 1(或或R Ri+1i+1)如果是逆序，如果是逆序，则交换位置则交换位置冒泡排序性能分析：冒泡排序性能分析：最好的情况：最好的情况：表的初态恰好是正序排列，第一趟扫描表的初态恰好是正序

17、排列，第一趟扫描没有移动发生没有移动发生 比较次数：比较次数：CminCminn-1n-1 移动次数：移动次数：MminMmin0 0最坏的情况最坏的情况：表的初态恰好是逆序排列，需要进行表的初态恰好是逆序排列，需要进行n-n-1 1趟排序，每趟都要移动整个区间趟排序，每趟都要移动整个区间 比较次数：比较次数：移动次数：移动次数：等概条件下平均情况：等概条件下平均情况：平均比较次数：平均移动次数：时间复杂度：O(n2)冒泡排序是一种稳定的排序方法 快速排序算法思想快速排序算法思想v设排序区间为设排序区间为R low.high R low.high；v在排序区间任选一个记录在排序区间任选一个记录

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

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

20、ogn)O(nlogn)。快速排序被认为是所有快速排序被认为是所有O(nlogn)O(nlogn)级别的排序方级别的排序方法中平均性能最好的。法中平均性能最好的。快速排序由于是递归实现的，需要消耗运行栈快速排序由于是递归实现的，需要消耗运行栈的空间的空间简单选择排序算法思想：简单选择排序算法思想：8设：排序区间设：排序区间R1.n;8在排序的过程中，整个排序区间被分为两个子区在排序的过程中，整个排序区间被分为两个子区间：有序区间：有序区R1.i-1和无序区和无序区Ri.n;8共进行共进行n1趟排序，每趟排序都是选择无序区的趟排序，每趟排序都是选择无序区的最小记录最小记录Rmin；将；将Rmin

21、与无序区的第一条记录位置与无序区的第一条记录位置互换，使得无序区长度减互换，使得无序区长度减1，有序区长度增，有序区长度增1。RR1R2Ri-1RiRi+1Rn-1Rn012i-1ii+1n-1n有序区无序区简单选择排序性能分析：简单选择排序性能分析：比较次数与表的初态无关：比较次数与表的初态无关：最好的情况：表的初态恰好是正序排列最好的情况：表的初态恰好是正序排列 移动次数：移动次数：Mmin0最坏的情况：每趟都有移动发生最坏的情况：每趟都有移动发生 移动次数：移动次数：Mmax3(n-1)平均平均O(n2),不稳定的排序方法不稳定的排序方法堆排序堆排序以大顶堆为例：以大顶堆为例：8堆顶是排

22、序区间最大的元素堆顶是排序区间最大的元素8去掉堆顶，将堆顶与堆的最后一个元素交换位置：去掉堆顶，将堆顶与堆的最后一个元素交换位置：最大元素归位；最大元素归位；新树根不满足堆定义，需要通过筛选调整为堆新树根不满足堆定义，需要通过筛选调整为堆归并排序归并排序(Merging sort)算法思想算法思想:8一种基于将两个有序表异地归并成一个有序表的排序策一种基于将两个有序表异地归并成一个有序表的排序策略。略。8初态是将排序表中的每个元素看成是一个有序的子表，初态是将排序表中的每个元素看成是一个有序的子表，共有共有n n个子表。个子表。8经过一趟排序，将两个相邻的有序子表归异地并成一个经过一趟排序，将

23、两个相邻的有序子表归异地并成一个有序子表；有序子表；8共进行共进行loglog2 2n n趟这样的归并，整个排序表就被归并成了趟这样的归并，整个排序表就被归并成了一个有序表。一个有序表。经典例题分析经典例题分析v【例例1 1】对一组数据（对一组数据（2 2，1212，1616，8888，5 5，1010）进行排序，若前三者趟排序结果如下：进行排序，若前三者趟排序结果如下：v第一趟排序结果：第一趟排序结果：2 2，1212，1616，5 5，1010，8888v第二趟排序结果：第二趟排序结果：2 2，1212，5 5，1010，1616，8888v第三趟排序结果：第三趟排序结果：2 2，5 5，1010，1212，1616，8888v则采用的排序方法可能是则采用的排序方法可能是vA.A.起泡排序起泡排序 B.B.希尔排序希尔排序 C.C.归并排序归并排序 D.D.基数排序基数排序v【解析解析】本题考查起泡排序算法的执行过程。第一本题考查起泡排序算法的执行过程。第一趟排序后，把最大数趟排序后，把最大数8888放到了最终位置，第二趟排放到了最终位置，第二趟排序后，把次大的序后，把次大的1616放到了最终位置，显然是起泡排放到了最终位置，显然是起泡排序。序。44