MENU

C语言 顺序栈及基本操作实现

2017 年 12 月 06 日 • 日常作业

《数据结构》实验让写一个栈,我写了顺序栈。这里是我的代码,供将来自己检索,和大家参考之用。

/* 
    栈的结构和基本操作
    By Bro.Xu on 04/12/17 under GCC 5.4.0
    提供给各位参考,未经测试,切勿照搬或轻信,包括命名
*/
#include <malloc.h>
#include <stdio.h>

#define ERROR -1
#define OK 1
#define TRUE 1
#define FALSE 0

/*
    除了在外面 define DataType 和 MAXNUM 外,还应该
    define SafeMode,值有 TRUE 和 FALSE
    define SafeData,值的类型为 DataType,作为出栈时安全数据填充
*/

typedef struct Stack
{
    int top;
    DataType data[MAXNUM];
} Stack;


/*
    初始化栈
    @返回 返回栈的指针,失败返回 NULL
    @使用示例
    Stack *stack = initStack();
    if(!stack) printf("栈建立失败,可能内存不足!");
*/
Stack *initStack(){
    if(MAXNUM <= 0) return NULL;
    if(SafeMode != TRUE && SafeMode != FALSE) return NULL;

    Stack *S = malloc(sizeof(Stack));
    if(!S) return NULL;
    S->top = -1;
    return S;
}

/*
    判断栈空
    @参数 S 栈的指针
    @返回 为空返回 TRUE,非空返回 FALSE,失败返回 ERROR
*/
int isStackEmpty(Stack *S){
    if(!S) return ERROR;

    return S->top == -1 ? TRUE : FALSE;
}

/*
    判断栈满
    @参数 S 栈的指针
    @返回 为满返回 TRUE,不满返回 FALSE,失败返回 ERROR
*/
int isStackFull(Stack *S){
    if(!S) return ERROR;

    return S->top == MAXNUM-1 ? TRUE : FALSE;
}

/*
    元素入栈
    @参数 S 栈的指针
          data 要入栈的元素
    @返回 已入栈元素的索引号,失败返回 ERROR
*/
int inStack(Stack *S, DataType data){
    if(!S) return ERROR;
    if(isStackFull(S) == TRUE) return ERROR;

    S->data[++S->top] = data;
    return S->top;
}

/*
    元素出栈
    @参数 S 栈的指针
          pd 要出栈到的元素的空间,若不需存放可设为 NULL
    @返回 已出栈元素的原索引号,失败返回 ERROR
*/
int outStackTo(Stack *S, DataType *pd){
    if(!S) return ERROR;
    if(isStackEmpty(S) == TRUE) return ERROR;

    if(pd) *pd = S->data[S->top];
    if(SafeMode == TRUE) S->data[S->top] = SafeData;
    return S->top--;
}

/*
    元素出栈,而不存放出栈元素的值
    @参数 S 栈的指针
    @返回 已出栈元素的原索引号,失败返回 ERROR
*/
int outStack(Stack *S){
    return outStackTo(S, NULL);
}

/*
    读栈顶,而不进行异常校验(危险)
    @参数 S 栈的指针
    @返回 栈顶元素
*/
DataType readStack(Stack *S){
    return S->data[S->top];
}

/*
    输出栈
    @参数 S 栈的指针
          printNode 输出函数的指针,该函数有两个参数,参数1接收栈元素,参数2接收对应索引号
          sep 分隔符字符串
    @返回 成功返回 OK,失败返回 ERROR
    @使用示例
    void myPrint(int data, int index){
        printf("[%d]%d", index, data);
    }
        printStack(stack, myPrint, ", ");
*/
int printStack(Stack *S, void (*printNode)(DataType,int), char *sep){
    if(!S) return ERROR;

    int top = S->top;
    for(int i=0; i<=top; ++i){
        if(i > 0) printf("%s", sep);
        printNode(S->data[i], i);
    }
    return OK;
}