new version
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
#define SINCREMENT 10
typedef char ElemType;
typedef struct{
ElemType *base;
ElemType *top; // 栈顶
int stacksize;
}SqStack;
void initStack(SqStack *s){
// 构造一个空栈
s->base = malloc(MAXSIZE*sizeof(ElemType)); // 分配空间
if (!s->base) exit(1); // error
// 此时为空栈，因此设置s->top=s->base;
s->top = s->base;
s->stacksize = MAXSIZE;
}
void destoryStack(SqStack *s){
// 销毁一个栈
free(s->base);
}
void clearStack(SqStack *s){
// 将S清空为一个空栈
if (!s->base) exit(1); // 未初始化的栈，拒绝处理
s -> top = s->base;
*(s->base) = 0;
}
int isEmpty(SqStack s){
// 判断是否为空栈
if (s.top == s.base){
return 1; // True
}else{
return 0; // False
}
}
int stackLength(SqStack s){
// 返回栈的长度
// return (s.top - s.base)/sizeof(ElemType); // error
return (s.top - s.base);
}
void getTop(SqStack s, ElemType *e){
// 用e返回栈顶元素
if (isEmpty(s)) *e =0 ; // no elements
e = s.top - 1;
}
void push(SqStack *s, ElemType e){
// 压入栈
if(stackLength(*s) >= s->stacksize-1){
// remalloc memory
s->base = realloc(s->base, s->stacksize+SINCREMENT*sizeof(ElemType));
if (!s->base) exit(1); // error
}
*s->top = e;
s->top++;
// if(stackLength(*s) >= s->stacksize)
}
void *pop(SqStack *s, ElemType *e){
// 弹出栈
if (isEmpty(*s)) exit(1); // none to pop
*e = *(s->top-1); // 这里应该是用指向，而不是用赋值
s->top--;
}
void traverse(SqStack s, void (*visit)(ElemType *)){
while (isEmpty(s)==0){
ElemType *e;
e = malloc(sizeof(ElemType));
pop(&s, e);
visit(e);
}
}
void print(ElemType *e){
printf("the value is %d\n", *e);
}
new version(depreciated) 这里实际因为只是定义了一个空指针，而未分配空间所以会出现各种很难debug的错误，所以我们使用新的版本。
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define SINCREMENT 10
typedef int ElemType;
typedef struct{
ElemType *base;
ElemType *top; // 栈顶
int stacksize;
}SqStack;
void initStack(SqStack *s){
// 构造一个空栈
s->base = malloc(MAXSIZE*sizeof(ElemType)); // 分配空间
if (!s->base) exit(1); // error
// 此时为空栈，因此设置s->top=s->base;
s->top = s->base;
s->stacksize = MAXSIZE;
}
void destoryStack(SqStack *s){
// 销毁一个栈
free(s->base);
}
void clearStack(SqStack *s){
// 将S清空为一个空栈
if (!s->base) exit(1); // 未初始化的栈，拒绝处理
s -> top = s->base;
*(s->base) = 0;
}
int isEmpty(SqStack s){
// 判断是否为空栈
if (s.top == s.base){
return 1; // True
}else{
return 0; // False
}
}
int stackLength(SqStack s){
// 返回栈的长度
// return (s.top - s.base)/sizeof(ElemType); // error
return (s.top - s.base);
}
void getTop(SqStack s, ElemType *e){
// 用e返回栈顶元素
if (isEmpty(s)) *e =0 ; // no elements
e = s.top - 1;
}
void push(SqStack *s, ElemType e){
// 压入栈
if(stackLength(*s) >= s->stacksize-1){
// remalloc memory
s->base = realloc(s->base, s->stacksize+SINCREMENT*sizeof(ElemType));
if (!s->base) exit(1); // error
}
*s->top = e;
s->top++;
// if(stackLength(*s) >= s->stacksize)
}
void *pop(SqStack *s, ElemType *e){
// 弹出栈
if (isEmpty(*s)) exit(1); // none to pop
*e = *(s->top-1); // 这里应该是用指向，而不是用赋值
s->top--;
}
void traverse(SqStack s, void (*visit)(ElemType *)){
while (isEmpty(s)==0){
ElemType *e;
pop(&s, e);
visit(e);
}
}
void print(ElemType *e){
printf("the value is %d\n", *e);
}
void main(){
SqStack stack;
initStack(&stack);
for (int i=0; i<=5; ++i){
push(&stack, i);
}
traverse(stack, print);
}
this version is not recommended.
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define SINCREMENT 10
typedef int ElemType;
typedef struct{
ElemType *base;
ElemType *top; // 栈顶
int stacksize;
}SqStack;
void initStack(SqStack *s){
// 构造一个空栈
s->base = malloc(MAXSIZE*sizeof(ElemType)); // 分配空间
if (!s->base) exit(1); // error
// 此时为空栈，因此设置s->top=s->base;
s->top = s->base;
s->stacksize = MAXSIZE;
}
void destoryStack(SqStack *s){
// 销毁一个栈
free(s->base);
}
void clearStack(SqStack *s){
// 将S清空为一个空栈
if (!s->base) exit(1); // 未初始化的栈，拒绝处理
s -> top = s->base;
*(s->base) = 0;
}
int isEmpty(SqStack s){
// 判断是否为空栈
if (s.top == s.base){
return 1; // True
}else{
return 0; // False
}
}
int stackLength(SqStack s){
// 返回栈的长度
// return (s.top - s.base)/sizeof(ElemType); // error
return (s.top - s.base);
}
void getTop(SqStack s, ElemType *e){
// 用e返回栈顶元素
if (isEmpty(s)) *e =0 ; // no elements
e = s.top - 1;
}
void push(SqStack *s, ElemType e){
// 压入栈
if(stackLength(*s) >= s->stacksize-1){
// remalloc memory
s->base = realloc(s->base, s->stacksize+SINCREMENT*sizeof(ElemType));
if (!s->base) exit(1); // error
}
*s->top = e;
s->top++;
// if(stackLength(*s) >= s->stacksize)
}
ElemType *pop(SqStack *s){
// 弹出栈
if (isEmpty(*s)) exit(1); // none to pop
ElemType* e = s->top-1; // 这里应该是用指向，而不是用赋值
s->top--;
return e;
}
void traverse(SqStack s, void (*visit)(ElemType *)){
while (isEmpty(s)==0){
ElemType *e;
e = pop(&s);
visit(e);
}
}
void print(ElemType *e){
printf("the value is %d\n", *e);
}
void main(){
SqStack stack;
initStack(&stack);
for (int i=0; i<=5; ++i){
push(&stack, i);
}
traverse(stack, print);
}
网友评论