C语言数据结构——桟、桟的顺序存储结构表示

小咪咪 2022-06-17 14:15 222阅读 0赞

1、桟是限定只在表位进行插入和删除操作的线性表，我们把允许插入的一端叫作栈顶，另一端称为栈底，不含任何数据元素的桟称为空栈。桟又称为先进后出的线性表。  
2、桟的插入操作称为出桟、压桟、入栈；桟的删除操作称为出桟、弹桟。

3、`/*桟的抽象数据类型*/`

InitStack(*S) //初始化操作，建立一个空桟
    DestroyStack(*S)  //若桟存在，销毁它
    ClearStack(*S)  //清空桟
    StackEmpty(*S)  //若桟为空，返回TRUE，否则返回FALSE
    GetTop(*S,e) //若桟存在且非空，用e返回栈顶元素
    Push(*S,e)  //若桟存在，插入新元素e到桟中，并称为栈顶元素
    Pop(*S,e)  //删除栈顶元素，用e返回其值
    StackLength(S)  //返回桟S的元素个数

4、`/*桟的顺序存储表示，不是我自己写的*/`

#include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #define FALSE 0
    #define TRUE 1
    #define ERROR 0
    #define OVERLOW -1 
    #define OK 1 
    #define Stack_Init_Size 100  //存储空间初始分配量 
    #define StackIncrement 10   //存储空间分配增量 
    
    typedef int Status;
    typedef int SElemType; 
    
    typedef struct
    {
        SElemType *base;  //在桟构造之前和销毁之后，base的值为NULL 
        SElemType *top;   //栈顶指针 
        int stacksize;   //当前已经分配的存储空间 
    }SqStack;
    
    //构造一个空桟
    Status InitStack(SqStack &S)
    {
        S.base = (SElemType *)malloc(Stack_Init_Size*sizeof(SElemType));
        if(!S.base)
            exit(OVERLOW);  //存储分配失败
        S.top = S.base;
        S.stacksize = Stack_Init_Size;
        return  OK; 
    }
    
    //销毁桟
    Status DestroyStack(SqStack &S)
    {
        if(S.base == S.top)
            return ERROR;
        free(S.base);
        S.base = NULL;
        return OK;
    } 
    
    //清空桟
    Status ClearStack(SqStack &S)
    {
        S.base = S.top;
        S.stacksize = 0;
        return OK;
    } 
    
    //判断桟是否为空
    Status StackEmpty(const SqStack &S)
    {
        if(S.base == S.base)
            return TRUE; //桟空
        return FALSE; 
    } 
    
    //返回桟S的元素个数
    Status StackLength(const SqStack &S)
    {
        return S.top-S.base; 
    } 
    
    //返回桟顶元素
    Status GetTop(const SqStack &S,SElemType &e)
    {
        if(S.top == S.base)
            return ERROR;
        e = *(S.top-1);
        return OK;
    } 
    
    //插入e为新的栈顶元素
    Status Push(SqStack &S,const SElemType &e)
    {
        if(S.top-S.base >= S.stacksize)  //满桟
        {
            S.base = (SElemType*)realloc(S.base,sizeof(SElemType)*(S.stacksize+StackIncrement));
            if(!S.base)
                exit(OVERLOW);
            S.top = S.base + S.stacksize;
            S.stacksize = S.stacksize + StackIncrement; 
        } 
        *S.top++ = e;
        return OK;
    } 
    
    //若桟不为空，删除桟S的栈顶元素
    Status Pop(SqStack &S,SElemType &e)
    {
        if(S.top == S.base)
            return ERROR;
        e = *--S.top;
        return OK;
    } 
    
    Status Disp(const SElemType &a)
    {
        return OK;
    }
    
    //从桟顶到桟底依次输出元素 
    Status StackTraverse(SqStack S,Status(*Visit)(const SElemType &e))
    {
        if(S.top == S.base)
            return ERROR;
        while(S.base < S.top)
        {
            Visit(*S.base++); 
        } 
        return OK;
    }
    
    int main()
    {
        SqStack S;
        int e;
        InitStack(S);
        for(int i=1;i<=10;i++)
            Push(S,i); //10个元素
        if(StackEmpty(S))
            printf("桟空\n");
        else
            printf("桟不空\n");
        printf("元素的个数为:%d个\n",StackLength(S));
        GetTop(S,e);
        printf("从桟底到桟顶的元素分别为:\n");
        StackTraverse(S,Disp);
        printf("\n");
        printf("桟顶的元素为:\n",e);
        Pop(S,e);
        printf("弹出栈顶的元素为:%d\n",e);
        printf("此时元素的个数为%d个\n",StackLength(S));
        printf("从栈底到栈顶的元素分别为:\n");
        StackTraverse(S,Disp);
        printf("\n");
        ClearStack(S);
        printf("桟已清空\n");
        printf("此时元素的个数为%d个\n",StackLength(S));
        return 0;
    }