广工数据结构 第5章.pptx

第5章 递归;引言;引言;5.1 递归基础：汉诺塔问题描述;汉诺塔示例：n = 3;汉诺塔示例：n = 3;汉诺塔程序;函数调用过程解析;函数调用的一般过程;函数调用的一般过程;函数递归调用的嵌套层数称为递归层次。 规定：最开始时其它函数对递归函数的调用称为第0层调用。 ;Hanoi(3, A, B, C)执行过程;Hanoi(3, A, B, C)执行过程;5.2 递归与分治：分治法;5.2 递归与分治：分治法;分治法举例：汉诺塔问题;分治法需要注意的问题;分治法需要注意的问题（续1）;分治法需要注意的问题（续2）;分治法应用1：折半查找算法;分治法应用1：折半查找算法（续）;折半查找算法举例;;折半查找算法举例;high;折半查找算法举例;;折半查找算法举例;int BinSearch(RcdType rcd[], KeyType key, int low, int high) { // 在有序序列rcd[low..high]中折半查找目标关键字key int mid = (low + high) / 2; if(high low) return -1; if(rcd[mid].key == key) return mid; //查找成功，返回中间关键字的下标 else if(rcd[mid].key key) // 在前半区折半查找 return BinarySearch(rcd, key, low, mid–1); else // 在后半区折半查找 return BinarySearch(rcd, key, mid+1, high); };分治法应用2：归并排序算法;31;32;归 并 排 序 算 法 举 例;34;35;36;37;归并排序算法的实现;归并排序算法的实现;归并排序算法的实现;归并排序算法的实现;归并排序算法的实现;归并排序算法的实现;归并排序算法的实现;归并排序算法的实现;归并排序算法的实现;归并排序算法的实现;归并排序算法的实现;归并排序算法的实现;归并排序算法的实现;归并排序算法的实现;;归并排序算法的实现;归并排序算法的实现;归并排序算法的实现;分治法应用3：快速排序算法;分治法应用3：快速排序算法;int Partition(RcdType rcd[ ], int low, int high) { // 对rcd[low..high] 作一次划分，并返回枢轴记录应该所处的位置 rcd[0] = rcd[low]; // 将枢轴移至数组的闲置分量　　 while(lowhigh) { // low和high从两端交替地向中间移动 　 while (lowhigh rcd[high].key = rcd[0].key) --high; 　 rcd[low] = rcd[high]; // 将比枢轴小的记录移到前端 　　 while(lowhigh rcd[low].key = rcd[0].key) ++low;　　　　 　　 rcd[high] = rcd[low]; // 将比枢轴大的记录移到后端 　} 　rcd[low] = rcd[0];　　 　　 　return low; 　　　　　 　　 } ;42;void QSort(RcdType rcd[], int s, int t) { 　// 对记录序列 rcd[s..t] 进行快速排序 　if(s t) { 　　　// 长度大于1 // 对rcd[s..t]一趟划分，并返回枢轴位置 　 int pivotloc = Partition(rcd, s, t); 　　 QSort(rcd, s, pivotloc-1); // 对前子序列递归进行排序 　　QSort(rcd, pivotloc+1, t); // 对后子序列递归进行排序 　} };5.3 递归与迭代;5.3 递归与迭代：迭代三要素;折半查找算法的迭代实现;2-路归并排序算法的迭代实现;迭代与递归的联系与区别;迭代与递归的联系与区别;5.4 广义表;广义表举例;69;70;广义表存储结构示例;广义表的分解方式：L7 = (f, (g) , h);广义表分解方式一举例：求广义表深度; 求广义表的深度;广义表分解方式二举例：在表尾添加元素; 在表尾添加元素; 在表尾添加元素