数据结构严薇敏——栈的顺序存储（C语言）

短命女 2022-05-18 00:27 175阅读 0赞

**栈是限定只能在表尾进行插入和删除操作的线性表。**

**栈的特点是后进先出。**

**它的顺序数据结构定义为**

typedef struct SQSTACK
    {
        ElemType *base;
        ElemType *top;
        int stacksize;       
    }SqStack;

**头文件\#include"SqStack.h"**

#ifndef SQSTACK_H_INCLUDED
    #define SQSTACK_H_INCLUDED
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define TRUE 1
    #define FALSE 0
    #define STACK_MAX_SIZE 10
    
    typedef int ElemType;
    typedef struct SQSTACK
    {
        ElemType *base;
        ElemType *top;
        int stacksize;
    }SqStack;
    //构造一个空栈
    SqStack *InitStack()
    {
        SqStack *S = (SqStack *)malloc(sizeof(SqStack));
        S->base = (ElemType *)malloc(STACK_MAX_SIZE * sizeof( ElemType));
        S->top = S->base;
        S->stacksize = STACK_MAX_SIZE;
        printf("顺序栈构造成功！\n");
        return S;
    }
    //销毁栈
    void DestoryStack(SqStack *S)
    {
        free(S);
    }
    //清空栈
    void ClearStack(SqStack *S)
    {
        S->top = S->base;
    }
    //栈是否为空
    int IsEmptyStack(SqStack *S)
    {
        if(S->top == S->base)
            return TRUE;
        else
            return FALSE;
    }
    //栈中元素的个数
    int StackLength(SqStack *S)
    {
        return S->top - S->base;
    }
    //获得栈顶元素
    ElemType GetTop(SqStack *S)
    {
        ElemType *p = S->top;
        return *p;
    }
    //插入元素
    void PushStack(SqStack *S,ElemType e)
    {
        *S->top++ = e;
    }
    //删除栈顶元素
    ElemType PopStack(SqStack *S)
    {
        ElemType e;
        if(IsEmptyStack(S) == 1)
            return -1;
        S->top--;
        e = * S->top;
        return e;
    }
    //遍历栈
    void TraverseStack(SqStack *S)
    {
        if(IsEmptyStack(S))
        {
            printf("栈为空！\n");
            return;
        }
        ElemType *p = S->top;
        p--;
        while(p >= S->base)
        {
            printf("%d\t",*p--);
        }
        printf("\n栈遍历成功！\n");
        system("pause");
    }
    #endif // SQSTACK_H_INCLUDED

**主函数main进行测试**

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #include"SqStack.h"
    
    #define n 6
    
    void teststr()
    {
        SqStack *S = InitStack();
        int i,a[n],m;
        for( i = 0 ; i < n; i++)
        {
            scanf("%d",&a[i]);
        }
        for( i = 0; i < n; i++)
            printf("%d\t",a[i]);
        printf("&\t");
        for(i = 0; i < n; i++)
            PushStack(S,a[i]);
        TraverseStack(S);
    }
    
    void testT()            //车厢调度
    {
        SqStack *S = InitStack();
        int i,a[n],m;
        printf("请输入01序列，0代表硬座，1代表软座！\n");
        for(i = 0; i < n; i++)
            scanf("%d",&a[i]);
        printf("原始车厢的序列是：");
        for(i = 0; i < n; i++)
            printf("%d",a[i]);
        printf("\n调度之后车厢的序列是：");
        for(i = 0; i < n; i++)
        {
            if(a[i] == 0)
                PushStack(S,a[i]);
            else
            {
                PushStack(S,a[i]);
                printf("%d",PopStack(S));
            }
        }
         while(!IsEmptyStack(S))
          {
               printf("%d",PopStack(S));
          }
          printf("\n");
    }
    void test()
    {
        SqStack *S = InitStack();
        int i;
        for(i = 1;i < 6;i++)
        {
            PushStack(S,i);
        }
    
        //PushStack(S,6);
        TraverseStack(S);
        //printf("删除的栈顶元素为%d\n",PopStack(S));
        //TraverseStack(S);
        //printf("栈顶元素为%d\n",GetTop(S));
        printf("栈的长度为%d\n",StackLength(S));
    }
    
    int main()
    {
        //teststr();
        //testT();
    
        //test();
        printf("\n");
        system("pause");
        return 0;
    }

**注：程序中为了方便测试其他函数，部分代码已被注释掉，如需参考请略加修改。**