HANOI塔問題的非遞歸解 
 
  解決HANOI塔問題的首選方法是遞歸函數算法。 遞歸函數的實質是函數調用自身，
并且調用一次就對參數進行降階或對問題進行簡化。具體可參見作者的《HANOI塔問題的
遞歸算法解 》一文。
    在遞歸函數算法中，隱含著復雜的函數嵌套調用關系，涉及到利用堆棧進行參數的
保存、調用。以上這些對于作者是無需考慮的，所以十分方便。
    但是，如果由作者自己來實現堆棧進行參數的保存、調用，以及利用函數的循環
調用，同樣可以實現遞歸函數算法的功能。
    簡單的說：函數的循環調用 + 堆棧 = 遞歸函數。
    以下是程序的簡要說明：

      1' 創建鏈表結構numnode作為堆棧,保存每次迭代的盤子數量；             
      2' 創建鏈表結構ptnode作為堆棧,保存每次迭代的原柱，中間柱，          
           目標柱的指針,由三個指針s1,s2,s3分別指向保存原柱，                         
           中間柱,目標柱的指針的堆棧;                                                     
      3' 將迭代操作區分為正向迭代和反向回溯，用變量direc標示；            
      4' 在迭代至只有一個盤子或回溯時，進行移位操作。在函數                
           digui(int ,char *,char *,char *) 中實現。
           
/*
  Name:     hanoinorecursive.c      
  Author:       zhuqing
  Description:      HANOI塔問題的非遞歸解   
  Date: 06-08-03 13:30
  Copyright: 
*/
#include <stdio.h>
#include <alloc.h>
 
#define N 5
int direc;
int tmp;
/* 保存每次迭代的盤子數量 */
struct numnode{
 int num;
 struct numnode *next; 
};

struct numnode *nn;
/* 分別保存每次迭代的原柱，中間柱，目標柱的3個指針 */
struct ptnode{
 char *ch;
 struct ptnode *next;
} *s1,*s2,*s3;
/* 原柱指針堆棧的push函數 */ 
void push1(char* a){
 struct ptnode *tmp;
 tmp=(struct ptnode *)malloc((int)sizeof(struct ptnode));
 tmp->ch=a;
 tmp->next=s1;
 s1=tmp; 
}
/* 中間柱指針堆棧的push函數 */ 
void push2(char* a){
 struct ptnode *tmp;
 tmp=(struct ptnode *)malloc((int)sizeof(struct ptnode));
 tmp->ch=a;
 tmp->next=s2;
 s2=tmp; 
}
/* 目標柱指針堆棧的push函數 */ 
void push3(char* a){
 struct ptnode *tmp;
 tmp=(struct ptnode *)malloc((int)sizeof(struct ptnode));
 tmp->ch=a;
 tmp->next=s3;
 s3=tmp; 
}
/* 原柱指針堆棧的pop函數 */ 
char* pop1(){
 struct ptnode *tmp;
 char* ch;
 ch=s1->ch; 
 tmp=s1;
 s1=s1->next;
 free(tmp);
 return ch;
}
/* 中間柱指針堆棧的pop函數 */ 
char* pop2(){
 struct ptnode *tmp;
 char* ch;
 ch=s2->ch; 
 tmp= s2;
 s2=s2->next;
 free(tmp);
 return ch;
}
/* 目標柱指針堆棧的pop函數 */ 
char* pop3(){
 struct ptnode *tmp;
 char* ch;
 ch=s3->ch; 
 tmp= s3;
 s3=s3->next;
 free(tmp);
 return ch;
} 
/* 保存盤子個數堆棧的push函數 */ 
void pushn(int a){
 struct numnode *tmp;
 tmp=(struct numnode *)malloc((int)sizeof(struct numnode));
 tmp->num=a;
 tmp->next=nn;
 nn=tmp; 
}
/* 保存盤子個數堆棧的pop函數 */
int popn(){
 struct numnode *tmp;
 int a;
 a=nn->num; 
 tmp= nn;
 nn=nn->next;
 /* free(tmp); */
 return a;
} 
/* 原柱，中間柱，目標柱初值數組 */ 
char a[9]={'1','2','3','4','5','6','7','8','9'};

char b[9]={'0','0','0','0','0','0','0','0','0'};

char c[9]={'0','0','0','0','0','0','0','0','0'};

int num=N;
char *x1=a;
char *x2=b;
char *x3=c;
int step=0; 
void prnt();

/*   核心函數，功能：進行迭代、回溯、移位操作    */
/*   參數說明：n:盤子個數；                      */
/*             t1,t2,t3：3指針                   */
/*               分別指向原柱、中間柱、          */
/*               目標柱數組；                    */  
void digui(int n,char *t1,char *t2,char *t3){
    if(n<=0)return;
 if(direc>0){
  if(n>1){
    pushn(n);
    push1(t2);
    push2(t1);
    push3(t3);
    x1=t1;
    x2=t3;
    x3=t2;
    num--;
    return;
        }        
        t3[0]=t1[0];
        t1[0]='0';
        prnt();
        direc=-1;
        num=popn();
        x1=pop1();
        x2=pop2();
        x3=pop3();    
        return;
 }
 else{
        if(n>2){    
            *(t3+n-1)=*(t2+n-1);
            *(t2+n-1)='0';
            prnt();
            direc=1;   
      num--;                                           
            return;                
        }
        *(t3+1)=*(t2+1);
        *(t2+1)='0';
        prnt();         
        t3[0]=t1[0];        
        t1[0]='0';
        prnt();
        direc=-1;
        num=popn();                
        x1=pop1();
        x2=pop2();
        x3=pop3();  
        return;
 } 
}
/*  主函數，功能：輔初值，循環調用digui()函數，調用prnt()函數  */ 
main(){
    int i;
    int j=0;
    printf("/*        HANOI塔問題的非遞歸解         */\n");
    printf("/* hanoinorecursive.c                   */\n\n");
    prnt();
    s1=s2=s3=(struct ptnode *)malloc((int)sizeof(struct ptnode));
    s1->ch=s2->ch=s3->ch=NULL;
    s1->next=s2->next=s3->next=NULL;
    nn=(struct numnode *)malloc((int)sizeof(struct numnode));
    nn->next=NULL; 
    direc=1;
    while(1){
        digui(num,x1,x2,x3);
        j++;
        /*if(s1->next==NULL&&direc>0)break;*/
        i=0;
        while(i<N&&c[i]!='0')i++;
        if(i==N)break;   
    } 
    /*printf("%3d",j);*/
    printf("\n");    
    getchar(); 
}
/* 屏幕打印函數 */
void prnt(){
   int i;
   printf("\n");
   printf("STEP%3d\n",step++);
   printf("a:");
   for(i=0;i<N;i++)
        printf("%3c",a[i]);
    printf("\n");
   printf("b:");        
    for(i=0;i<N;i++)
        printf("%3c",b[i]);
    printf("\n");
    printf("c:");                                        
    for(i=0;i<N;i++)
        printf("%3c",c[i]);
    printf("\n\n");        
}