数据结构栈

说明：严蔚敏的《数据结构》（C语言版）学习笔记，记录一下，以备后面查看。 如上图所示，刚开始base指针和tZ喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcNa41eu2vNa4z/LVu7XNo6y1sdG51bu1xMqxuvKjrHRvcNa41evP8snP0sa2r6Os1rG1

说明：严蔚敏的《数据结构》（C语言版）学习笔记，记录一下，以备后面查看。

如上图所示，刚开始base指针和tZ喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcNa41eu2vNa4z/LVu7XNo6y1sdG51bu1xMqxuvKjrHRvcNa41evP8snP0sa2r6Os1rG1vdW7wvq686Os1bu2pda41et0b3DWuM/y1bvN4rXY1rejrLTLyrHO0sPH0OjSqtTZt9bF5NDCv9W85KGjPC9wPjxwPjwvcD48cHJlIGNsYXNzPQ=="brush:sql;">#include #include #include #define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 const int OK = 1; //定义正确返回 const int ERROR = -1; //定义错误的返回 const int OVERFLOW = -2; //定义溢出 //定义元素类型 typedef int SElemType; //定义返回类型 typedef int Status; typedef struct{ SElemType *base; //栈底指针，在构造之前和销毁后base的值为NULL SElemType *top; //栈顶指针 int stacksize; //已分配的空间 }SqStack; //初始化栈 Status InitStack(SqStack &S){ S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } //获取栈顶元素 Status GetTop(SqStack S, SElemType &e){ if(S.top == S.base) return ERROR; e = *(S.top - 1); 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; S.top++; return OK; } //出栈 Status Pop(SqStack &S, SElemType &e){ if(S.top == S.base) return ERROR; e = *(--S.top); return OK; } //判断栈是否为空 bool StackEmpty(const SqStack &S){ if(S.top == S.base) return true; else return false; } //十进制数转8进制数 void conversion(SqStack &S){ InitStack(S); printf("请输入10进制数，返回一个8进制数：\n"); int n; scanf("%d", &n); while(n){ Push(S, n % 8); n = n / 8; } SElemType e; printf("8进制数是：0x"); while(!StackEmpty(S)){ Pop(S, e); printf("%d", e); } printf("\n"); } int main(){ SqStack sq; //InitStack(sq); //Push(sq, 1); //Push(sq, 2); //Push(sq, 3); //SElemType e3; //Pop(sq, e3); //GetTop(sq, e3); //printf("%d", e3); conversion(sq); scanf("%d"); return 0; }

上面的conversion函数是一个将10进制转换为8进制的例子，这个就是栈的一个应用，还有例如，括号匹配的验证、迷宫求解等。

例如Hanoi塔问题：

假设有3个分别为a,b,c的三个塔座，a上有直径从大到小的圆盘，可以借助b塔座将a上的圆盘移动到c上，移动过程中大小顺序不变。

void movePic(char a, int n, char b){
    printf("将编号为%d的圆盘从%c上移动到%c上\n", n , a, b);
}

void hanuota(int n, char x, char y, char z){
    if(n == 1){
        movePic(x, 1, z);  //将编号为1的圆盘从x移到z
    }else{
        hanuota(n - 1, x, z, y); //将x上编号为1到n-1的圆盘移到y,z作辅助塔
        movePic(x, n, z);  //将编号为n的圆盘从x移到z
        hanuota(n - 1, y, x, z); //将y上编号为1到n-1的圆盘移到z,x作辅助塔
    }
}

int main(){
    hanuota(3, 'a', 'b', 'c');
}

我们可以将问题简单抽象成递归。

1、要将n个圆盘移动到c，则需要先将n-1个圆盘移动到b

2、再将a上的最底下的圆盘移动到c

3、最后将b上面的n-1个圆盘移动到c

经过这三个步骤就可以完成移动，在这三个步骤中，步骤1，从a将n-1个圆盘移动到b和问题本身是同一个问题，步骤3将n-1个圆盘从b移动到c也和问题本身是同一个问题，所以这两处我们就可以迭代调用。