数据结构习题解析第5章

第5章 递归与广义表

一、复习要点

本章主要讨论递归过程和广义表。一个递归的定义可以用递归的过程计算，一个递归的数据结构可以用递归的过程实现它的各种操作，一个递归问题也可以用递归的过程求解。因此，递归算法的设计是必须掌握的基本功。递归算法的一般形式：

void p ( 参数表 ) { if ( 递归结束条件)

可直接求解步骤； 基本项 else p ( 较小的参数 ); 归纳项 }

在设计递归算法时，可以先考虑在什么条件下可以直接求解。如果可以直接求解，考虑求解的步骤，设计基本项；如果不能直接求解，考虑是否可以把问题规模缩小求解，设计归纳项，从而给出递归求解的算法。必须通过多个递归过程的事例，理解递归。但需要说明的是，递归过程在时间方面是低效的。

广义表是一种表，它的特点是允许表中套表。因此，它不一定是线性结构。它可以是复杂的非线性结构，甚至允许递归。可以用多重链表定义广义表。在讨论广义表时，特别注意递归在广义表操作实现中的应用。

本章复习的要点： 1、基本知识点

要求理解递归的概念：什么是递归？递归的定义、递归的数据结构、递归问题以及递归问题的递归求解方法。理解递归过程的机制与利用递归工作栈实现递归的方法。通过迷宫问题，理解递归解法，从而掌握利用栈如何实现递归问题的非递归解法。在广义表方面，要求理解广义表的概念，广义表的几个性质，用图表示广义表的方法，广义表操作的使用，广义表存储结构的实现，广义表的访问算法，以及广义表的递归算法。

2、算法设计

? 求解汉诺塔问题，掌握分治法的解题思路。

? 求解迷宫问题、八皇后问题，掌握回溯法的解题思路。

? 对比单链表的递归解法和非递归解法，掌握单向递归问题的迭代解法。 ? 计算广义表结点个数，广义表深度，广义表长度的递归算法。 ? 输出广义表各个原子所在深度的非递归算法。 ? 判断两个广义表相等的递归算法。

? 广义表的按深度方向遍历和按层次（广度）方向遍历的递归算法。 ? 使用栈的广义表的按深度方向遍历的非递归算法。 ? 递归的广义表的删除算法

二、难点与重点

1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解 ? 链表是递归的数据结构，可用递归过程求解有关链表的问题 2、递归实现时栈的应用

? 递归的分层(树形)表示：递归树

92

? 递归深度(递归树的深度)与递归工作栈的关系 ? 单向递归与尾递归的迭代实现

3、广义表：广义表定义、长度、深度、表头、表尾 ? 用图形表示广义表的存储结构

? 广义表的递归算法，包括复制、求深度、求长度、删除等算法

三、教材中习题的解析

5-1 已知A[n]为整数数组，试写出实现下列运算的递归算法： (1) 求数组A中的最大整数。 (2) 求n个整数的和。 (3) 求n个整数的平均值。 【解答】

#include class RecurveArray { private:

int *Elements; int ArraySize; int CurrentSize; public :

RecurveArray ( int MaxSize =10 ) :

ArraySize ( MaxSize ), Elements ( new int[MaxSize] ){ } ~RecurveArray ( ) { delete [ ] Elements; } void InputArray(); int MaxKey ( int n ); int Sum ( int n );

};

//输入数组的内容 //求最大值 //求数组元素之和 //求数组元素的平均值

//数组指针 //数组尺寸

//当前已有数组元素个数

//数组类声明

float Average ( int n );

void RecurveArray :: InputArray ( ){

int RecurveArray :: MaxKey ( int n ) {

int RecurveArray :: Sum ( int n ) {

if ( n == 1) return Elements[0]; else return Elements[n-1] + Sum (n-1); }

//递归求数组之和

if ( n == 1 ) return Elements[0]; int temp = MaxKey ( n - 1 );

if ( Elements[n-1] > temp ) return Elements[n-1]; else return temp; }

//递归求最大值

//输入数组的内容

cout << \;

for ( int i = 0; i < ArraySize; i++ ) cin >> Elements[i]; }

93

float RecurveArray :: Average ( int n ) {

int main ( int argc, char* argv [ ] ) { int size = -1;

cout << \; while ( size < 1 ) cin >> size; RecurveArray ra ( size ); ra.InputArray();

cout<< \ \ << endl; cout<< \ \endl; cout<< \ \endl; return 0; }

if ( n == 1) return (float) Elements[0];

else return ( (float) Elements[n-1] + ( n - 1) * Average ( n - 1 ) ) / n; }

//递归求数组的平均值

5-2 已知Ackerman函数定义如下：

(n?m)or(n?0)n?1,?nn?1? Cm?, otherwiseCCm-1m?1? (1) 根据定义，写出它的递归求解算法；

(2) 利用栈，写出它的非递归求解算法。 【解答】

(1) 已知函数本身是递归定义的，所以可以用递归算法来解决：

unsigned akm ( unsigned m, unsigned n ) { if ( m == 0 ) return n+1;

// m == 0 // m > 0, n == 0 // m > 0, n > 0

else if ( n == 0 ) return akm ( m-1, 1 ); }

else return akm ( m-1, akm ( m, n-1 ) );

(2) 为了将递归算法改成非递归算法，首先改写原来的递归算法，将递归语句从结构中独立出来：

unsigned akm ( unsigned m, unsigned n ) { unsigned v;

if ( m == 0 ) return n+1; v = akm ( m, n-1 ) ); return akm ( m-1, v ); }

// m == 0 // m > 0, n ==0 // m > 0, n > 0

if ( n == 0 ) return akm ( m-1, 1 );

计算akm(2, 1)的递归调用树如图所示：

94

akm = 5 akm(2, 1) v = 3 akm = 5 v =akm(2, 0) akm(1, 3)

v = 4

akm(1, 1) akm = 3 v = akm(1, 2) akm(0, 4) = 5

v = 2 v = 3

v =akm(1, 0) akm(0, 2) = 3 v = akm(1, 1) akm(0, 3) = 4

v = 2

akm(0, 1) = 2 v = akm(1, 0) akm(0, 2) = 3 akm(0, 1) = 2 用到一个栈记忆每次递归调用时的实参值，每个结点两个域{vm, vn}。对以上实例，栈的变化如下：

vm vn vm vn vm vn vm vn vm vn vm vn 1 0 0 1 2 0 1 1 1 1 1 1 0 2 2 1 2 1 2 1 2 1 2 1 1 3 改akm(m-1,1) 改akm(m-1,1) v = n+1= 2 改akm(m-1,v) 改akm(m-1,v) v = n+1 = 3

vm vn vm vn vm vn vm vn vm vn vm vn

1 0 0 1 1 1 1 1 0 2 1 2 1 2 1 2 0 3 1 3 1 3 1 3 1 3 0 4 改akm(m-1,1) v = n+1 = 2 改akm(m-1,v) 改akm(m-1,v) 改akm(m-1,v) 栈空, 返回v = 5 v = n+1 = 3 v = n+1 = 4 v = n+1 = 5

相应算法如下

#include

#include “stack.h” #define maxSize 3500;

unsigned akm ( unsigned m, unsigned n ) { struct node { unsigned vm, vn; }

stack st ( maxSize ); node w; unsigned v;

w.vm = m; w.vn = n; st.Push (w);

do {

while ( st.GetTop( ).vm > 0 ) {

while ( st.GetTop( ).vn > 0 ) { w.vn--; st.Push( w ); } w = st.GetTop( ); st.Pop( );

95

//计算akm(m-1, 1) //直到akm( 0, akm( 1, * ) ) //计算v = akm( 1, * )+1

//如果栈不空, 改栈顶为( m-1, v )

w.vm--; w.vn = 1; st.Push( w );

v = w.vn++;

//计算akm(m-1, akm(m, n-1) )

//计算akm(m, n-1), 直到akm(m, 0)

}

w = st.GetTop(); st.Pop( ); if ( st.IsEmpty( ) == 0 )