《数据结构递归与广义表》由会员分享，可在线阅读，更多相关《数据结构递归与广义表（17页珍藏版）》请在金锄头文库上搜索。
1、92第 5 章 递归与广义表一、复一、复习习要点要点本章主要讨论递归过程和广义表。一个递归的定义可以用递归的过程计算，一个递归 的数据结构可以用递归的过程实现它的各种操作，一个递归问题也可以用递归的过程求解。 因此，递归算法的设计是必须掌握的基本功。递归算法的一般形式： void p ( 参数表 ) if ( 递归结束条件)可直接求解步骤； 基本项 else p ( 较小的参数 ); 归纳项 在设计递归算法时，可以先考虑在什么条件下可以直接求解。如果可以直接求解，考 虑求解的步骤，设计基本项；如果不能直接求解，考虑是否可以把问题规模缩小求解，设 计归纳项，从而给出递归求解的算法。必须通过多个递
2、归过程的事例，理解递归。但需要 说明的是，递归过程在时间方面是低效的。 广义表是一种表，它的特点是允许表中套表。因此，它不一定是线性结构。它可以是 复杂的非线性结构，甚至允许递归。可以用多重链表定义广义表。在讨论广义表时，特别 注意递归在广义表操作实现中的应用。 本章复习的要点： 1、基本知识点 要求理解递归的概念：什么是递归？递归的定义、递归的数据结构、递归问题以及递 归问题的递归求解方法。理解递归过程的机制与利用递归工作栈实现递归的方法。通过迷 宫问题，理解递归解法，从而掌握利用栈如何实现递归问题的非递归解法。在广义表方面， 要求理解广义表的概念，广义表的几个性质，用图表示广义表的方法，广
3、义表操作的使用， 广义表存储结构的实现，广义表的访问算法，以及广义表的递归算法。 2、算法设计 求解汉诺塔问题，掌握分治法的解题思路。 求解迷宫问题、八皇后问题，掌握回溯法的解题思路。 对比单链表的递归解法和非递归解法，掌握单向递归问题的迭代解法。 计算广义表结点个数，广义表深度，广义表长度的递归算法。 输出广义表各个原子所在深度的非递归算法。 判断两个广义表相等的递归算法。 广义表的按深度方向遍历和按层次（广度）方向遍历的递归算法。 使用栈的广义表的按深度方向遍历的非递归算法。 递归的广义表的删除算法二、二、难难点与重点点与重点1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解 链
4、表是递归的数据结构，可用递归过程求解有关链表的问题 2、递归实现时栈的应用 递归的分层(树形)表示：递归树递归深度(递归树的深度)与递归工作栈的关系93单向递归与尾递归的迭代实现 3、广义表：广义表定义、长度、深度、表头、表尾 用图形表示广义表的存储结构 广义表的递归算法，包括复制、求深度、求长度、删除等算法三、教材中三、教材中习题习题的解析的解析5-1 已知 An为整数数组，试写出实现下列运算的递归算法： (1) 求数组 A 中的最大整数。 (2) 求 n 个整数的和。 (3) 求 n 个整数的平均值。 【解答】#include class RecurveArray /数组类声明privat
5、e:int *Elements;/数组指针int ArraySize;/数组尺寸int CurrentSize;/当前已有数组元素个数public :RecurveArray ( int MaxSize =10 ) :ArraySize ( MaxSize ), Elements ( new intMaxSize ) RecurveArray ( ) delete Elements; void InputArray();/输入数组的内容int MaxKey ( int n );/求最大值int Sum ( int n );/求数组元素之和float Average ( int n );/求数组
6、元素的平均值;void RecurveArray : InputArray ( )/输入数组的内容cout Elementsi;int RecurveArray : MaxKey ( int n ) /递归求最大值if ( n = 1 ) return Elements0;int temp = MaxKey ( n - 1 );if ( Elementsn-1 temp ) return Elementsn-1;else return temp;int RecurveArray : Sum ( int n ) /递归求数组之和if ( n = 1) return Elements0;else
7、return Elementsn-1 + Sum (n-1);94float RecurveArray : Average ( int n ) /递归求数组的平均值if ( n = 1) return (float) Elements0;else return ( (float) Elementsn-1 + ( n - 1) * Average ( n - 1 ) ) / n;int main ( int argc, char* argv ) int size = -1;cout size;RecurveArray ra ( size );ra.InputArray();cout 0, n =
8、 0else return akm ( m-1, akm ( m, n-1 ) ); / m 0, n 0(2) 为了将递归算法改成非递归算法，首先改写原来的递归算法，将递归语句从结构 中独立出来：unsigned akm ( unsigned m, unsigned n ) unsigned v;if ( m = 0 ) return n+1;/ m = 0if ( n = 0 ) return akm ( m-1, 1 );/ m 0, n =0v = akm ( m, n-1 ) ); / m 0, n 0return akm ( m-1, v );计算 akm(2, 1)的递归调用树如
9、图所示：95用到一个栈记忆每次递归调用时的实参值，每个结点两个域vm, vn。对以上实例， 栈的变化如下：相应算法如下#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 ) /计算 akm(m-1, akm(m,
10、n-1) )while ( st.GetTop( ).vn 0 ) /计算 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 =
11、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) = 5 v = 2v = 2v = 3v = 4v = 3akm = 5akm = 5akm = 32 1 2 1 2 1 2 1 2 1 1 32 0 1 1 1 1 1 1 0 21 0 0 1 改 akm(m-1,1) 改 akm(m-1,1) v = n+1= 2 改 akm(m-1,
12、v) 改 akm(m-1,v)v = n+1 = 3vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn 1 3 1 3 1 3 1 3 0 4 1 2 1 2 1 2 0 3 1 1 1 1 0 2 1 0 0 1 改 akm(m-1,1) v = n+1 = 2 改 akm(m-1,v) 改 akm(m-1,v) 改 akm(m-1,v) 栈空, 返回 v = 5v = n+1 = 3 v = n+1 = 4 v = n+1 = 596 w = st.GetTop(); st.Pop( ); w.vm
13、-; w.vn = v; st.Push( w ); while ( st.IsEmpty( ) = 0 );return v; 5-3 【背包问题】设有一个背包可以放入的物品的重量为 s，现有 n 件物品，重量分别为 w1, w2, , wn。问能否从这 n 件物品中选择若干件放入此背包中，使得放入的重量之 和正好为 s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否 则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。 （提示：此 背包问题的递归定义如下：）) 1,(10 ) 1,(10False0False0True),(时所选物品中包括时所选
14、物品中不包括且或物品件数不能为负数且总重量不能为负数此时背包问题一定有解nwnnwsKNAPnwnsnsKNAPnsssnsKNAP【解答】 根据递归定义，可以写出递归的算法。enum boolean False, True boolean Knap( int s, int n ) if ( s = 0 ) return True;if ( s 0 class ListNode /链表结点类0# 主对角线 1# 主对角线 2# 主对角线 3# 主对角线 4# 主对角线 5# 主对角线 6# 主对角线6# 次对角线5# 次对角线4# 次对角线3# 次对角线2# 次对角线0# 次对角线 1# 次对角线0 1 2 30123 99friend class List;private:int data;/结点数据ListNode *link;/结点指针public:ListNode ( const int item ) : data(item), link(NULL) /构造函数;class List /链表类private:ListNode *first, current;int Max ( ListNode *f );int Num ( ListNode *f );float Avg (
