数据结构递归与广义表

《数据结构递归与广义表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章递归与广义表一、复习要点本章主要讨论递归过程和广义表。一个递归的定义可以用递归的过程计算，一个递归的数据结构可以用递归的过程实现它的各种操作，一个递归问题也可以用递归的过程求解。因此，递归算法的设计是必须掌握的基本功。递归算法的一般形式：voidp(参数表){if(递归结束条件)可直接求解步骤；基本项elsep(较小的参数);归纳项}在设计递归算法时，可以先考虑在什么条件下可以直接求解。如果可以直接求解，考虑求解的步骤，设计基本项；如果不能直接求解，考虑是否可以把问题规模缩小求解，设计归纳项，从而给出递归求解的算法。必须通过多个递归过程的事例，理解递归。

2、但需要说明的是，递归过程在时间方面是低效的。广义表是一种表，它的特点是允许表中套表。因此，它不一定是线性结构。它可以是复杂的非线性结构，甚至允许递归。可以用多重链表定义广义表。在讨论广义表时，特别注意递归在广义表操作实现中的应用。本章复习的要点：1、基本知识点要求理解递归的概念：什么是递归？递归的定义、递归的数据结构、递归问题以及递归问题的递归求解方法。理解递归过程的机制与利用递归工作栈实现递归的方法。通过迷宫问题，理解递归解法，从而掌握利用栈如何实现递归问题的非递归解法。在广义表方面，要求理解广义表的概念，广义表的几个性质，用图表示广义表的方法，广义表操作的

3、使用，广义表存储结构的实现，广义表的访问算法，以及广义表的递归算法。2、算法设计Ø求解汉诺塔问题，掌握分治法的解题思路。Ø求解迷宫问题、八皇后问题，掌握回溯法的解题思路。Ø对比单链表的递归解法和非递归解法，掌握单向递归问题的迭代解法。Ø计算广义表结点个数，广义表深度，广义表长度的递归算法。Ø输出广义表各个原子所在深度的非递归算法。Ø判断两个广义表相等的递归算法。Ø广义表的按深度方向遍历和按层次（广度）方向遍历的递归算法。Ø使用栈的广义表的按深度方向遍历的非递归算法。Ø递归的广义表的删除算法二、难点与重点1、递归：递归的定义、递归的数据结构、递归问题用递归过程求

4、解Ø链表是递归的数据结构，可用递归过程求解有关链表的问题2、递归实现时栈的应用Ø递归的分层(树形)表示：递归树Ø递归深度(递归树的深度)与递归工作栈的关系107Ø单向递归与尾递归的迭代实现3、广义表：广义表定义、长度、深度、表头、表尾Ø用图形表示广义表的存储结构Ø广义表的递归算法，包括复制、求深度、求长度、删除等算法三、教材中习题的解析5-1已知A[n]为整数数组，试写出实现下列运算的递归算法：(1)求数组A中的最大整数。(2)求n个整数的和。(3)求n个整数的平均值。【解答】#include classRecurveArray{//数

5、组类声明 private: int*Elements;//数组指针 intArraySize;//数组尺寸intCurrentSize;//当前已有数组元素个数 public:RecurveArray(intMaxSize=10):ArraySize(MaxSize),Elements(newint[MaxSize]){} ~RecurveArray(){delete[]Elements;} voidInputArray();//输入数组的内容 intMaxKey(intn);//求最大值 intSum(intn);//求数组元素之和floatAverage(

6、intn);//求数组元素的平均值};voidRecurveArray::InputArray(){//输入数组的内容cout<<"InputthenumberofArray:";for(inti=0;i>Elements[i];}intRecurveArray::MaxKey(intn){//递归求最大值if(n==1)returnElements[0];inttemp=MaxKey(n-1);if(Elements[n-1]>temp)returnElements[n-1];elsereturntemp;}intR

7、ecurveArray::Sum(intn){//递归求数组之和if(n==1)returnElements[0];elsereturnElements[n-1]+Sum(n-1);}107floatRecurveArray::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;cout<<"No.ofthe

8、Elements:";while(si