就是栈,这是我根据严蔚敏的数据结构上改编的
程序代码:
/**************顺序栈的实现,参考了严蔚敏《数据结构》*******************/
#include <stdio.h>
#include <malloc.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define Status int
#define ERROR 0
#define OK 1
typedef struct {
int *base;
int *top;
int stackSize;
}SqStack; //->用于指针情况下,如 SqStack * PP; PP->就可以用
/************ 初始化一个栈,初始化后栈为空*************/
Status initStack(SqStack &S){ //建立一个空的栈
S.base = (int*) malloc( sizeof(int) * STACK_INIT_SIZE );
if(!S.base)
return ERROR;
S.top = S.base;
S.stackSize = STACK_INIT_SIZE;
return OK;
}
/**************判断栈是否为空*********************/
Status stackEmpty(SqStack S){
if(S.base == S.top)
return OK;
return ERROR;
}
/**************将栈清空*****************/
Status clearStack(SqStack S){
S.top = S.base;
return OK;
}
/**********销毁一个栈**********/
Status destroyStack(SqStack &S){
free(&S);
return OK;
}
/**************压栈,压入的值为e*******************/
Status push(SqStack &S, int e){ //要注意栈此时已满的情况
if(S.top-S.top >= S.stackSize){
S.base = (int *) realloc (S.base,(S.stackSize + STACKINCREMENT) * sizeof (int));
if(!S.base)
return ERROR;
S.top = S.base + S.stackSize;//本来这里S.top++就可以了,但是realloc函数是有可能改变原来内存的地址的,故用这个
S.stackSize = S.stackSize + STACKINCREMENT;
}
*S.top = e;
S.top++;
return OK;
}
/**************出栈,将刚在栈顶的值放在e中*******************/
Status pop(SqStack &S, int &e){
if(S.base == S.top){
printf("栈已空,删除错误!");
return ERROR;
}
--S.top;
e = *S.top;
return OK;
}
/**************得到栈顶值,放在e中*******************/
Status getTop(SqStack S, int &e){
if(S.top = S.base){
printf("栈为空");
return ERROR;
}
e = *(S.top - 1);
return OK;
}
/**************得到栈长度******************/
int getLength(SqStack S){
int length = 0;
if(S.base == S.top)
return 0;
for(int * i = S.base; i != S.top; i++){
++length;
}
return length;
}
void main(){
SqStack s1;
int e = 0;
initStack(s1);
push(s1,1);
push(s1,2);
push(s1,3);
push(s1,4);
push(s1,5);
push(s1,6);
push(s1,7);
push(s1,8);
push(s1,9);
pop(s1,e);
for(int * i = s1.base; i != s1.top; i++){
printf("%d ", *i);
}
printf("\n");
printf("%d ", getLength( s1));
destroyStack(s1);
// printf("%d ", getLength( s1));
}