数据结构总复习4.ppt

第九章 查找 P217 监视哨的作用 算法描述 二分查找实现时可以用链表吗? 哈希表——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫~ 哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫~ (5)除留余数法 构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，p?m 特点 简单、常用，可与上述几种方法结合使用 p的选取很重要；p选的不好，容易产生同义词 (6)随机数法 构造：取关键字的随机函数值作哈希地址，即H(key)=random(key) 适于关键字长度不等的情况 开放定址法 方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,……k(k?m-1) 其中：H(key)——哈希函数 m——哈希表表长 di——增量序列 分类 线性探测再散列：di=1,2,3,……m-1 二次探测再散列：di=12,-12,22,-22,32,……±k2(k?m/2) 伪随机探测再散列：di=伪随机数序列 再哈希法 方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key) i=1,2,……k 其中：Rhi——不同的哈希函数 特点：计算时间增加 链地址法 方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针 第十章 内部排序 堆排序 堆的定义：n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆 堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫~ 堆排序需解决的两个问题： 如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？ 第二个问题解决方法——筛选 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选” 算法描述 8.4 归并排序 归并——将两个或两个以上的有序表组合成一个新的有序表，叫~ 2-路归并排序 排序过程 设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1 两两合并，得到?n/2?个长度为2或1的有序子序列 再两两合并，……如此重复，直至得到一个长度为n的有序序列为止 8.5 基数排序 （3）例子 例如，已知待排序的一组记录的初始排列如下所示： 按算法10.1进行直接插入排序的过程如图10.1所示。 监视哨 L.r[0] 图10.1 直接插入排序示例 [初始关键字]: (49) 38 65 97 76 13 27 49 i = 2: (38) (38 49) 65 97 76 13 27 49 i = 3: (65) (38 49 65) 97 76 13 27 49 i = 4: (97) (38 49 65 97) 76 13 27 49 i = 5: (76) (38 49 65 76 97) 13 27 49 i = 6: (13) (13 38 49 65 76 97) 27 49 i = 7: (27) (13 27 38 49 65 76 97) 49 i = 8: (49) (13 27 38 49 49 65 76 97) （4）算法效率 从空间来看，只需要一个记录的辅助空间。 从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。 ①当待排序列中记录按关键字非递减有序排序（“正序”）时，所需进行关 键字间比较的次数达最小值n－1（即 ），记录不需移动。 数达最大值(n + 2)(n－1)/2（即 ），记录移动的次数也达最大值 (n + 4)(n－1)/2（即 ）。 ②当待排序列中记录