顺序栈.cpp

最近重新复习了数据结构，并且手动实现了一些代码，供大家使用，也供自己以后复习总结用.
顺序栈是使用顺序存储的方式。若使用链式存储的方式的就叫链式栈。

@author：Kadima

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;     //用作函数值类型，表示函数结果状态
typedef int ElemType;

typedef struct{
    ElemType * elem;    //  存储空间的基址
    int top;            //栈顶元素的下一个位置，简称栈顶位标
    int size;           //当前分配的存储容量
    int increment;      //扩容时，增加的存储容量
}SqStack;               //顺序栈

/*初始化栈操作*/
Status InitStack_Sq(SqStack &S, int size, int inc){//初始化空顺序栈S
    S.elem = (ElemType *)malloc(size*sizeof(ElemType));//分配存储空间     使用中间变量是防止拓展失败，把之前的数据弄丢了
    if(NULL==S.elem)    return OVERFLOW;
    S.top = 0;      //置S为空栈
    S.size = size;  //初始容量值
    S.increment = inc;//初始增量值
    return OK;
}

/*入栈操作*/
Status Push_Sq(SqStack &S, ElemType e){//元素e压入栈S
    ElemType * newbase;
    if(S.top >= S.size){//若栈顶位标已到达所分配的容量，则栈满，扩容
        newbase = (ElemType *)realloc(S.elem, (S.size+S.increment)*sizeof(ElemType));
        if(NULL==newbase)   return OVERFLOW;
        S.elem = newbase;
        S.size += S.increment;
    }
    S.elem[S.top++] = e;//e入栈，并将S.top加1
    return OK;
}

/*判断栈S是否为空，若空则返回TRUE，否则FALSE*/
Status StackEmpty_Sq(SqStack &S){
    if(S.top == 0)
        return TRUE;
    else
        return FALSE;
}

/*栈S的栈顶元素出栈，并用e返回*/
Status Pop_Sq(SqStack &S, ElemType &e){
    if(0==S.top)
        return ERROR;
    e = S.elem[--S.top];//e出栈，并将S.top减1
    return OK;
}

/*取栈S的栈顶元素，并用e返回*/
Status GetTop_Sq(SqStack S, ElemType &e){
    if(0==S.top)
        return ERROR;
    else
        e = S.elem[S.top-1];
    return OK;
}

/*销毁顺序栈S*/
Status DestroyStack_Sq(SqStack &S){
    if(S.top!=0){
        free(S.elem);
        //释放掉内存只是把申请的内存返还给系统
        //还需要把指针设置为空
        S.top = 0;
        S.elem = NULL;
        return OK;
    }
    else
        return ERROR;
}

/*清空栈S*/
void ClearStack_Sq(SqStack &S){
    //只要S.top设置为0即可
    S.top = 0;
}


/*进制转换函数：十进制转化为八进制*/
void Converstion(int N){
    SqStack S;
    ElemType e;
    InitStack_Sq(S,10,5);//栈S的初始容量为10
    while(N!=0){
        Push_Sq(S, N%8);    //将N除以8的余数入栈
        N /= 8;             //N取值为其除以8的商
    }
    printf("八进制数:");
    while(FALSE == StackEmpty_Sq(S)){//依次输出栈中的余数
        Pop_Sq(S,e);
        printf("%d",e);
    }
}

/*
括号匹配算法：
1.依次扫描括号序列，每读入一个括号：
①若是左括号，则入栈
②若是右括号，首先检查栈，若栈空，则表明该“右括号”多余，不匹配，结束。
否则和栈顶元素比较，若相匹配，则“左括号出栈”，否则表明不匹配，结束。
2.当读入完所有括号时检查栈，若栈空，则括号正确匹配，结束，否则“左括号”多余，不匹配，结束。
*/
Status Matching(char *exp, int n){//检查exp中长度为n的括号序列是否匹配
    int i = 0;
    ElemType e;
    SqStack S;
    InitStack_Sq(S, n, 5);
    while(i<n){
        switch(exp[i]){
            case '(':
            case '[':Push_Sq(S, exp[i]);i++;break;
            case ')':
            case ']':
                if(TRUE == StackEmpty_Sq(S))
                    return ERROR;   //"右括号"多余
                else{
                    GetTop_Sq(S,e);
                    if((exp[i]==')'&&e=='(')||(exp[i]==']'&&e=='[')){
                        Pop_Sq(S,e);
                        i++;
                    }
                    else
                        return ERROR;   //右括号是“非所期待的”
                }
                break;
        }
    }
    if(TRUE==StackEmpty_Sq(S))
        return OK;
    else
        return ERROR;   //“左括号”多余
}


int main()
{
    /*十进制数转化为八进制数*/
    int num;
    printf("十进制数:");
    scanf("%d",&num);//input:1348,output:2504
    Converstion(num);
    printf("\n");

    /*括号匹配*/
    char c[20];
    char * exp;
    int n;
    exp = c;
    printf("输入括号串:");
    scanf("%s",c);
    n = strlen(c);
    if(Matching(exp,n))
        printf("括号匹配成功\n");
    else
        printf("括号匹配失败\n");
    return 0;
}