第三章：3.栈和队列 -- 栈与递归的实现

前言：

　　栈还有一个总要应用是在程序设计语言中实现递归。一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。

　　1、栈

　　2、栈的应用举例

　　3、栈与递归的实现

　　4、队列

　　5、离散事件模型

正文：

　　3、栈与递归的实现

　　　　递归程序设计是一个强有力的工具。

　　　　1）很多数学函数是递归调用的

　　　　　　阶乘： Fact（n）=n * (n-1) * (n-2) * ...... * 2 * 1

　　　　　　斐波那契数列、阿克曼函数等

　　　　2）有的数据结构，如二叉树、广义表等，由于数据结构本身固有的递归特性，则他们的操作可递归的描述。

　　　　3）还有一类，虽然本身没有明显的递归结构，但用递归求解会更加简单，以 hanoi 汉诺塔为例。

　　代码实现:

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

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
//Status是函数的类型，其值是函数结果状态码
typedef int Status;
typedef int SElemType;
//typedef char SElemType;

typedef struct {
    SElemType * base;
    SElemType * top;
    int stacksize;
}SqStack;

//构造空栈
Status InitStack(SqStack &S){
    S.base=(SElemType *)malloc(sizeof(SElemType)*STACK_INIT_SIZE);
    if(!S.base) exit(OVERFLOW);
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
    return OK;
}

//插入元素 （入栈）
Status Push(SqStack &S,SElemType e){
    if((S.top-S.base)==S.stacksize){                                        //空间不够，继续分配空间
        S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
        if(!S.base) exit(OVERFLOW);
        S.top=S.base+S.stacksize;
        S.stacksize+=STACKINCREMENT;
    }
    *S.top++=e;
    return OK;
}

//删除元素（出栈）
Status Pop(SqStack &S,SElemType &e){
    if(S.top!=S.base){
        e=*(--S.top);
    }else{
        return ERROR;
    }
    return OK;
}



void printAllValues(SqStack &S){
    SElemType * q=S.top;
    printf("top：%p
",q);
    while(q!=S.base){
        printf("地址：%p，",q-1);
        printf("值：%d
",*(q-1));
        //printf("值：%c
",*(q-1));
        q--;
    }
    printf("base：%p
",S.base);
}

//gettop获取栈顶元素
SElemType GetTop(SqStack &S){
    if(S.base==S.top){
        return 0;
    }
    return *(S.top-1);
}



//初始化 汉诺塔 X
void HanoiInit(int n,SqStack &X){
    for(int i=1;i<=n;n--)
        Push(X,n);
}

//将元素 e 从栈 A 删除 ，插入到栈 B 上。
void move(SqStack &A,int e,SqStack &B){
    if(GetTop(A)==e){
        SElemType c;
        Pop(A,c);
        Push(B,e);            
    }        
}

int MoveNum=0;

//将汉诺塔 X 上的 N 个元素 按照同样的顺序 放到 塔 Z上。
void Hanoi(int n,SqStack &X,SqStack &Y,SqStack &Z){    
    if(n==1){
        move(X,n,Z);                    //从X 柱 往 Y 柱 移动元素 n ，
        MoveNum++;
    }else{
        Hanoi(n-1,X,Z,Y);
        move(X,n,Z);
        MoveNum++;
        Hanoi(n-1,Y,X,Z);
    }
    
}


void main(){
    SqStack X;
    InitStack(X);

    SqStack Y;
    InitStack(Y);

    SqStack Z;
    InitStack(Z);

    int n=5;
    HanoiInit(n,X);
    printf("%s
","X柱：");
    printAllValues(X);

    printf("%s
","Y柱：");
    printAllValues(Y);

    printf("%s
","Z柱：");
    printAllValues(Z);
    
    printf("
%s

","调用Hanoi 函数之后:");

    Hanoi(5,X,Y,Z);

    printf("%s
","X柱：");
    printAllValues(X);

    printf("%s
","Y柱：");
    printAllValues(Y);

    printf("%s
","Z柱：");
    printAllValues(Z);

    printf("汉诺塔上的元素共移动：%d次
",MoveNum);

}

运行结果：