巧用C语言“栈”实现Hanoi塔的动态显示

黑龙江 马友华
1994-10-28

        Hanoi塔的三根针中金片的移动可求精为对三个栈(0、1、2号)的操作，其栈底指针分别为bos[0]、bos[1]、bos[2]，0号栈中压入反映金片大小的数据，1、2号栈栈顶针与其对应的栈底指针相同。三根针的动态塔高可用栈顶减栈底得出，第n号针动态塔高为tos-bos(入栈)或tos-bos+1(出栈)，n号针上顶层金片的大小可用*tos表示，例如从1号针取一金片放入2号针，可求精为从1号栈取出数据*tos压入2号栈中。由此，可利用Turbo_C中的图形函数实现金片的动态直观显示。
        程序清单：
        #include <graphics.h>
        #include <stdlib.h>
        void init_h(void);
        void pop_push();
        void push_h();
        int pop_h();
        int *block;
        int H,i,n,ErrorCode;
        int *bos,*tos;
        /*金片移动的递归调用函数*/
        movetower(h,f,t,u)
        int h,f,t,u;
        {
        if (h==1) {
        i++;
        pop_push(f,t);
        getch();
        }
        else {
        movetower(h-1,f,u,t);
        i++;
        pop_push(f,t);
        getch();
        movetower(h-1,u,t,f);
        }
        }
        /*金片移动函数*/
        void pop_push(a,b)
        int a,b;
        {
        int k;
        k=pop_h(a);
        push_h(b,k);
        }
        /*金片弹出显示函数*/
        pop_h(a)
        int a;
        {
        int r,hh;
        tos--;
        r=*tos;
        hh=tos-bos+1;
        putimage(a*100,300-hh*10,block,XOR_PUT);
        return(r);
        }
        /*金片压入显示函数*/
        void push_h(b,k)
        int b,k;
        {
        int r,hh;
        *tos=k;
        tos++;
        hh=tos-bos;
        putimage(b*100,300-hh*10,block,XOR_PUT);
        }
        /*图形及栈初始化函数*/
        void init_h(vlid)
        {
        int gd=DETECT,gm=0,size,i,x1,x2,y1,y1,hh;
        initgraph(&gd,&gm,"");
        size=imagesize(0,0,100,10);
        for (i=1;i<=h;i++)
        block=malloc(size);
        ErrorCode=graphresult();
        if (grOK!=ErrorCode) {
        printf("graphics System Error:%s\n",grapherrormsg(ErrorCode));
        exit(1);
        }
        cleardevice();
        setcolor(15);
        line(0,301,100,301);
        line(50,301,50,150);
        for (i=H;i>0;i--) {
        x1=50-i*10/2;
        y1=310-(H+1-i)*10;
        x2=50+i*10/2;
        y2=302-(h+1-i)*10;
        setfillstyle(1,(H+1-i));
        bar(x1,y1,x2,y2);
        getimage(0,y1,99,y2,block);
        }
        cleardevice();
        line(0,301,300,301);
        line(50,301,50,150);
        line(150,301,150,150);
        line(250,301,250,150);
        for (i=0;i<3;i++) {
        bos=(int *)malloc(H*sizeof(int));
        tos=bos;
        }
        for (i=H;i>0;i--) {
        *tos=i;
        hh=tos-bos;
        putimage(0,290-hh*10,block,XOR_PUT);
        tos++;
        }
        getch();
        }
        main()
        {
        int a=0,b=1,c=2;
        i=0;
        printf("intput n(n<=8):");
        scanf("%d",&n);
        H=n;
        init_h();
        movetower(n,a,b,c);
        printf("\t The End !\n\n");
        closegraph();
        }
        (黑龙江 马友华)
 
 