C语言实现线性栈

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);
}