数据结构第5章递归与广义表

92第5章递归与广义表一、复习要点本章主要讨论递归过程和广义表。一个递归的定义可以用递归的过程计算，一个递归的数据结构可以用递归的过程实现它的各种操作，一个递归问题也可以用递归的过程求解。因此，递归算法的设计是必须掌握的基本功。递归算法的一般形式：voidp(参数表){if(递归结束条件)可直接求解步骤；基本项elsep(较小的参数);归纳项}在设计递归算法时，可以先考虑在什么条件下可以直接求解。如果可以直接求解，考虑求解的步骤，设计基本项；如果不能直接求解，考虑是否可以把问题规模缩小求解，设计归纳项，从而给出递归求解的算法。必须通过多个递归过程的事例，理解递归。但需要说明的是，递归过程在时间方面是低效的。广义表是一种表，它的特点是允许表中套表。因此，它不一定是线性结构。它可以是复杂的非线性结构，甚至允许递归。可以用多重链表定义广义表。在讨论广义表时，特别注意递归在广义表操作实现中的应用。本章复习的要点：1、基本知识点要求理解递归的概念：什么是递归？递归的定义、递归的数据结构、递归问题以及递归问题的递归求解方法。理解递归过程的机制与利用递归工作栈实现递归的方法。通过迷宫问题，理解递归解法，从而掌握利用栈如何实现递归问题的非递归解法。在广义表方面，要求理解广义表的概念，广义表的几个性质，用图表示广义表的方法，广义表操作的使用，广义表存储结构的实现，广义表的访问算法，以及广义表的递归算法。2、算法设计求解汉诺塔问题，掌握分治法的解题思路。求解迷宫问题、八皇后问题，掌握回溯法的解题思路。对比单链表的递归解法和非递归解法，掌握单向递归问题的迭代解法。计算广义表结点个数，广义表深度，广义表长度的递归算法。输出广义表各个原子所在深度的非递归算法。判断两个广义表相等的递归算法。广义表的按深度方向遍历和按层次（广度）方向遍历的递归算法。使用栈的广义表的按深度方向遍历的非递归算法。递归的广义表的删除算法二、难点与重点1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解链表是递归的数据结构，可用递归过程求解有关链表的问题2、递归实现时栈的应用递归的分层(树形)表示：递归树递归深度(递归树的深度)与递归工作栈的关系93单向递归与尾递归的迭代实现3、广义表：广义表定义、长度、深度、表头、表尾用图形表示广义表的存储结构广义表的递归算法，包括复制、求深度、求长度、删除等算法三、教材中习题的解析5-1已知A[n]为整数数组，试写出实现下列运算的递归算法：(1)求数组A中的最大整数。(2)求n个整数的和。(3)求n个整数的平均值。【解答】#includeiostream.hclassRecurveArray{//数组类声明private:int*Elements;//数组指针intArraySize;//数组尺寸intCurrentSize;//当前已有数组元素个数public:RecurveArray(intMaxSize=10):ArraySize(MaxSize),Elements(newint[MaxSize]){}~RecurveArray(){delete[]Elements;}voidInputArray();//输入数组的内容intMaxKey(intn);//求最大值intSum(intn);//求数组元素之和floatAverage(intn);//求数组元素的平均值};voidRecurveArray::InputArray(){//输入数组的内容coutInputthenumberofArray:\n;for(inti=0;iArraySize;i++)cinElements[i];}intRecurveArray::MaxKey(intn){//递归求最大值if(n==1)returnElements[0];inttemp=MaxKey(n-1);if(Elements[n-1]temp)returnElements[n-1];elsereturntemp;}intRecurveArray::Sum(intn){//递归求数组之和if(n==1)returnElements[0];elsereturnElements[n-1]+Sum(n-1);}94floatRecurveArray::Average(intn){//递归求数组的平均值if(n==1)return(float)Elements[0];elsereturn((float)Elements[n-1]+(n-1)*Average(n-1))/n;}intmain(intargc,char*argv[]){intsize=-1;coutNo.oftheElements:;while(size1)cinsize;RecurveArrayra(size);ra.InputArray();cout\nThemaxis:ra.MaxKey(ra.MaxSize)endl;cout\nThesumis:ra.Sum(ra.MaxSize)endl;cout\ntheavris:ra.Average(ra.MaxSize)endl;return0;}5-2已知Ackerman函数定义如下：otherwise,0)m)or(n(n,1CCC1n1mn1mnm-(1)根据定义，写出它的递归求解算法；(2)利用栈，写出它的非递归求解算法。【解答】(1)已知函数本身是递归定义的，所以可以用递归算法来解决：unsignedakm(unsignedm,unsignedn){if(m==0)returnn+1;//m==0elseif(n==0)returnakm(m-1,1);//m0,n==0elsereturnakm(m-1,akm(m,n-1));//m0,n0}(2)为了将递归算法改成非递归算法，首先改写原来的递归算法，将递归语句从结构中独立出来：unsignedakm(unsignedm,unsignedn){unsignedv;if(m==0)returnn+1;//m==0if(n==0)returnakm(m-1,1);//m0,n==0v=akm(m,n-1));//m0,n0returnakm(m-1,v);}计算akm(2,1)的递归调用树如图所示：95用到一个栈记忆每次递归调用时的实参值，每个结点两个域{vm,vn}。对以上实例，栈的变化如下：相应算法如下#includeiostream.h#include“stack.h”#definemaxSize3500;unsignedakm(unsignedm,unsignedn){structnode{unsignedvm,vn;}stacknodest(maxSize);nodew;unsignedv;w.vm=m;w.vn=n;st.Push(w);do{while(st.GetTop().vm0){//计算akm(m-1,akm(m,n-1))while(st.GetTop().vn0)//计算akm(m,n-1),直到akm(m,0){w.vn--;st.Push(w);}w=st.GetTop();st.Pop();//计算akm(m-1,1)w.vm--;w.vn=1;st.Push(w);}//直到akm(0,akm(1,*))w=st.GetTop();st.Pop();v=w.vn++;//计算v=akm(1,*)+1if(st.IsEmpty()==0)//如果栈不空,改栈顶为(m-1,v)akm(2,1)v=akm(2,0)akm(1,1)v=akm(1,0)akm(0,1)=2akm(0,2)=3akm(1,3)v=akm(1,2)v=akm(1,1)v=akm(1,0)akm(0,1)=2akm(0,2)=3akm(0,3)=4akm(0,4)=5v=2v=2v=3v=4v=3akm=5akm=5akm=321212121211320111111021001改akm(m-1,1)改akm(m-1,1)v=n+1=2改akm(m-1,v)改akm(m-1,v)v=n+1=3vmvnvmvnvmvnvmvnvmvnvmvnvmvnvmvnvmvnvmvnvmvnvmvn1313131304121212031111021001改akm(m-1,1)v=n+1=2改akm(m-1,v)改akm(m-1,v)改akm(m-1,v)栈空,返回v=5v=n+1=3v=n+1=4v=n+1=596{w=st.GetTop();st.Pop();w.vm--;w.vn=v;st.Push(w);}}while(st.IsEmpty()==0);returnv;}5-3【背包问题】设有一个背包可以放入的物品的重量为s，现有n件物品，重量分别为w[1],w[2],…,w[n]。问能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。（提示：此背包问题的递归定义如下：）][)1],[(][10)1,(10False0False0True),(时所选物品中包括时所选物品中不包括且或物品件数不能为负数且总重量不能为负数此时背包问题一定有解nwnnwsKNAPnwnsnsKNAPnsssnsKNAP【解答】根据递归定义，可以写出递归的算法。enumboolean{False,True}booleanKnap(ints,intn){if(s==0)returnTrue;if(s0||s0&&n1)returnFalse;if(Knap(s–W[n],n-1)==True){coutW[n]‘,’;returnTrue;}returnKnap(s,n-1);}若设w={0,1,2,4,8,16,32}，s=51,n=6。则递归执行过程如下递归Knap(51,6)returnTrue,完成Knap(51-32,5)returnTrue,打印32Knap(19-16,4)returnTrue,打印16Knap(3-8,3)returnFalseKnap(3,3)returnTrue,无动作s=-50returnFalseKnap(3-4,4)returnFalseKnap(3,2)returnTrue,无动作s=-10returnFalseKnap(3-2,1)returnTrue,打印2Knap(1-1,0)returnTrue,打印1s=0returnTrue5-4【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第1行，第2行，…。第8行上布放棋子。在每一行中有8个可选择位置，但在任一时刻，棋盘的合法布局都必须满足3个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。(提示：用回溯法。在第n行第j列安放一个棋子时，需要记录在行方向、列方向、正斜线方向、反斜线方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子，恢复安放该棋子前的状态，试探本行的第j+1列。)【解答】此为典型的回溯法问题。97在解决8皇后时，采用回溯法。在安放第i行皇后时，需要在列的方向从1到n试探(j=1,…,n)：首先在第j列安放一个皇后，如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第j列安放的皇后。如果没有出现攻击，在第j列安放的皇后不动，递归安放第i+1行皇后。解题时设置4个数组：col[n]：col[i]标识第i列是否安放了皇后md[2n-1]：md[k]标识第k条主对角线是否安放了皇后sd[2n-1]：sd[k]标识第k条次对角线是否安放了皇后q[n]