考研数据结构复习121130.ppt

输入顺序不同所建立的不同二叉排序树 顺序输入:24、53、12、28、 45、 90 排序 将排序码写成一个一维数组的形式， 并且在没有声明的情形下，所有排序都按排序码的值递增排列。 排序 插入排序（直插排序、二分排序、希尔排序） 交换排序（冒泡排序、快速排序） 选择排序 （直选排序） 归并排序（二路归并排序） 插入排序 1．直接插入排序 基本思想：把n个待排序的元素看成一个有序表和一个无序表， 开始时有序表中只包含一个元素，无序表中包含有n-1个元素， 排序过程中每次从无序表中取出第一个元素，把它的排序码 依次与有序表元素的排序码进行比较，将它插入到有序表中 的适当位置，使之成为新的有序表。 2.折半插入排序 例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。它的直接插入排序的执行过程如图7-1所示。 3. 希尔排序 希尔排序(缩小增量排序):1959年由D.L.Shell提出来的。 基本思想：先将整个待排元素序列分割成若干个子序列（由 “增量”确定）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。 例如，n=8，数组array[ ]的八个元素分别为：91，67，35，62，29，72，46，57。下面用图7-2给出希尔排序算法的执行过程。 交换排序 冒泡排序 基本思想: 对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部，就象水底下的气泡一样逐渐向上冒。 例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。下面用图7-3给出冒泡排序算法的执行过程。 快速排序 基本思想是：取待排序序列中的某个元素（一般第一个元素）作为基准，通过一趟排序，将待排元素分为左右两个子序列， 左子序列元素的排序码均小于或等于基准元素的排序码， 右子序列的排序码则大于基准元素的排序码， 然后分别对两个子序列继续进行快速排序，直至整个序列有序。 元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面，排序码较小的记录一次就能够交换到前面，记录每次移动的距离较远，因而总的比较和移动次数较少。 例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图7-4所示。 选择排序 直接选择排序 基本思想 直接选择排序是一种简单的排序方法。基本思想是：第一次从array[0]~array[n-1]中选取最小值，与array[0]交换，第二次从array[1]~array[n-1]中选取最小值，与array[1]交换，第三次从array[2]~array[n-1]中选取最小值，与array[2]交换，…，第i次从array[i-1]~array[n-1]中选取最小值，与array[i-1]交换，…, 第n-1次从array[n-2]~array[n-1]中选取最小值，与array[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。 例如，给定n=8，数组R中的8个元素的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序过程如图7-5所示。 归并排序 二路归并排序 1、基本思想：将两个有序子区间（有序表）合并成一个有序子区间，一次合并完成后，有序子区间的数目减少一半，而区间的长度增加一倍，当区间长度从1增加到n（元素个数）时，整个区间变为一个，即为有序序列. 例如，给定排序码46，55，13，42，94，05，17，70，二路归并排序过程如图7-10所示。算法P284 树 根 结点 X 的第一个孩子 结点 X 紧邻的右兄弟 二叉树 根 结点 X 的左孩子 结点 X 的右孩子 I A C B D H G F E F I A B D H G C E 树 森林转换为二叉树的过程 森林 哈夫曼树及应用 1 哈夫曼树---带权路径长度最短的二叉树(最优树）。 路径：从一个结点到另一个结点之间的若干个分支序列； 路径长度：从一个结点到另一个结点路径上的分支数目； 结点的路径长度：从根到该结点的路径长度； 树的路径长度：树中所有叶子结点的路径长度之和；记为PL. 在结点数相同的条件下，完全二叉树是路径最短的二叉树 7 1 3 2 5 6 4 8 8 1 3 2 5 7 4 6 非完全二叉树 PL=10 完全二叉树PL=9 （路径最短的二叉树不唯一，不是完全二叉树，也可能路径长度最短） 1 哈夫曼树的概念（续） 结点的权：根据应用的需要给树的结点赋的权值； 结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积