HANOI塔问题的非递归解

文章类别：C语言程序设计 | 发表日期:2008-9-24 14:45:35

    解决HANOI塔问题的首选方法是递归函数算法。 递归函数的实质是函数调用自身，
并且调用一次就对参数进行降阶或对问题进行简化。具体可参见作者的《HANOI塔问题的
递归算法解 》一文。
    在递归函数算法中，隐含着复杂的函数嵌套调用关系，涉及到利用堆栈进行参数的
保存、调用。以上这些对于作者是无需考虑的，所以十分方便。
    但是，假如由作者自己来实现堆栈进行参数的保存、调用，以及利用函数的循环
调用，同样可以实现递归函数算法的功能。
    简单的说：函数的循环调用 + 堆栈 = 递归函数。
    以下是程序的简要说明：

      1' 创建链表结构numnode作为堆栈,保存每次迭代的盘子数量；             
      2' 创建链表结构ptnode作为堆栈,保存每次迭代的原柱，中间柱，         
           目标柱的指针,由三个指针s1,s2,s3分别指向保存原柱，                        
           中间柱,目标柱的指针的堆栈;                                                    
      3' 将迭代操作区分为正向迭代和反向回溯，用变量direc标示；           
      4' 在迭代至只有一个盘子或回溯时，进行移位操作。在函数               
           digui(int ,char *,char *,char *) 中实现。
          
/*
  Name:     hanoinorecursive.c     
  Author:       zhuqing
  Des cription:      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");       
}          

上一篇：{应用}HANOI塔问题的递归解 人气:4798
下一篇：{应用}HANOI塔问题的动画演示 人气:5507

C语言程序设计视频教程