hanoi的非递归算法.c

几个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",&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(&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(&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(&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(&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(&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;
}