C语言汉诺塔问题非递归解法代码求大神讲解

int game2()要改为int main()后才可编译运行：

#include

#include 

#define CSZL 10 

#define FPZL 10 

typedef struct hanoi 

{ 

int n; 

char x,y,z; 

}hanoi;

typedef struct Stack //定义栈结点 

{ 

hanoi *base,*top; 

int stacksize; 

}Stack;

int InitStack(Stack *S) 

{ 

S->base=(hanoi *)malloc(CSZL*sizeof(hanoi)); //申请栈空间 

if(!S->base) //若申请不成功返回失败信息 

return 0; 

S->top=S->base; //置为空栈 

S->stacksize=CSZL; //栈结点数 

return 1; 

} 

int PushStack(Stack *S,int n,char x,char y,char z) //入栈 

{ 

if(S->top-S->base==S->stacksize) //若栈已满 

{ 

S->base=(hanoi *)realloc(S->base,(S->stacksize+FPZL)*sizeof(hanoi)); //补充申请，扩充栈空间 

if(!S->base)   //若申请不成功返回失败信息 

return 0; 

S->top=S->base+S->stacksize; //重置栈顶指针 

S->stacksize+=FPZL; //重置栈空间尺寸 

} 

S->top->n=n; //新结点信息存入栈顶结点 

S->top->x=x; 

S->top->y=y; 

S->top->z=z; 

S->top++; //栈中元素加1 

return 1; 

} 

int PopStack(Stack *S,int *n,char *x,char *y,char *z) //出栈 

{ 

if(S->top==S->base) //若栈已空 

return 0; //返回出错信息 

else 

{ 

S->top--; //栈顶指针减1 

*n=S->top->n; //返回出栈元素信息 

*x=S->top->x; 

*y=S->top->y; 

*z=S->top->z; 

return 1; 

} 

} 

int EmptyStack(Stack *S) //判定是否空栈 

{ 

if(S->base==S->top) 

return 1;

else 

return 0;

} 

int i=1; 

void Move(char x,char z) //打印移动盘子的信息 

{ 

printf("\n\t\t第%d步，%c-->%c",i++,x,z); 

} 

int main() /* 非递归法 */

{ 

int n; 

char x,y,z; 

Stack *S; 

system("cls"); /*清屏指令*/

S=(Stack *)malloc(sizeof(Stack)); //申请栈空间 

if(!S) 

return 0; 

if(!InitStack(S)) //初始化栈 

return 0; 

printf("请输入汉诺塔的初始盘子数量以及轴的名称："); 

scanf("%d\t%c%c%c",&n,&x,&y,&z); 

if(!PushStack(S,n,x,y,z)) //要移动的盘子数及各轴名称入栈 

return 0; 

while(!EmptyStack(S)) //当栈非空时循环 

{ 

if(!PopStack(S,&n,&x,&y,&z)) //若空栈则退出循环，否则出栈一个任务 

break; 

if(n==1) //若只有一个盘子，直接移动 

{ 

Move(x,z); 

} 

else //有1个以上的盘子时入栈（注意栈的工作特点，是后进先出，所以最先做的事要最后入栈） 

{ 

if(!PushStack(S,n-1,y,x,z)) //将上层的n-1个盘子从y移向z

break; 

if(!PushStack(S,1,x,y,z)) //将底层的盘子从x移向z 

break; 

if(!PushStack(S,n-1,x,z,y)) //将上层的n-1个盘子从x移向y

break; 

} 

} 

free(S->base); 

S->base=NULL; 

S->top=NULL; 

S->stacksize=0; 

return 0; 

}