辽宁石油化工大学数据结构课件-递归及广义表.ppt

辽宁石油化工大学数据结构课件-递归及广义表.ppt

  1. 1、本文档共61页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
递归的概念 递归过程与递归工作栈 递归与回溯 广义表 递归的概念 递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的;若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 以下三种情况常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的 定义是递归的 求解阶乘 n! 的过程 在链表中寻找等于给定值的结点并打印其数值 template class Type void Print ( ListNodeType *f, Type x ) { if ( f != NULL ) if ( f - data == x ) cout f - data endl; else Print ( f - link, x ); } 递归过程与递归工作栈 递归过程在实现时,需要自己调用自己。 层层向下递归,退出时的次序正好相反: 递归调用 n! (n-1)! (n-2)! 1! 0!=1 返回次序 主程序第一次调用递归过程为外部调用; 递归过程每次递归调用自己为内部调用。 它们返回调用它的过程的地址不同。 递归工作栈 每一次递归调用时,需要为过程中使用的参数、局部变量等另外分配存储空间。 每层递归调用需分配的空间形成递归工作记录,按后进先出的栈组织。 函数递归时的活动记录 递归过程改为非递归过程 递归过程简洁、易编、易懂 递归过程效率低,重复计算多 改为非递归过程的目的是提高效率 单向递归和尾递归可直接用迭代实现其非递归过程 其他情形必须借助栈实现非递归过程 long Fibnacci ( long n ) { StackNode S; Node *w; long sum = 0; //反复执行直到所有终端结点数据累加完 do { while ( n 1 ) { w-n = n; w-tag = 1; S.push ( w ); n--; } //向左递归到底, 边走边进栈 sum = sum + n; //执行求和 while ( !S.IsEmpty( ) ) { w = S.getTop( ); S.Pop( ); if ( w-tag == 1 ) { //改为向右递归 w-tag = 2; S.push ( w ); n = w-n – 2; //F(n)右侧为F(n-2) break; } } } while ( !S.IsEmpty( ) ); return sum; } 单向递归用迭代法实现 long FibIter ( long n ) { if ( n = 1 ) return n; long twoback = 0, oneback = 1, Current; for ( int i = 2; i = n; i++ ) { Current = twoback + oneback; twoback = oneback; oneback = Current; } return Current; } 尾递归用迭代法实现 递归与回溯 常用于有哪些信誉好的足球投注网站过程 n皇后问题 在 n 行 n 列的国际象棋棋盘上,若两个皇后位于同一行、同一列、同一对角线上,则称为它们为互相攻击。n皇后问题是指找到这 n 个皇后的互不攻击的布局。 解题思路 安放第 i 行皇后时,需要在列的方向从 0 到 n-1 试探 ( j = 0, …, n-1 ) 在第 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] : q[i] 记录第 i 行皇后在第几列 void Queen( in

文档评论(0)

134****9291 + 关注
实名认证
内容提供者

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

1亿VIP精品文档

相关文档