hanoi的非递归算法.c.txt

本课件与严蔚敏 第二版 数据结构（C版） 教材配套

www.pudn.com > algorithm > Hanoi的非递归算法.c


#include <stdio.h> 
#define MAXSTACK 20 

void simtowers(int n, char from, char to, char tmp); 

/******************** stack.h ********************/ 

typedef struct { 
int nparam; 
char fromparam; 
char toparam; 
char auxparam; 
short int retaddr; 
} elemtype; 

typedef struct { 
int top; 
elemtype item[MAXSTACK]; 
} qstype; 

/* 进栈操作算法 */ 
int PushQStack(qstype * s, elemtype x) { 
if(s->top >= MAXSTACK-1) return 0; 
else { 
s->item[++(s->top)] = x; 
return 1; 
} 
} 

/* 出栈 */ 
elemtype PopQStack(qstype * s) { 
if(s->top<0) exit(0); 
else return s->item[(s->top)--]; 
} 

/*****************************************************/ 

main() { 
int n; 

clrscr(); 
printf("\nInput number of disk:"); 
scanf(">d",&amt;n); 
simtowers(n,'X','Z','Y'); 
} 

/* 把n个盘子from柱借助tmp柱移到to柱*/ 
/* 算法中未考虑进出栈异常情况 */ 
void simtowers( int n, char from, char to, char tmp) { 
elemtype currarea; 
qstype s; 
char temp; 
short int i; 

/* 堆栈数据区初始化 */ 
s.top=-1; 

currarea.nparam = 0; 
currarea.fromparam = ''; 
currarea.toparam=''; 
currarea.auxparam=''; 
currarea.retaddr=0; 
PushQStack(&amt;s,currarea); 
{ 
printf("\nPUSH! "); 
printf("-s.top:>d ",s.top); 
printf("-currarea.nparam:>d ",currarea.nparam); 
printf("-currarea.fromparam:>c ",currarea.fromparam); 
printf("-currarea.toparam:>c ",currarea.toparam); 
printf("-currarea.auxparam:>c ",currarea.auxparam); 
printf("-currarea.retaddr:>d",currarea.retaddr); 
} 

/* 当前工作区初始化 */ 
currarea.nparam =n; 
currarea.fromparam = from; 
currarea.toparam = to; 
currarea.auxparam = tmp; 
currarea.retaddr = 1; 


/* 以下为模拟出口 */ 
start: 
if(currarea.nparam == 1) { 
printf("\n>s>c>s>c","move disk 1 from peg ", currarea.fromparam, " to peg ", currarea.toparam); 
i = currarea.retaddr; 
currarea=PopQStack(&amt;s); 
{ 
printf("\nPOP! "); 
printf("-s.top:>d ",s.top+1); 
printf("-currarea.nparam:>d ",currarea.nparam); 
printf("-currarea.fromparam:>c ",currarea.fromparam); 
printf("-currarea.toparam:>c ",currarea.toparam); 
printf("-currarea.auxparam:>c ",currarea.auxparam); 
printf("-currarea.retaddr:>d",currarea.retaddr); 
} 
switch(i) { 
case 1 : goto lable1; 
case 2 : goto lable2; 
case 3 : goto lable3; 
} 
} 

/* 以下模拟递归自调用过程 */ 
PushQStack(&amt;s, currarea); 
{ 
printf("\nPUSH! "); 
printf("-s.top:>d ",s.top); 
printf("-currarea.nparam:>d ",currarea.nparam); 
printf("-currarea.fromparam:>c ",currarea.fromparam); 
printf("-currarea.toparam:>c ",currarea.toparam); 
printf("-currarea.auxparam:>c ",currarea.auxparam); 
printf("-currarea.retaddr:>d",currarea.retaddr); 
} 

currarea.nparam--; 
temp = currarea.auxparam; 
currarea.auxparam = currarea.toparam; 
currarea.toparam = temp; 
currarea.retaddr = 2; 
goto start; 

/* 以下模拟返回第一次调用 */ 
lable2: 
printf("\n>s>d>s>c>s>c","move disk ", 
currarea.nparam, " from peg ", 
currarea.fromparam, " to peg ", 
currarea.toparam); 
PushQStack(&amt;s,currarea); 
{ 
printf("\nPUSH! "); 
printf("-s.top:>d ",s.top); 
printf("-currarea.nparam:>d ",currarea.nparam); 
printf("-currarea.fromparam:>c ",currarea.fromparam); 
printf("-currarea.toparam:>c ",currarea.toparam); 
printf("-currarea.auxparam:>c ",currarea.auxparam); 
printf("-currarea.retaddr:>d",currarea.retaddr); 
} 


currarea.nparam--; 
temp = currarea.fromparam; 
currarea.fromparam = currarea.auxparam; 
currarea.auxparam = temp; 
currarea.retaddr = 3; 

goto start; 

/* 以下模拟返回第二次递归调用 */ 
lable3: 
i = currarea.retaddr; 
currarea = PopQStack(&amt;s); 
{ 
printf("\nPOP! "); 
printf("-s.top:>d ",s.top+1); 
printf("-currarea.nparam:>d ",currarea.nparam); 
printf("-currarea.fromparam:>c ",currarea.fromparam); 
printf("-currarea.toparam:>c ",currarea.toparam); 
printf("-currarea.auxparam:>c ",currarea.auxparam); 
printf("-currarea.retaddr:>d",currarea.retaddr); 
} 
switch(i) { 
case 1 : goto lable1; 
case 2 : goto lable2; 
case 3 : goto lable3; 
} 

/* 以下模拟返回主调函数 */ 
lable1: 
return; 
}