c++与数据结构课件.pptVIP

设哈希表的长度11，哈希函数是h(k) = k % 11，将整数序列{54,77,94,89,14,45,76}存入哈希表。按平方探查法处理冲突 例2 0 1 2 3 4 5 6 7 8 9 10 54 77 94 89 54 % 11 = 10 77 % 11 = 0 94 % 11 = 6 89 % 11 = 1 14 % 11 = 3 45 % 11 = 1 (冲突) 76 % 11 = 10 (冲突) 14 45 76 链地址法 将哈希地址相同的数据元素存储到同一个单链表中，哈希表中的每个存储单元中不再存放数据元素而是存放相应单链表的头指针 14.2 排序 1. 排序的基本概念 ? 排序：将文件中的记录按排序码非递减(或非递增)的顺序重新排列 ? 排序码：数据元素中的一个或多个数据项。排序码可以是关键字，也可以是其他若干数据项的组合。 ? 排序算法的稳定性：如果在待排序的元素序列中，存在着多个排序码相同的元素，按照某种排序算法排序后，这些元素的相对位置仍保持不变，则称该排序算法是稳定的，否则就是不稳定的。 2. 插入排序 ? 基本思想：把元素ei(0in) 依次插入到由S中前i个元素组成的已经排好序的序列{e0, e1, …,ei-1}的适当位置上，插入后S的前i+1个元素仍为有序。 ? 直接插入排序： 以顺序查找的办法找到要插入的元素在已排好序的元素序列中应处的位置。 所有元素分成2个集合：已排序记录集和待排序记录集。初始时，已排序记录集只有一个元素，即e0，待排序记录集是所有剩余元素。然后每次从待排序记录集中选取一个元素，使用顺序查找的方法，找到其在已排序记录集中的位置，将其插入到该位置，直到待排序记录集为空。 ? 例： 待排序记录为{50,20,75,34,40} 34 40 75 20 50 ? 直接插入排序的函数示例： ? 算法分析： 直接插入排序的平均时间复杂度是O(n2) 直接插入排序是稳定的排序算法 对于一个长度较短、接近有序的序列，直接插入排序是十分有效的 在插入ei时，e0, e1, … , ei-1是一个有序序列，所以可以用二分查找法寻找ei的插入位置，从而减少比较次数。 二分插入排序是稳定的排序算法，其平均时间复杂度仍是O(n2) ? 二分插入排序： 3. 选择排序 ? 基本思想：把元素ei(0in) 依次插入到由S中前i个元素组成的已经排好序的序列{e0, e1, …,ei-1}的适当位置上，插入后S的前i+1个元素仍为有序。 在初始时，已排好序的元素序列为空，待排序的元素序列中包括了需要排序的所有元素 ? 直接选择排序： 基本思想：用逐个比较的办法从待排序的元素序列中选出最小的元素。依次对i=0, 1, 2, … ,n-2分别执行如下的选择和交换步骤：在元素序列ei, ei+1, … , en-1中选择出最小的元素ek；当k≠i时，交换ei与ek的值。经上述n-1次的选择和交换后，排序工作即已完成。 ?直接选择排序函数模板： 直接选择排序算法是不稳定算法，其平均时间复杂度为O(n2) ? 演示： ? 树形选择排序： 基本思想： 首先对n个待排序元素的排序码两两进行比较，得到 个比较的优胜者（排序码较小者），然后对这些优胜者再进行两两比较，如此反复，直至选出排序码最小的元素。 在下一步选择排序码为次小的元素时，只需把树当中与已选出元素对应的叶结点的值设置为最大（∞），并从该叶结点开始和其兄弟结点进行比较，修改从该叶结点到根结点路径上各结点的值，即可选出排序码次小的元素。 算法的时间复杂度O(nlog2n)，该算法是稳定的。 ? 堆排序： 基本思想： 首先，用需要排序的元素的排序码构造一个堆（称为建堆），这样就可以找到排序码最小的元素，将其取出；然后，用剩下的排序码继续建堆。如此反复进行直至全部元素有序。 堆是一棵完全二叉树，其中每个分支结点的值均小于或等于左、右子女的值。位于堆顶位置的结点（即完全二叉树的根结点）的值是最小的。 堆排序的关键步骤有两个：一是建立初始堆；二是在取出堆顶后把剩余的结点调整为堆。 首先，把所有元素的排序码组织到一棵完全二叉树中。然后从完全二叉树中结点编号排在最后的那个分支结点km( )开始，逐步地把以km、km-1、km-2……为根的子树建成堆，最后，当以k0（k0是完全二叉树的根结点）为根的完全二叉树也是堆时，整个建堆过程也就完成了。 建立初始堆： 考虑以ki为根的子树，设ki的左、右子树均已是堆。为将该子树也调整为堆，只需将ki与其左子女k2i+1和右子女k2i+2进行比较。如果ki≤k2i+1且ki≤k2i+2，则以ki为根的子树已经是