用非递归算法求二叉树叶子结点的c语言代码怎样写？
用非递归算法求二叉树叶子结点的c语言代码怎样写？
08-12-02 &
这个数据结构书上都有啊 。。。。 求节点个数？ preorder(bitree t) { initstack(s); p=t; n=0; while(p||!sempty(s)) { if(p) {visit(p);push(p);p=p-&} else {pop(&p);n++;p=p-&} } print(n); }
请登录后再发表评论!
　在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2个结点；深度为k的二叉树至多有2 - 1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。　　树和二叉树的2个主要差别：　　1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；　　2. 树的结点无左、右之分，而二叉树的结点有左、右之分。……　　树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。[编辑本段]一、树的概述　　树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。以下具体地给出树的定义及树的数据结构表示。　　（一）树的定义　　　　树是由一个或多个结点组成的有限集合，其中：　　⒈必有一个特定的称为根(ROOT)的结点；　　⒉剩下的结点被分成ｎ&=0个互不相交的集合T1、T2、......Tn，而且， 这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。　　树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树　　1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。　　2.树的深度——组成该树各结点的最大层次，如上图，其深度为4；　　3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；　　4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。　　5.树的表示　　树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：　　(A(B(E(K,L),F),C(G),D(H(M),I,J)))　　5. 2 二叉树　　　　1.二叉树的基本形态：　　二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：　　(1)空二叉树——(a)；　　(2)只有一个根结点的二叉树——(b)；　　(3)只有右子树——(c)；　　(4)只有左子树——(d)；　　(5)完全二叉树——(e)　　注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。　　2.两个重要的概念：　　(1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；　　(2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。　　3.二叉树的性质　　(1) 在二叉树中，第i层的结点总数不超过2^(i-1)；　　(2) 深度为h的二叉树最多有2^h-1个结点(h&=1)，最少有h个结点；　　(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，　　则N0=N2+1；　　(4) 具有n个结点的完全二叉树的深度为int（log2n）+1　　(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：　　若I为结点编号则 如果I&&1，则其父结点的编号为I/2；　　如果2*I&=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I&N，则无左儿子；　　如果2*I+1&=N，则其右儿子的结点编号为2*I+1；若2*I+1&N，则无右儿子。　　(6)给定N个节点，能构成h(N)种不同的二叉树。　　h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。　　4.二叉树的存储结构：　　(1）顺序存储方式　　type node=record　　data:datatype　　l,r:　　　　var tr:array[1..n]　　(2)链表存储方式，如：　　type btree=^node；　　node=record　　data:　　lchild,rchild:　　　　5.普通树转换成二叉树：凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线。　　二叉树很象一株倒悬着的树，从树根到大分枝、小分枝、直到叶子把数据联系起来，这种数据结构就叫做树结构，简称树。树中每个分叉点称为结点，起始结点称为树根，任意两个结点间的连接关系称为树枝，结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的&双亲&，结点的后趋结点称为该结点的&子女&或&孩子&，同一结点的&子女&之间互称&兄弟&。　　二叉树：二叉树是一种十分重要的树型结构。它的特点是，树中的每个结点最多只有两棵子树，即树中任何结点的度数不得大于２。二叉树的子树有左右之分，而且，子树的左右次序是重要的，即使在只有一棵子树的情况下，也应分清是左子树还是右子树。定义：二叉树是结点的有限集合，这个集合或是空的，或是由一个根结点和两棵互不相交的称之为左子树和右子树的二叉树组成。　　（三）完全二叉树　　对满二叉树，从第一层的结点(即根)开始，由下而上，由左及右，按顺序结点编号，便得到满二叉树的一个顺序表示。据此编号，完全二叉树定义如下：一棵具有ｎ个结点，深度为K的二叉树，当且仅当所有结点对应于深度为K的满二叉树中编号由１至ｎ的那些结点时，该二叉树便是完全二叉树。图4是一棵完全二叉树。[编辑本段]三、二叉树遍历　　遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。　　设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。　　(1)先序遍历　　访问根；按先序遍历左子树；按先序遍历右子树　　(2)中序遍历　　按中序遍历左子树；访问根；按中序遍历右子树　　(3)后序遍历　　按后序遍历左子树；按后序遍历右子树；访问根
请登录后再发表评论!
递归算法：是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。　　递归算法的特点　　递归过程一般通过函数或子过程来实现。　　递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。　　递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。　　递归算法解决问题的特点：　　(1) 递归就是在过程或函数里调用自身。　　(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。　　(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。　　(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。　　递归算法所体现的“重复”一般有三个要求：　　一是每次调用在规模上都有所缩小(通常是减半)；　　二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；　　三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。　　例子如下：　　描述：把一个整数按n(2&=n&=20)进制表示出来，并保存在给定字符串中。比如121用二进制表示得到结果为：“1111001”。　　参数说明：s: 保存转换后得到的结果。　　n: 待转换的整数。　　b: n进制（2&=n&=20）　　void　　numbconv(char *s, int n, int b)　　{　　　　if(n == 0) {　　strcpy(s, &&);　　　　}　　/* figure out first n-1 digits */　　numbconv(s, n/b, b);　　/* add last digit */　　len = strlen(s);　　s[len] = &ABCDEFGHIJKLMNOPQRSTUVWXYZ&[n%b];　　s[len+1] = '\0';　　}　　void　　main(void)　　{　　char s[20];　　int i,　　FILE *fin, *　　fin = fopen(&&, &r&);　　fout = fopen(&palsquare.out&, &w&);　　assert(fin != NULL && fout != NULL);　　fscanf(fin, &%d&, &base);　　/*PLS set START and END*/　　for(i=START; i &= END; i++) {　　numbconv(s, i*i, base);　　fprintf(fout, &%s\n&, s);　　}　　exit(0);　　}　　递归算法简析（PASCAL语言）　　递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写　　程序能是程序变得简洁和清晰.　　一 递归的概念　　1.概念　　一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).　　如:　　　　begin　　.　　.　　.　　a;　　.　　.　　.　　　　这种方式是直接调用.　　又如:　　　　begin begin　　. .　　. .　　. .　　c;　　. .　　. .　　. .　　　　这种方式是间接调用.　　例1计算n!可用递归公式如下:　　1 当 n=0 时　　fac(n)={n*fac(n-1) 当n&0时　　可编写程序如下:　　program fac2;　　var　　n:　　function fac(n:integer):　　begin　　if n=0 then fac:=1 else fac:=n*fac(n-1)　　　　begin　　write('n=');readln(n);　　writeln('fac(',n,')=',fac(n):6:0);　　end.　　例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.　　设n阶台阶的走法数为f(n)　　显然有　　1 n=1　　f(n)={　　f(n-1)+f(n-2) n&2　　可编程序如下：　　　　var n:　　function f(x:integer):　　begin　　if x=1 then f:=1 else　　if x=2 then f:=2 else f:=f(x-1)+f(x-2);　　　　begin　　write('n=');read(n);　　writeln('f(',n,')=',f(n))　　end.　　二，如何设计递归算法　　1.确定递归公式　　2.确定边界(终了)条件　　三，典型例题　　例3 梵塔问题　　如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子　　从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上　　不能出现大盘压小盘.找出移动次数最小的方案.　　程序如下:　　　　var　　n:　　procedure move(n,a,b,c:integer);　　begin　　if n=1 then writeln(a,'---&',c)　　else begin　　move(n-1,a,c,b);　　writeln(a,'---&',c);　　move(n-1,b,a,c);　　　　　　begin　　write('Enter n=');　　read(n);　　move(n,1,2,3);　　end.　　例4 快速排序　　快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.　　程序如下:　　　　const n=7;　　type　　arr=array[1..n]　　var　　a:　　i:　　procedure quicksort(var b: s,t:integer);　　var i,j,x,t1:　　begin　　i:=s;j:=t;x:=b;　　repeat　　while (b[j]&=x) and (j&i) do j:=j-1;　　if j&i then begin t1:=b; b:=b[j];b[j]:=t1;　　while (b&=x) and (i&j) do i:=i+1;　　if i&j then begin t1:=b[j];b[j]:=b;b:=t1; end　　until i=j;　　b:=x;　　i:=i+1;j:=j-1;　　if s&j then quicksort(b,s,j);　　if i&t then quicksort(b,i,t);　　　　begin　　write('input data:');　　for i:=1 to n do read(a);　　　　quicksort(a,1,n);　　write('output data:');　　for i:=1 to n do write(a:6);　　　　end.
请登录后再发表评论!
递归算法：是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。　　递归算法的特点　　递归过程一般通过函数或子过程来实现。　　递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。　　递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。　　递归算法解决问题的特点：　　(1) 递归就是在过程或函数里调用自身。　　(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。　　(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。　　(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。　　递归算法所体现的“重复”一般有三个要求：　　一是每次调用在规模上都有所缩小(通常是减半)；　　二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；　　三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。　　例子如下：　　描述：把一个整数按n(2&=n&=20)进制表示出来，并保存在给定字符串中。比如121用二进制表示得到结果为：“1111001”。　　参数说明：s: 保存转换后得到的结果。　　n: 待转换的整数。　　b: n进制（2&=n&=20）　　void　　numbconv(char *s, int n, int b)　　{　　　　if(n == 0) {　　strcpy(s, &&);　　　　}　　/* figure out first n-1 digits */　　numbconv(s, n/b, b);　　/* add last digit */　　len = strlen(s);　　s[len] = &ABCDEFGHIJKLMNOPQRSTUVWXYZ&[n%b];　　s[len+1] = '\0';　　}　　void　　main(void)　　{　　char s[20];　　int i,　　FILE *fin, *　　fin = fopen(&&, &r&);　　fout = fopen(&palsquare.out&, &w&);　　assert(fin != NULL && fout != NULL);　　fscanf(fin, &%d&, &base);　　/*PLS set START and END*/　　for(i=START; i &= END; i++) {　　numbconv(s, i*i, base);　　fprintf(fout, &%s\n&, s);　　}　　exit(0);　　}　　递归算法简析（PASCAL语言）　　递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写　　程序能是程序变得简洁和清晰.　　一 递归的概念　　1.概念　　一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).　　如:　　　　begin　　.　　.　　.　　a;　　.　　.　　.　　　　这种方式是直接调用.　　又如:　　　　begin begin　　. .　　. .　　. .　　c;　　. .　　. .　　. .　　　　这种方式是间接调用.　　例1计算n!可用递归公式如下:　　1 当 n=0 时　　fac(n)={n*fac(n-1) 当n&0时　　可编写程序如下:　　program fac2;　　var　　n:　　function fac(n:integer):　　begin　　if n=0 then fac:=1 else fac:=n*fac(n-1)　　　　begin　　write('n=');readln(n);　　writeln('fac(',n,')=',fac(n):6:0);　　end.　　例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.　　设n阶台阶的走法数为f(n)　　显然有　　1 n=1　　f(n)={　　f(n-1)+f(n-2) n&2　　可编程序如下：　　　　var n:　　function f(x:integer):　　begin　　if x=1 then f:=1 else　　if x=2 then f:=2 else f:=f(x-1)+f(x-2);　　　　begin　　write('n=');read(n);　　writeln('f(',n,')=',f(n))　　end.　　二，如何设计递归算法　　1.确定递归公式　　2.确定边界(终了)条件　　三，典型例题　　例3 梵塔问题　　如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子　　从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上　　不能出现大盘压小盘.找出移动次数最小的方案.　　程序如下:　　　　var　　n:　　procedure move(n,a,b,c:integer);　　begin　　if n=1 then writeln(a,'---&',c)　　else begin　　move(n-1,a,c,b);　　writeln(a,'---&',c);　　move(n-1,b,a,c);　　　　　　begin　　write('Enter n=');　　read(n);　　move(n,1,2,3);　　end.　　例4 快速排序　　快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.　　程序如下:　　　　const n=7;　　type　　arr=array[1..n]　　var　　a:　　i:　　procedure quicksort(var b: s,t:integer);　　var i,j,x,t1:　　begin　　i:=s;j:=t;x:=b;　　repeat　　while (b[j]&=x) and (j&i) do j:=j-1;　　if j&i then begin t1:=b; b:=b[j];b[j]:=t1;　　while (b&=x) and (i&j) do i:=i+1;　　if i&j then begin t1:=b[j];b[j]:=b;b:=t1; end　　until i=j;　　b:=x;　　i:=i+1;j:=j-1;　　if s&j then quicksort(b,s,j);　　if i&t then quicksort(b,i,t);　　　　begin　　write('input data:');　　for i:=1 to n do read(a);　　　　quicksort(a,1,n);　　write('output data:');　　for i:=1 to n do write(a:6);　　　　end.
请登录后再发表评论!本节主要说了递归的设计和算法实现，以及递归的基本例程斐波拉契数列、strlen的递归解法、汉诺塔和全排列递归算法。
一、递归的设计和实现
1.递归从实质上是一种数学的解决问题的思维，是一种分而治之的思想。
这个是常见的一种数学算法，其实它就是递归的本质。我们要求的是所有数的乘积，那么我们就先求出两个数的乘积，然后再根据这两个数的乘积去求第三个数的乘积，这样每一次我们实际上都是进行的两个数的相乘，也就是我们把一个很多个数的相乘转换为了两个数的相乘。
2.通过上面的例子可以发现，递归就是将大型复杂问题转化为与原问题相同，但是规模变小的问题进行处理。
4.同时我们可以发现a1 这个时候n==1，是一个特殊的条件。这就是递归的边界条件，最后的最后我们都会执行到递归的边界条件，然后再从边界条件返回。等到都返回结束后我们就真正实现了我们想要的结果。
5.如果递归没有边界条件，那么我们的递归将永远无法跳出，也就是这个问题递归是无法解决的。
6.在解决递归问题的时候首先要建立递归模型，这是解决递归类问题的第一步。但是说来容易，其实这是一个痛苦的过程，说白了，算法不是一般人能搞的。
二、斐波拉切数列的递归实现
1.斐波拉切数列实际上就是一个递归的典型表现，它的具体要求如下：
通过上图我们可以知道，斐波拉契数列的要求就是求相邻两个的数和然后赋给第三个数。这样我们可以先求前两个数的和，然后再求第二个与第三个数的和，一直求到最后，然后再返回。
2.假定我们要求的数列的元素个数为10
那么具体程序如下所示：
#include &stdio.h&
int fibonacci(int n)
if( n & 1 )
return fibonacci(n-1) + fibonacci(n-2);
else if( n == 1 )
else if( n == 0 )
int main()
int i = 0;
for(i=1; i&=10; i++)
printf("fibonacci(%d) = %d\n", i, fibonacci(i));
通过上面的程序可以看出：我们首先通过主函数调用fibonacci函数，然后通过for循环依次向里面传递值，第一次传递的值为1，返回的值为1，所以打印1.第二次传递的值为2，符合if(n&1)的条件，执行语句
fibonacci(n-1) + fibonacci(n-2);
这个时候产生第一轮递归，也就是先执行函数fibonacci(1)执行以后的返回结果是1，再执行fibonacci(0)，执行以后的返回结果是0，所以这一轮的返回结果是是1.
继续调用fibonacci函数,传递的参数是3，然后依次向后执行，每一次的递归深度都在加深。
三、strlen函数使用递归方式实现
1.我们都知道strlen函数的使用方法，它是通过传递进来的字符串来判断字符串的大小，但遇见"\0"的时候返回字符的个数，"\0"不包括在内。 2.假定我们要求一个"12345"的字符串的长度，具体例程如下：
#include &stdio.h&
int strlen(const char* s)
if( s == NULL )
return -1;
else if( *s == '\0' )
return strlen(s+1) + 1;
int main()
printf("strlen(\"12345\") = %d\n", strlen("12345"));
printf("strlen(NULL) = %d\n", strlen(NULL));
printf("strlen(\"\") = %d\n", strlen(""));
程序分析：我们在主函数中调用strlen函数，在我们第一次进入strlen函数的时候，程序执行判定，都不满足前两个判定，程序继续向下执行，再次调用strlen函数，然后再进行判定，仍然不满足判定条件，一直执行到s指针指向'\0'，这个时候各个调用函数开始返回，最外层的返回0，0+1，第二层返回1,1+1，第三层返回1,1+1 。直至所有函数全部返回。程序打印结果如下所示：
整个程序我们是把一个字符串的长度求解过程转变成了对每一个字符长度的求解，然后再进行相加，边界条件就是'\0'。
四、汉诺塔递归算法的实现
1.汉诺塔的要求我就不详细说了，汉诺塔的问题我想了足足一天，其实最后也是单步调试加上草稿纸才把它搞定，这里拿三个盘子作为分析。
2.汉诺塔的递归思想：第一，把a上的n-1个盘通过c移动到b。第二，把a上的最下面的盘移到c。第三，因为n-1个盘全在b上了，所以把b当做a重复以上步骤就好了。 &
&3.汉诺塔的具体代码实现：
#include &stdio.h&
void hanoi(int n, char a, char b, char c)
if( n & 0 )
if( n == 1 )
printf("%c -& %c\n", a, c);
hanoi(n-1, a, c, b);
printf("%c -& %c\n", a, c);
hanoi(n-1, b, a, c);
int main()
hanoi(3, 'a', 'b', 'c');
getchar();
程序打印结果如下：
五、汉诺塔递归调用分析
因为为了调试方便观看值，所以我把a,b,c字符重新定义成了整型变量，具体程序如下：
#include &stdio.h&
void hanoi(int n, int a, int b, int c)
if( n & 0 )
if( n == 1 )
printf("%d -& %d\n", a, c);
hanoi(n-1, a, c, b);
printf("%d -& %d\n", a, c);
hanoi(n-1, b, a, c);
int main()
hanoi(3, 5, 6, 7);
1.从主函数中调用hannoi函数，传递的参数是：n=3,a(1)=5,b(1)=6,c(1)=7 2.第1次进入hannoi函数，执行if(n==1)判定，不符合条件，调用hanoi(n-1,a,c,b)函数 3.向hannoi传递的参数是：n=2,a(2)=a(1),b(2)=c(1),c(2)=b(1) 4.第2次进入hannoi函数，执行if(n==1),不符合条件，调用hanoi(n-1,a,c,b)函数 5.向hannoi传递的参数：n=1,a(3)=a(2),b(3)=c(2),c(3)=b(2) 6.第3次进入hannoi函数，执行if(n==1)判定，符合条件，执行打印函数printf("%d-&%d\n",a,c)这个时候打印函数里面的a,c是第3次调用hannoi函数传递进来的参数，也就是a3),c(3),追到原始值也就是a(1),c(1)。打印结果是：5-&7 7.n=3的hannoi函数调用结束，子函数第1次执行结束。返回到n=2的hannoi函数调用位置，程序继续向下执行 8.调用打印函数：printf("%d-&%d\n",a,c)，这个时候打印函数的参数是n=2的时候hannoi函数的参数，也就是 a(2),c(2),追到原始值a(1),b(1)。打印结果是：5-&6 9.执行完打印函数以后程序继续向下执行，调用hanoi(n-1,b,a,c)函数 10.这次调用hanoi(n-1,b,a,c)是从n=2的hannoi函数开始的，所以向hannoi函数传递的参数是：n=1,a(4)=b(2),b(4)=a(2),c(4)=c(2) 11.第4次进入hannoi函数，指定if(n==1)判定，符合条件，执行打印函数printf("%d-&%d\n",a,c)这个时候打印函数里的a,c是a(4),c(4),追到原始值c(1),b(1)，打印结果是：7-&6. 12.调用hanoi(n-1,b,a,c)函数结束，程序返回到调用hanoi(n-1,b,a,c)函数的位置，接下来程序没有语句，子函数再次结束，程序返回到n=3调用hannoi函数的位置，执行印函printf("%d-&%d\n",a,c)，这个时候打印函数里的参数a,c是n=3的时候的参数，也就是a(1),c(1),追到原始值。打印结果是：5-&7。 13.程序继续向下执行，调用hanoi(n-1,b,a,c)函数 14.这个时候第一轮递归已经结束，向hannoi传递的参数是：n=2,a(5)=b(1),b(5)=a(1),c(5)=c(1) 15.第5次进入hannoi函数，执行if(n==1)判定，不符合条件，调用hannoi(n-1,a,c,b)函数 16.向hannoi传递的参数是：n=1,a(6)=a(5),b(6)=c(5),c(6)=b(5) 17.第6次进入hannoi函数，执行if(n==1)判定，符合条件，执行打印函数printf("%d-&%d\n",a,c)这个打印函数里面的参数a,c是第6次调用hannoi函数的参数，也就是a(6),c(6),即b(1),a(1),追到原始值为6,5，打印结果是6-&5 18.这个时候第6次进入hannoi函数执行完毕，程序返回到第六次调用hannoi函数的位置，继续向下执行。 19.调用打印函数printf("%d-&%d\n",a,c)，这个时候打印函数的参数a,c是n=2的时候第5次调用hannoi函数传递的参数，也就是a(5),c(5),追到原始值是b(1),c(1),即6,7.打印结果是6-&7 20.程序继续向下执行，调用hanoi(n-1,b,a,c)函数，这个时候程序是从n=2的hannoi函数位置继续向下执行的，参数是：n=1,a(7)=b(5),b(7)=a(5),c(7)=c(5) 21.第七次进入hannoi函数，进行if(n==1)判定，符合条件，执行打印函数printf("%d-&%d\n",a,c)，这个时候打印函数的参数是第七次调用hannoi函数的参数，也就是a(7),c(7)即b(5),c(5)，追到原始值5,7打印结果是：5-&7 22.程序最后再一次返回两次调用hanoi(n-1,b,a,c)函数的位置，但是每一次返回都没有其他动作，直至程序结束。
程序分析的结果十分复杂和繁琐，而且这仅仅是三层盘子。同时由于自己的画图水平不好，所以也没有画流程图，同时网上好多大牛说是可以用树的想法去想汉诺塔问题，但是我没学习到树，所以只能用上面那种最笨额方法了。
六、全排列的递归调用
1.问题的提出：假定有三个元素a,b,c，那么这三个元素的全排列有六种方式：abc,acb,bac,bca,cba,cab。那么两个元素的全排列的是ab,ba，一个元素的全排列就是元素本身，所以一个元素的全排列就是递归的边界条件。
2.我们这里以三个元素的全排列，程序例程如下：
#include &stdio.h&
void permutation(char s[], int b, int e)
if( (0 &= b) && (b &= e) )
if( b == e )
printf("%s\n", s);
int i = 0;
for(i=b; i&=e; i++)
char c = s[b];
s[b] = s[i];
permutation(s, b+1, e);
s[b] = s[i];
int main()
char s[] = "abcd";
permutation(s, 0, 3);
&程序的递归算法框图如下所示：
&由于我们传进子函数的四个字符的字符数组，所以这里我们直接执行else部分的函数，首先执行for循环，for循环从i=b开始，这样我们第一轮for循环先做的交换代码如下：
char c = s[b];
s[b] = s[i];
其实这个时候我们没有完成任何交换，然后继续调用permutation(s, b+1, e)函数，再次进入for循环，这个时候for循环是从i=b+1开始的，这个时候执行交换部分的代码还会完成另一个元素的交换。实质上这个交换部分的代码完成的就是将每一个元素作为第一个位置的作用，然后再进行其他操作。 for循环里的第二部分主要代码如下：
s[b] = s[i];
这一部分代码的主要作用是在每一个permutation(s, b+1, e)进行弹出操作的时候开始执行，这样我们就可以对后面的数进行全排列了。我们也就完成图示的全排列操作。具体的递归过程可以例程单步调试来进行理解。
阅读(...) 评论()