...
说明：严蔚敏的《数据结构》（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也和问题本身是同一个问题，所以这两处我们就可以迭代调用。