数据结构递归与广义表.doc

  1. 1、本文档共16页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构递归与广义表

第5章 递归与广义表 一、复习要点 本章主要讨论递归过程和广义表。一个递归的定义可以用递归的过程计算,一个递归的数据结构可以用递归的过程实现它的各种操作,一个递归问题也可以用递归的过程求解。因此,递归算法的设计是必须掌握的基本功。递归算法的一般形式: void p ( 参数表 ) { if ( 递归结束条件) 可直接求解步骤; 基本项 else p ( 较小的参数 ); 归纳项 } 在设计递归算法时,可以先考虑在什么条件下可以直接求解。如果可以直接求解,考虑求解的步骤,设计基本项;如果不能直接求解,考虑是否可以把问题规模缩小求解,设计归纳项,从而给出递归求解的算法。必须通过多个递归过程的事例,理解递归。但需要说明的是,递归过程在时间方面是低效的。 广义表是一种表,它的特点是允许表中套表。因此,它不一定是线性结构。它可以是复杂的非线性结构,甚至允许递归。可以用多重链表定义广义表。在讨论广义表时,特别注意递归在广义表操作实现中的应用。 本章复习的要点: 1、基本知识点 要求理解递归的概念:什么是递归?递归的定义、递归的数据结构、递归问题以及递归问题的递归求解方法。理解递归过程的机制与利用递归工作栈实现递归的方法。通过迷宫问题,理解递归解法,从而掌握利用栈如何实现递归问题的非递归解法。在广义表方面,要求理解广义表的概念,广义表的几个性质,用图表示广义表的方法,广义表操作的使用,广义表存储结构的实现,广义表的访问算法,以及广义表的递归算法。 2、算法设计 ( 求解汉诺塔问题,掌握分治法的解题思路。 ( 求解迷宫问题、八皇后问题,掌握回溯法的解题思路。 ( 对比单链表的递归解法和非递归解法,掌握单向递归问题的迭代解法。 ( 计算广义表结点个数,广义表深度,广义表长度的递归算法。 ( 输出广义表各个原子所在深度的非递归算法。 ( 判断两个广义表相等的递归算法。 ( 广义表的按深度方向遍历和按层次(广度)方向遍历的递归算法。 ( 使用栈的广义表的按深度方向遍历的非递归算法。 ( 递归的广义表的删除算法 二、难点与重点 1、递归:递归的定义、递归的数据结构、递归问题用递归过程求解 ( 链表是递归的数据结构,可用递归过程求解有关链表的问题 2、递归实现时栈的应用 ( 递归的分层(树形)表示:递归树 ( 递归深度(递归树的深度)与递归工作栈的关系 ( 单向递归与尾递归的迭代实现 3、广义表:广义表定义、长度、深度、表头、表尾 用图形表示广义表的存储结构 广义表的递归算法,包括复制、求深度、求长度、删除等算法 三、教材中习题的解析 5-1 已知A[n]为整数数组,试写出实现下列运算的递归算法: (1) 求数组A中的最大整数。 (2) 求n个整数的和。 (3) 求n个整数的平均值。 【解答】 #include iostream.h 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 ( ){ //输入数组的内容 cout Input the number of Array: \n; for ( int i = 0; i ArraySize; i++ ) cin Elements[i]; } int RecurveArray :: MaxKey ( int n ) { //递归求最大值 if ( n == 1 ) return Elements[0]; int temp = MaxKey ( n - 1 ); if ( Elements[n-1] temp )

文档评论(0)

shenlan118 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档