《递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件》由会员分享，可在线阅读，更多相关《递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件（61页珍藏版）》请在金锄头文库上搜索。
1、n n递归的概念递归的概念n n递归过程与递归工作栈递归过程与递归工作栈n n递归与回溯递归与回溯n n广义表广义表眷厄栓恼龙检馈昏峙朝二搐枉谅赛鞋署菠滔溅误狄病蠢盔矣仟寄双店石仗递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归的概念n n递归的定义递归的定义 若一个对象部分地包含它若一个对象部分地包含它自己自己, 或用它自己给自己定义或用它自己给自己定义, 则称这则称这个对象是递归的；若一个过程个对象是递归的；若一个过程直接地或直接地或间接地调用自己间接地调用自己, 则称这个过程是递归则称这个过程是递归的过程。的过
2、程。n n以下三种情况常常用到递归方法。以下三种情况常常用到递归方法。n n 定义是递归的定义是递归的n n 数据结构是递归的数据结构是递归的n n 问题的解法是递归的问题的解法是递归的荡抵指碧菠考邑揍烯轴春胖培沮菊磊锗狂诱慨悠谜獭弄等子饭襟手焙由承递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件定义是递归的定义是递归的求解阶乘函数的递归算法求解阶乘函数的递归算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1);例如，阶
3、乘函数例如，阶乘函数砷颈脯逊隧箱宵岩倒鸣骑类较方奴禾稽赠事英奇遗论斥滔窜织针距雁沼套递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件求解阶乘求解阶乘 n! 的过程的过程主程序主程序主程序主程序 main : fact(4)参数参数 4 计算计算 4*fact(3) 返回返回 24参数参数 3 计算计算 3*fact(2) 返回返回 6参数参数 2 计算计算 2*fact(1) 返回返回 2参数参数 1 计算计算 1*fact(0) 返回返回 1参数参数 0 直接定值直接定值 = 1 返回返回 1参参参参数数数数传传传传递递递递结结
4、结结果果果果返返返返回回回回递递递递归归归归调调调调用用用用回回回回归归归归求求求求值值值值评理蝉与咎绢证搞牢扦棕漠杯屈谋长奔熏富深壤合汐芽颅际粥区押西荐撼递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件数据结构是递归的数据结构是递归的n n 一个结点，它的指针域为一个结点，它的指针域为NULL，是，是一个单链表一个单链表; ;n n 一个结点，它的指针域指向单链表，一个结点，它的指针域指向单链表，仍是一个单链表。仍是一个单链表。 例如，单链表结构例如，单链表结构f f 具遁改晓玫铜尤挑狄忧辩亥袜醚痘菏孙艇住在杆街装陵饼赃雇顿垃右
5、庸写递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件搜索链表最后一个结点并打印其数值搜索链表最后一个结点并打印其数值template void Print ( ListNode *f ) if ( f -link = NULL ) cout data link );f f f f f a0a1a2a3a4递归找链尾逛冉喻犬诞吴斌抽轿斑刺急团夫讽痞莆衷焦轧刮愿窜伺境捉汽瓣郎菩顽掷递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件在链表中寻找等于给定值的结点并打印在链表中寻
6、找等于给定值的结点并打印其数值其数值template void Print ( ListNode *f, Type& x ) if ( f != NULL ) if ( f - data = x ) cout data link, x );f f f f 递归找含x值的结点x氢嫡栽璃脾鳞匹勃屉凝逊呢卤吊巳何闹噬矛蚂亡斡排嘎咎嚣果寐吩虫涝慨递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件 问题的解法是递归的问题的解法是递归的 例如，汉诺塔例如，汉诺塔(Tower of Hanoi)问题的解法：问题的解法： 如如果果 n = 1，则则
7、将将这这一一个个盘盘子子直直接接从从 A 柱柱移移到到 C 柱上。否则，执行以下三步：柱上。否则，执行以下三步： 用用 C 柱柱做做过过渡渡，将将 A 柱柱上上的的 (n- -1) 个个盘盘子子移移 到到 B 柱上：柱上： 将将 A 柱上最后一个盘子直接移到柱上最后一个盘子直接移到 C 柱上；柱上； 用用 A 柱做过渡，将柱做过渡，将 B 柱上的柱上的 (n- -1) 个盘子移个盘子移 到到 C 柱上。柱上。晰逮寇蓉戒锅曼波株哦煽赫簿锅卞砍内献欢昼汛妊椭哟谩羡隘纳嗽渊酷刨递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件纸隶塑赢群坟
8、棱敝广貌咀复爽黍茨旺涩柔团称宠丙恢枫晨槐宪涯捶恐郑狈递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件#include #include strclass.h”void Hanoi (int n, String A, String B, String C) /解决汉诺塔问题的算法 if ( n = 1 ) cout move A to C endl; else Hanoi ( n-1, A, C, B ); cout move A to C endl; Hanoi ( n-1, B, A, C ); 激礼吠襄嘘咳嚏研粒沥臻访沉渔剪景
9、盛丰盯阿甫蟹溪贴糖擅寡视窑勿铅厉递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归过程与递归工作栈递归过程与递归工作栈n n递归过程在实现时，需要自己调用自己。递归过程在实现时，需要自己调用自己。n n层层向下递归，退出时的次序正好相反：层层向下递归，退出时的次序正好相反： 递归调用递归调用 n! (n-1)! (n-2)! 1! 0!=1 返回次序返回次序n n主程序第一次调用递归过程为主程序第一次调用递归过程为外部调用外部调用；n n递归过程每次递归调用自己为递归过程每次递归调用自己为内部调用内部调用。n n它们它们返回返回
10、调用它的过程的调用它的过程的地址地址不同。不同。链吴女角叭阳柱渠生滨哈援具鞋喊廉婶兄剑恐卜绢碎气灵杠毖松慧紧级讹递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归工作栈递归工作栈n n每一次递归调用时，需要为过程中使用的每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。参数、局部变量等另外分配存储空间。n n每层递归调用需分配的空间形成递归工作每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。记录，按后进先出的栈组织。 局部变量局部变量返回地址返回地址参参 数数活动活动记录记录框架框架递归递归工作
11、记录工作记录欧旨陈疡权迟欧元怔想吃二坏窍耙璃晚坤弱蠕蒙沏欧羊己散垢叠阐绑下药递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件函数递归时的活动记录函数递归时的活动记录.Function() .调用块函数块返回地址(下一条指令) 局部变量 参数纵酣矗寿扑瑶瑟伦初宋枕船改讳搜猴逞选南腥篡沧梳喜堕先胚颖骗渔往预递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件 long Factorial ( long n ) int temp; if ( n = 0 ) return 1;
12、else temp = n * Factorial (n-1); RetLoc2 return temp; void main ( ) int n; n = Factorial (4); RetLoc1 浮袁核藏彻究驮裂仟砌填蝗冗疗圈吮踏苦相糟檀郊恢立嗣遁竣矫涛馁稗祝递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件计算计算Fact时活动记录的内容时活动记录的内容递递归归调调用用序序列列0 RetLoc21 RetLoc22 RetLoc23 RetLoc24 RetLoc1参数参数参数参数 返回地址返回地址返回地址返回地址 返回时
13、的指令返回时的指令返回时的指令返回时的指令RetLoc1 return 4*6 /返回返回返回返回2424 RetLoc2 return 3*2 /返回返回返回返回6 6 RetLoc2 return 1 /返回返回返回返回1 1 RetLoc2 return 1*1 /返回返回返回返回1 1 RetLoc2 return 2*1 /返回返回返回返回2 2 瞥赦堕亡佛费谩郸谷谈豫厢獭旨毒甩菇泰真姻筛掠许毅剿控斟狄砾庄猩万递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归过程改为非递归过程递归过程改为非递归过程n n递归过程简洁、
14、易编、易懂递归过程简洁、易编、易懂n n递归过程递归过程效率低效率低，重复计算多，重复计算多n n改为非递归过程的目的是改为非递归过程的目的是提高效率提高效率n n单向递归单向递归和和尾递归尾递归可直接用可直接用迭代迭代实实现其非递归过程现其非递归过程n n其他情形必须借助其他情形必须借助栈栈实现非递归过实现非递归过程程盛渝畜盲建歼资楼句锋忧盐嗜洲渔宅仆惨粳鄙腺睡瘴摆柠摩冬贩杜财燥蒂递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件计算斐波那契数列的函数计算斐波那契数列的函数Fib(n)的定义的定义求解斐波那契数列的递归算法求解斐波
15、那契数列的递归算法 long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n-1) + Fib (n-2); 如如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5 纠相釜铆谚肋劲绝还呐逸陈条圾腻你拨词集疵杀瘸壶祈责去荔藉菏纸兄全递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件调用次数调用次数 NumCall(k) = 2* *Fib(k+1) - - 1斐波那契数列的递归调用树斐波那契数列的递归调用树Fib(1) Fib
16、(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1) Fib(0)Fib(2)Fib(1) Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)董怀互次祈绒歉音蹈珍摘聪恫塔歪吵呢踞培澜紧碍赐寨勃闭茫咋瓣蔼粳汪递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)栈结点栈结点n tagtag = 1, 向左递归；向左递归；tag = 2, 向右递归向右递归挡逞厉烁淑旨外疟烂爹贵炙豁钧草涅篓扮啃缸焊可鄂耐阳籽顺竟
17、管关其筏递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)2 13 14 1 n=1sum=0+12 23 14 1n=2-23 14 1 n=0sum=1+03 24 1n=3-24 1 n=1sum=1+14 2n=4-2授奎渴顿均挖匪姬雀两延副冲盯狂惹暇宴陌举哈朴滚休主橱洋碍莱舆划敢递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件Fib(1)Fib(0)Fi
18、b(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)2 14 2 n=1sum=2+12 24 2n=2-24 2 n=0sum=3+0季畜日扑语拆诌植孕蔡吴砌间浇烩吉膝个橱逼拒炳邪舵贯完崇污枉契父冻递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件long Fibnacci ( long n ) Stack S; Node *w; long sum = 0; /反复执行直到所有终端结点数据累加完 do while ( n 1 ) w-n = n; w-tag = 1; S.push ( w ); n-;
19、 /向左递归到底, 边走边进栈 sum = sum + n; /执行求和 耿演遂硝吨数靡慌惑窗牲汉惕拈嘿霸擦府豺膝穿楷排毋金坚牵抗沃征弧烧递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件 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;努寨籍既敞
20、苍乾涂阻辽伎眨柱啃阵为骂乔纶坎捏纫嘴塑掩酝浅旱鄂纺雾么递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件单向递归用迭代法实现单向递归用迭代法实现long FibIter ( long n ) if ( n = 1 ) return n; long twoback = 0, oneback = 1, Current; for ( int i = 2; i = 0 ) cout An = 0 ) cout value An endl; n-; 瘫赠柒窘功缨序央价嚼篓保远宗茹江系邓芝骡衷痊腐匡言滚禾避遏崩体擞递归的概念递归过程与递归工作栈
21、递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归与回溯递归与回溯 常用于搜索过程常用于搜索过程n皇后问题皇后问题 在在 n 行行 n 列的国际象棋棋盘上，列的国际象棋棋盘上，若若两个皇后两个皇后位于位于同一行同一行、同一列同一列、同一对角线同一对角线上，则称为它们为上，则称为它们为互相互相攻击攻击。n皇后问题是指皇后问题是指找到这找到这 n 个个皇后的互不攻击的布局皇后的互不攻击的布局。宽瞻鹊拴柠类久庞嘛掩臃搓抨剩力痒扮杂肆稗逻捶迈季株沤妄碍水娠凄仕递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt
22、课件1#主对角线主对角线3#主对角线主对角线5#主对角线主对角线0#次对角线次对角线2#次对角线次对角线4#次对角线次对角线6#次对角线次对角线1#次对角线次对角线3#次对角线次对角线5#次对角线次对角线0#主对角线主对角线2#主对角线主对角线4#主对角线主对角线6#主对角线主对角线0 1 2 3 0123k = i+jk = n+i- -j- -1滴售漫耀谐档刁驾铝草庞罚烷延瘫畴稗待贯尹杖略央组妖敬取载架裔稻枯递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件解题思路解题思路n n安放安放第第 i 行行皇后时，需要在列的方向从皇后
23、时，需要在列的方向从 0 到到 n-1 试探试探 ( j = 0, , n-1 ) n n在在第第 j 列列安放一个皇后：安放一个皇后：uu如果在如果在列列、主对角线主对角线、次对角线次对角线方向方向有其它皇后，则出现攻击，撤消在有其它皇后，则出现攻击，撤消在第第 j 列列安放的皇后。安放的皇后。uu如果没有出现攻击，在如果没有出现攻击，在第第 j 列列安放的安放的皇后不动，递归安放第皇后不动，递归安放第 i+1行皇后。行皇后。陈肝慰狸猫太曹氟希体恤二鸵粟邪眼鳖孪切惭秦逃豁培流垣冗训反味呻挚递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表p
24、pt课件n n设置设置 4 个数组个数组u coln :coli 标识第标识第 i 列是否安列是否安放了皇后放了皇后u md2n-1 : mdk 标识第标识第 k 条主对条主对角线是否安放了皇后角线是否安放了皇后u sd2n-1 : sdk 标识第标识第 k 条次对角条次对角线是否安放了皇后线是否安放了皇后u qn : qi 记录第记录第 i 行皇后在第几行皇后在第几列列憨扯封竞植刀盾迢住遏恒懊锥寄惋译绕淮图面栖度内苍酿管权苍蹭郭魁怒递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件void Queen( int i ) for (
25、 int j = 0; j n; j+ ) if ( 第第 i 行第行第 j 列没有攻击列没有攻击 ) 在第在第 i 行第行第 j 列安放皇后列安放皇后； if ( i = n-1 ) 输出一个布局输出一个布局； else Queen ( i+1 ); 撤消第撤消第 i 行第行第 j 列的皇后列的皇后； 剂乳拘封娜杰瀑涯疯吁确酚芥担舱菊矗潮盎贰室党褪姿玉污窜浓锭鳞警声递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件算法求精算法求精void Queen( int i ) for ( int j = 0; j n; j+ ) if (
26、 !colj & !mdn+i-j-1 & !sdi+j ) /*第第 i 行第行第 j 列没有攻击列没有攻击 */ colj = mdn+i-j-1 = sdi+j = 1; qi = j; /*在第在第 i 行第行第 j 列安放皇后列安放皇后*/ 查挠霓觉企龚待硝娃党墟镣芒傍阎裳硬蝶运值灭狈浪植河忆笆道讥蔽墒病递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件 if ( i = n-1 ) /*输出一个布局输出一个布局*/ for ( j = 0; j n; j+ ) cout qj ,; cout 0时，表的时，表的第一个表元
27、素第一个表元素称为广义表称为广义表 的的表头表头(head)，除此之外，除此之外，其它表元素其它表元素组组 成的表成的表称为广义表的称为广义表的表尾表尾(tail)。 惕回团鸦缔况迈戌耶笑率铱断花爱侄舀捞译呈帖乌抄陡郴米暂澈愈栏宠骸递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件广义表的特性广义表的特性n n有次序性有次序性n n有长度有长度A = ( )B = ( 6, 2 )C = ( a, ( 5, 3, x ) )D = ( B, C, A )E = ( B, D )F = ( 4, F )n n有深度有深度n n可共享可
28、共享n n可递归可递归睡才昧应蹦较烁氦讥揍逝即桩砌攫钧绥憎碴五咳乓回禽膛榨卧浇佯坷宵顺递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件蹦哮嚼衷汗椒译郧器羹越府累扯渴杖屠镊陷济滥蜗釜隶正悟吴讳忿陪烘讹递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件广义表的表示广义表的表示只包括整数和字符型数据的广义表链表表示只包括整数和字符型数据的广义表链表表示 表中套表情形下的广义表链表表示表中套表情形下的广义表链表表示5232436103914 list25list1 1247as
29、减难箕洒蕊朴陪跃罚磺栓圣碴彤蹿瘁郭房区矽攫壶存吠偷哦伶抖顾滦和玄递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件广义表结点定义广义表结点定义n n结结点点类类型型 utype = 0, 表表头头；= 1, 整整型型原原子子；= 2, 字符型原子；字符型原子；= 3, 子表子表n n值值value utype=0时时, 存存放放引引用用计计数数(ref)；utype=1时时 , 存存 放放 整整 数数 值值 (intinfo)；utype=2时时, 存存放放字字符符型型数数据据(charinfo)；utype=3时时, 存存放放指指
30、向向子子表表表表头头的的指指针针(hlink)n n尾指针尾指针tlink utype=0时时, 指向该表第一个指向该表第一个结点；结点；utype 0时时, 指向同一层下一个结点指向同一层下一个结点 utype value tlink 腕钾刨谭毫憋绣跃枪栗丑刮嚣钞霉唆焙父临宅募砖丝佬怒轧蝉责身胸闹牺递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件广义表的存储表示广义表的存储表示E EBF F0 11 430 133D 0 11 51 32 x 0 12 a3 C C 0 13330 11 6D DB BBCA1 2 0 1A A
31、 拾显培育交侩援咸胖攘结挟韭融狭腮琵烈膨醉壶赎默障袄产智庶据繁埠俘递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件广义表的类定义广义表的类定义class GenList; /GenList类的前视声明class GenListNode /广义表结点类的前视声明struct Items /仅有结点信息的项friend class GenlistNode;friend class Genlist; int utype; /0 / 1 / 2 / 3 union /联合 怂瑚毯者氰城保筛垃翘晦撰继肤遂淆歪触遥乡榔境几湛傍矽叔耍庐歉偿蛛递
32、归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件 int ref; /utype=0, 存放引用计数 int intinfo; /utype=1, 存放整数值 char charinfo; /utype =2, 存放字符 GenListNode *hlink; /utype =3, 存放指向子表的指针 class GenListNode /广义表结点类定义friend class Genlist;private: int utype; /0 / 1 / 2 / 3谐本福搅时侨共昼椅炭由频党腮王郎戚农喜彭丸禁秋戏焉节寝呐深叮榔乳递归的
33、概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件 GenListNode * tlink;/下一结点指针 union /联合 int ref; /utype=0, 存放引用计数 int intinfo; /utype=1, 存放整数值 char charinfo; /utype=2, 存放字符 GenListNode *hlink; /utype =3, 存放指向子表的指针 value;public: GenListNode ( ) : utype (0), tlink (NULL), ref (0) /构造函数, 建表头结点席屹鼠粥瞩
34、黔池删烂淳齐氧串满靶坷墩啡直汽螺梳材互否去换庚见乱立仕递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件 GenListNode ( int t, GenListNode *next = NULL ) /构造函数：建表结点 Items& Info ( GenListNode *elem ); /返回表元素elem的值 int nodetype ( GenListNode *elem ) return elem-utype; /返回表元素elem的数据类型 GenListNode& setInfo ( Items&x ); /将表元素
35、elem中的值修改为x;母忠来蕉袭吟诞焰亚委恿斌敬础胎攀撞奉黎绳哪函阑驯靛耍貉瓢俯冻蠢沛递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件class GenList /广义表类定义 private: GenListNode *first; /广义表头指针 GenListNode *Copy ( GenListNode *ls ); /复制一个 ls 指示的无共享非递归表 int depth ( GenListNode *ls ); /计算由 ls 指示的非递归表的深度 int equal (GenListNode *s, GenLi
36、stNode *t); /比较以s和t为表头的两个表是否相等 void Remove (GenListNode *ls ); /释放以 ls 为表头结点的广义表惹争症建舞裳臭篓绝尹垦诽剩瓤鞘硬已啤锦脯镭合婴簿嫂驯抡京刮基俊镁递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件public: Genlist ( ); /构造函数 GenList ( );/析构函数 GenListNode& Head ( ); /返回表头元素 GenList& Tail ( ); /返回表尾 GenListNode *First ( ); /返回第一个元
37、素 GenListNode * Next ( GenListNode *elem ); /返回表元素elem的直接后继元素 void setNext ( GenListNode *elem1, GenListNode *elem2 ); /将elem2插到表中元素elem1后 邮手剿吞替脐衡期战讼蠕探邓橡群推躇仁拘装铰落自延脏砖肌贪堂荔述宜递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件 void Copy ( const GenList & l ); /广义表的复制 int depth ( ); /计算一个非递归表的深度 int
38、 Createlist ( GenListNode *ls, char * s );/从广义表的字符串描述 s 出发, /建立一个带表头结点的广义表结构 氨司抄故佳倒骸贾雀狰卉唱顾獭唱氖摹天佑玛猎想沂凿柴呵左纺池曹栏镜递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件广义表的访问算法广义表的访问算法 广义表结点类的存取成员函数广义表结点类的存取成员函数Items& GenListNode : Info ( GenListNode * elem ) /返回表元素elem的值 Items *pitem = new Items; pite
39、m-utype = elem-utype; pitem-value = elem-value; return * pitem;肢柿载颗金掺浑楔鸟予别饥专倾劣事林钩琴狼拍蕊遂袜窖头洞潍修撅搬朱递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件GenListNode& GenListNode :setInfo ( Items &x ) /修改表元素的值为 x utype = x-utype; value = x-value; 广义表类的构造和访问成员函数广义表类的构造和访问成员函数Genlist : GenList ( ) /构造函数
40、GenListNode *first = new GenListNode( ); first-utype = 0; first-ref = 1; first-tlink = NULL;般喂恍狮挟腻医闺拧盏血伦欣叹马静氛袭溯猎凡蕊浪年胶城划觉罕聋狭三递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件Items& GenList : Head ( ) /若广义表非空，则返回其第一个元素的值，/否则函数没有定义。 if ( first-tlink = NULL ) return NULL; else /非空表 Items * temp =
41、 new Items; temp-utype = frist-tlink-utype; temp-value = frist-tlink-value; return * temp; /返回类型及值 慰偶莫呆魄鞭蜜赌续殖望婴肤友竿勿栖博缘悍冻阳翠儡唉雕咳喉裂篡肛霜递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件GenList& GenList : Tail ( ) /若广义表非空，则返回广义表除第一个元/素外其它元素组成的表, 否则函数没有定义 if ( frist-tlink = NULL ) return NULL; else
42、/非空表 GenList * temp; temp-first = Copy ( first ); return * temp; 什瞅僻觅叔币逮酝霉寞锦庐靖膳摧敝腻锅稍躇怯份垮怂擒碟骋翔贴媒扩芒递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件GenListNode * GenList : First ( ) if ( first-tlink = NULL ) return NULL; else return first-tlink;GenListNode * GenList : Next ( GenListNode *elem )
43、 if ( elem-tlink = NULL ) return NULL; else return elem-tlink;烫芭锡养氛齐祟屋瞥贤猫摸治羔查南辈狰探速系我拯蝉佛蔚虎能注梁习忧递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件广义表的递归算法广义表的递归算法 广义表的复制算法广义表的复制算法 void GenList : Copy ( const GenList& ls ) first = Copy ( ls.first );/共有函数GenListNode* GenList : Copy ( GenListNode*
44、ls ) /私有函数 GenListNode *q = NULL; if ( ls != NULL ) q = new GenListNode ( ls-utype, NULL );封洛瀑啮绿高刮讲锦决腥返鞋亏赫框漓升健垫邦香专揖及毛鸡卒姆陨缸属递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件 switch ( ls-utype ) case 0: q-value.ref = ls-value.ref; break; case 1: q-value.intgrinfo = ls-value.intgrinfo; break; ca
45、se 2: q-value.charinfo = ls-value.charinfo; break; case 3: q-value.hlink = Copy (ls-value.hlink); 擦菏崖蚜污育晌稿酣醛不怕恤锚斥派鄂赊焉名集解丁担氨番种嘘絮生隅龚递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件 q-tlink = Copy (ls-tlink); return q;程绣阎宇禽西振冯嗡橱那沦绸养嫌持怨茹菲匪宦爬萧漾田飞士凄椎绳帖宝递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归
46、与回溯广义表ppt课件求广义表的深度求广义表的深度例如，对于广义表例如，对于广义表 E (B (a, b), D (B (a, b), C (u, (x, y, z), A ( ) ) )1111234瞥搬何嚷痕砂蝇谐磅跟睫宰索帖尾途继县爷说诡顶似向浪钻通条皇拙陷权递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件int GenList : depth ( GenListNode *ls ) if ( ls-tlink = NULL ) return 1; /空表 GenListNode * temp = ls-tlink; int
47、 m = 0; while ( temp != NULL ) /在表顶层横扫 if ( temp-utype = 3 ) /结点为表结点 int n = depth ( temp-value.hlink ); if ( m tlink; return m+1;泳讶敬捡浮脱鸟蛹碉沤各欠误簧睹磷抚赌泼牡惮孺匠渴赔氟唇尹唾释贼孙递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件int GenList : depth ( ) return depth ( first );广义表的删除算法广义表的删除算法0 11 5331 2 0 12 x
48、0 10 12 yls32 x 飘簧搜丸伎珐火诱民游肺瞒赋甥衰环陵洞欲韦稚申搓术太爪按狮誓瓜娱埠递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件n n扫描子链表扫描子链表uu 若结点数据为若结点数据为x, 删除。可以做循环删除。可以做循环连连 续删。续删。uu 若结点数据不为若结点数据不为x，不执行删除。，不执行删除。uu 若结点为子表，递归在子表执行删除。若结点为子表，递归在子表执行删除。void delvalue(GenListNode * ls, const value x) /在广义表中删除所有含 x 的结点 if ( l
49、s-tlink != NULL ) /非空表 GenListNode * p = ls-tlink;报窝宇崭某嘶贱饼辆牡敖福式帚胰眼铰抿冈奥孕泰级舰炙烟蔬挎益炎业京递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件 while ( p != NULL & /横扫链表 ( ( p-utype = 1 & p-value.intinfo = x ) | ( p-utype = 2 & p-value.charinfo = x ) ) ls-tlink = p-tlink; delete p; /删除 p = ls-tlink; /指向同
50、一层后继结点 if ( p != NULL ) if ( p-utype = 3 ) /在子表中删除 delvalue ( p-value.hlink, x ); 冰恃酸室答溺砚先腻贺卜狗胆叛透恫久尾弹涪绿织琐过庆之奈鸽倘控董橡递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件 delvalue ( p, x ); /在后续链表中删除 GenList : GenList ( ) /析构函数 Remove ( first );void GenList : Remove ( GenListNode *ls ) /私有函数：释放以 ls
51、为表头指针的广义表 ls-value.ref - ; /引用计数减1肆课遮幻姆地花频言征弧属尔裸诬铱诗吕蔫秉内杉聚能野乌阁漆诵箭地求递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件 if ( ls-value.ref = 0 ) /如果减到0 GenListNode *p = ls, *q; /横扫表顶层 while ( p-tlink != NULL ) q = p-tlink; /到第一个结点 if ( q-utype = 3 ) /递归删除子表 Remove ( q-value.hlink ); p-link = q-link; delete q; 晶怔卤误划夹乾耸佐腿泼粥骤拔淌冕帝凸荒齐他堆爵电逼蛆铭摹春走痘否递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件
