栈的顺序存储实现-白红宇

栈的顺序存储实现

阅读量：6279 次

发布时间：2019-06-22

本文共 3962 字，大约阅读时间需要 13 分钟。

栈的链式存储实现请戳

所需头文件

#include
     
      #include
      
       #include

需要的宏定义

#define STACK_INIT_SIZE 100#define STACKINCREMENT   10#define ERROR             0#define OK                1#define OVERFLOW         -1

类型别名以及结构的定义

typedef int Status;typedef char SElemType;typedef struct SNode{    SElemType *base;    SElemType *top;    int stacksize;}SqStack;

以下是具体实现

Status InitStack(SqStack *S){    assert(S);    S->base = S->top = (SElemType *)malloc(sizeof(SElemType)*STACK_INIT_SIZE);    if (!S->top)        exit(OVERFLOW);    S->stacksize = STACK_INIT_SIZE;    return OK;}void ClearStack(SqStack *S){    assert(S);    S->top = S->base;}void DestroyStack(SqStack *S){    assert(S);    free(S->base);    S->top = S->base = NULL;    S->stacksize = 0;}Status StackEmpty(SqStack *S){    return S->base == S->top;}int StackLength(SqStack *S){    return S->top - S->base;}Status GetTop(SqStack *S, SElemType *e){
    //取栈顶元素    assert(e&&S);    if (StackEmpty(S))        return ERROR;    *e = *(S->top - 1);    return OK;}Status Push(SqStack *S, SElemType e){
    //入栈    assert(S);    if (StackLength(S) >= 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){
    //出栈,e==NULL则不反回栈顶元素    assert(S);    if (StackEmpty(S))        return ERROR;    if (e)        *e = *(--S->top);    --S->top;    return OK;}void StackTraverse(SqStack *S, void(*visit)(SElemType *)){
    //从栈底遍历栈顶    int i;    for (i = 0; i < S->stacksize; ++i)        visit(S->base + i);}

下面是测试代码

//匹配(),{},[],"",''  支持对\",\'的转义//连按两次回车退出程序int main(){    SqStack S;    SElemType c;    SElemType ctop;//存储栈顶元素    int flag = 1;//如果匹配失败,则为0    InitStack(&S);    c = getchar();    while ('\n' != c)    {        while ('\n' != c)        {            switch (c)            {            case '{
    ':            case '[':            case '(':                Push(&S, c);                break;            case '\"':                //一直读取，直到读到\n或"为止                //如果读到的是\n，则不匹配                //否则匹配                while ('\"' != (c = getchar()) && '\n' != c)                    if ('\\' == c)//对转义的支持                        getchar();                if ('\n' == c)                    flag = 0;                break;            case '\'':                //类似于对"的处理                while ('\'' != (c = getchar()) && '\n' != c)                    if ('\\' == c)                        getchar();                if ('\n' == c)                    flag = 0;                break;            case '}':                if (GetTop(&S, &ctop) == ERROR)                    flag = 0;                if ('{
    ' != ctop)                    flag = 0;                else                    Pop(&S, NULL);                break;            case ']':                if (GetTop(&S, &ctop) == ERROR)                    flag = 0;                if ('[' != ctop)                    flag = 0;                else                    Pop(&S, NULL);                break;            case ')':                if (GetTop(&S, &ctop) == ERROR)                    flag = 0;                if ('(' != ctop)                    flag = 0;                else                    Pop(&S, NULL);                break;            default:                break;            }//switch            if (!flag)                break;            c = getchar();        }//while        if (!StackEmpty(&S) || 0 == flag)        {            if ('\n' != c)                while ('\n' != getchar());            printf("不匹配\n");        }        else            printf("匹配\n");        ClearStack(&S);        flag = 1;        c = getchar();    }//while    printf("谢谢使用\n");    system("pause");    return 0;}//main

测试结果：