汉若塔by栈和递归

栈是只准在一端进行插入和删除操作的线性表，其主要特性是先入后出，对于后进的元素优先进行操作。这一特性可以有效的模仿汉若塔问题中大盘子不能叠在小盘子上的规则。
可以利用栈的思想，通过递归解决汉若塔问题。

#include <stdio.h>
#include <stdlib.h>

#define INIT_SIZE 100
#define INCREMENT 10


typedef  int ElemType;

typedef struct{
  ElemType *base;
  ElemType *top;
  int stacksize;
  char name;
}Sqstack;


Sqstack Init_stack(char c)//初始化
{
    Sqstack s;
    s.name=c;
    s.base = (ElemType *)malloc(INIT_SIZE* sizeof(ElemType));
    if(!s.base)
    {
        printf("栈申请内存失败!\n");
        exit(0);
    }
    else
    {
        s.top=s.base;
        s.stacksize=INIT_SIZE;

        return s;
    }
}

void push(Sqstack *s,ElemType e)//压栈
{
    ElemType *p;
    if(s->top-s->base >= INIT_SIZE)
    {
        p=(ElemType*)realloc(s->base,(s->stacksize+INCREMENT)*sizeof(ElemType));
        if(!p)
        {
            printf("追加申请内存失败!\n");
            exit(0);
        }
        else
            s->base=p;
        s->top=s->base+s->stacksize;
        s->stacksize+=INCREMENT;
    }
    *s->top=e;
    s->top++;
}

void pop(Sqstack *s,ElemType *e)//弹栈
{
    if(s->top==s->base)
    {
        printf("栈为空!\n");
    }
    else
    {
        s->top--;
        *e=*s->top;
    }
}

int isempty(Sqstack s)//判断栈是否为空
{
    if(s.top==s.base)
        return 1;
    else
        return 0;
}

void move(Sqstack *a, Sqstack *c)//移动函数：将元素从a弹出，压入c
{
    int n;
    pop(a,&n);
    push(c,n);
}

void Hanoi(Sqstack *a, int n, Sqstack *b, Sqstack *c)//汉若塔递归
{
    if(n==1)//1个直接移动到c
    {
        move(a, c);
        printf("将 %d 从 %c 移动到 %c\n",n, a->name, c->name);
    }
    else
    {
        Hanoi(a, n-1, c, b);//为了将n从a移动到c，先将n-1移动到b
        move(a, c);//将n移动到c
        printf("将 %d 从 %c 移动到 %c\n",n, a->name, c->name);
        Hanoi(b, n-1, a, c);//再将n-1移动到c
    }
}


int main()
{
    int n;
    int i=1;
    Sqstack a, b, c;
    a=Init_stack('A');//初始化三个栈A，B，C
    b=Init_stack('B');
    c=Init_stack('C');
    printf("输入层数n： ");
    scanf("%d", &n);
    for(i=n;i>=1;i--)//假设希望将A中的n个盘移动到C，先将n个盘存入栈A中
    {
        push(&a, i);
    }
    Hanoi(&a, n, &b, &c);//递归
    printf("C:\n");//输出C中元素，查看结果
    while(!isempty(c))
    {
        pop(&c,&n);
        printf("%d\n", n);
    }
    return 0;
}