汉诺塔非递归算法C语言实现.doc

《汉诺塔非递归算法C语言实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、汉诺塔非递归算法C语言实现#include#include#defineCSZL10#defineFPZL10typedefstructhanoi{intn;charx,y,z;}hanoi;typedefstructStack{hanoi*base,*top;intstacksize;}Stack;intInitStack(Stack*S){S->base=(hanoi*)malloc(CSZL*sizeof(hanoi));if(!S->base)return0;S->top=S->base;S-

2、>stacksize=CSZL;return1;}intPushStack(Stack*S,intn,charx,chary,charz){if(S->top-S->base==S->stacksize){S->base=(hanoi*)realloc(S->base,(S->stacksize+FPZL)*sizeof(hanoi));if(!S->base)return0;S->top=S->base+S->stacksize;S->stacksize+=FPZL;}S->top->n=n;S->top->x=x;S->top->y=

3、y;S->top->z=z;S->top++;return1;}intPopStack(Stack*S,int*n,char*x,char*y,char*z){if(S->top==S->base)return0;else{S->top--;*n=S->top->n;*x=S->top->x;*y=S->top->y;*z=S->top->z;return1;}}intEmptyStack(Stack*S){if(S->base==S->top)return1;elsereturn0;}inti=1;voidMove(charx,char

4、z){printf("tt第%d部，从%c移到%c。",i++,x,z);}intmain(){intn;charx,y,z;Stack*S;S=(Stack*)malloc(sizeof(Stack));if(!S)return0;if(!InitStack(S))return0;printf("tt请输入汉诺塔的初始盘子数量以及轴的名称：");scanf("%d%c%c%c",&n,&x,&y,&z);if(!PushStack(S,n,x,y,z))return0;while(!EmptyStack(S)){

5、if(!PopStack(S,&n,&x,&y,&z))break;if(n==1){Move(x,z);}else{if(!PushStack(S,n-1,y,x,z))break;if(!PushStack(S,1,x,y,z))break;if(!PushStack(S,n-1,x,z,y))break;}}free(S->base);S->base=NULL;S->top=NULL;S->stacksize=0;return0;}