参考着严蔚敏的《数据结构(C语言版)》,用自己拿渣的可怜的C语言做了一下午的实现。。。也没能写出来几个。。。就很菜(气哭)。。。
/*-------------------栈的结构体定义---------------------*/
#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10 // 存储空间分配增量
typedef char SElemType; /*SElemType 类型根据实际情况而定,这里假设为int */
typedef struct{
SElemType *top;
SElemType *base;
int stacksize; /* 栈的最大容量 */
}SqStack;
/*-----------------------------------------------------*/
/*初始化栈,并分配空间*/
Status InitStack(SqStack *S){
//构造一个空栈S
S = (SqStack *)malloc(sizeof(SqStack));
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;
} // InitStack
/*若栈存在,则销毁它*/
Status DestroyStack(SqStack *S){
free(S);
if(!S)return ERROR;
return OK;
}
/*将栈清空*/
Status ClearStack(SqStack *S){
}
/*若栈为空,返回true,否则返回false*/
Status StackEmpty(SqStack S){
}
/*若栈存在且非空,用e返回S的栈顶元素*/
Status GetTop(SqStack S, SElemType *e){
//若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
if(S.top == S.base)
return ERROR; //空栈判断
e = S.top - 1;
return OK;
} //GetTop
Status Push(SqStack *S, SElemType e){
//插入元素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 ++;
S->top = e;
return OK;
}
Status Pop(SqStack *S, SElemType *e){
//若栈不空,则删除S的栈顶元素,用e返回其值,变返回oK;否则返回ERROR
if(S->top == S->base)return ERROR;
e = * -- S->top;
return OK;
} //pop