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

数据结构重难点串讲,讲师：翔高教育一级培训师地点：上海,第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.按关键字值有序排列查找方法：设查找区间为Rlow.high取mid(low+high)/2，则当KRmid.key：下一个查找区间为Rmid+1.High当K=Rmid.key：查找成功，结束当lowhigh：查找失败，结束,02,16,11,22,25,27,33,42,56,77,81,79,举例：K39,K33low=mid+1,Kbt-key:在bt的右子树上继续查找当K=bt-key:查找成功,查找分析：查找成功时：ASL(1122344351)/11=34/11查找失败时：ASL(354552)/12=45/12ASL值与树的形态有关,构造散列函数时的几点要求：散列函数的定义域必须包括需要存储的全部关键码；散列函数的值域必须在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为整数如果Hin12+n22+nk2(n=n1+n2+nk)所以对每个子表排序所耗费的时间之和要小于对整个区间排序所耗费的时间通过对子表小范围的排序,将排序区间调整成基本有序的序列;不断减少子表的个数(即扩大子表的长度),直至子表的个数为1,完成整个排序操作.,冒泡排序(BubbleSort)自下而上(或上而下)扫描记录序列，相邻的两条记录Ri与Ri1(或Ri+1)如果是逆序，则交换位置,冒泡排序性能分析：最好的情况：表的初态恰好是正序排列，第一趟扫描没有移动发生比较次数：Cminn-1移动次数：Mmin0最坏的情况：表的初态恰好是逆序排列，需要进行n-1趟排序，每趟都要移动整个区间比较次数：移动次数：,等概条件下平均情况：,平均比较次数：,平均移动次数：,时间复杂度：O(n2),冒泡排序是一种稳定的排序方法,快速排序算法思想设排序区间为Rlow.high；在排序区间任选一个记录Rx做为基准；经过一趟排序后，将排序区间分为左、右两个子区间：Rlow.i-1RxRi+1.high使得：Rlow.i-1.keyRx.keyRi+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),不稳定的排序方法,堆排序以大顶堆为例：堆顶是排序区间最大的元素去掉堆顶，将堆顶与堆的最后一个元素交换位置：最大元素归位；新树根不满足堆定义，需要通过筛选调整为堆,归并排序(Mergingsort)算法思想:一种基于将两个有序表异地归并成一个有序表的排序策略。初态是将排序表中的每个元素看成是一个有序的子表，共有n个子表。经过一趟排序，将两个相邻的有序子表归异地并成一个有序子表；共进行log2n趟这样的归并，整个排序表就被归并成了一个有序表。,经典例题分析,【例1】对一组数据（2，12，16，88，5，10）进行排序，若前三者趟排序结果如下：第一趟排序结果：2，12，16，5，10，88第二趟排序结果：2，12，5，10，16，88第三趟排序结