C严蔚敏数据结构-顺序栈

布满荆棘的人生 2022-03-25 05:39 341阅读 0赞

> **1）base为栈底指针，初始化完成后，栈底指针base始终指向栈底的位置，若base的值为NULL，则表示栈结构不存在。top为栈顶指针，其初值指向栈底。每当插入新的栈顶元素时，指针top+1；删除栈顶元素时，指针top-1.因此，栈空时，top和base的值相等，都指向栈底；栈非空时，top始终指向栈顶元素的上一个位置。**
> 
> **2）stacksize指示栈可使用的最大容量**

## **顺序栈的初始化** ##

>  *  **为顺序栈动态分配一个最大容量为SIZE的数组空间，使base指向这段空间的基地址，即栈底**
>  *  **栈顶指针top初始为base，表示栈为空**
>  *  **stacksize置为栈的最大容量SIZE**

Status InitStack(Sqstack &s)
    {
        s.base = (ElemType*)malloc(SIZE*sizeof(ElemType));   //为栈底指针申请堆空间
        if(!s.base)
            exit(ERROR);
        s.top = s.base;                      //栈顶指针等于栈底指针，初始为空栈
        s.stacksize = SIZE;                  //stacksize初始化为SIZE
        return OK;
    }

## **入栈** ##

>  *  **判断栈是否满，若满则返回ERROR**
>  *  **将新元素压入栈顶，栈顶指针+1**

Status Push(Sqstack &s,ElemType e)       //入栈
    {
        if(s.top-s.base == s.stacksize)     //如果栈顶指针地址-栈底指针地址==栈容量，说明此时栈已满
        {
            printf("栈已满,无法入栈!\n");
            return ERROR;
        }
        *s.top++ = e;   //将e赋给当前top指针所在位置，top指针上移一位
        return OK;
    }

## **出栈** ##

>  *  **判断栈是否空，若空则返回ERROR**
>  *  **栈顶指针-1，栈顶元素出栈**

Status Pop(Sqstack &s,ElemType &e)      //出栈,返回出栈元素（栈顶元素）
    {
        if(s.top == s.base)                 //top==base，此时栈空
        {
            printf("栈已空!\n");
            return ERROR;
        }
        e = *--s.top;                       //先让top指针下移，取出当前top指针所在位置的值赋给e（实际元素还在数组中，只是不显示）
        return OK;
    }

## 取栈顶元素 ##

>  *  **当栈非空时，返回当前栈顶元素的值，栈顶指针保持不变**

Status GetTop(Sqstack s,ElemType &e)    //获取栈顶元素
    {
        if(s.top == s.base)
        {
            printf("栈已空!\n");
            return ERROR;
        }
        e = *(s.top-1);                     //取出top指针下一位的元素值赋给e（与出栈操作不同）
        return OK;
    }

#include <stdio.h>
    #include <stdlib.h>
    #define SIZE 20
    #define ERROR 0
    #define OK 1
    typedef int ElemType;
    typedef int Status;
    typedef struct
    {
        int* base;
        int* top;
        int stacksize;
    } Sqstack;
    Status InitStack(Sqstack &s);
    Status Push(Sqstack &s,ElemType e);
    Status Pop(Sqstack &s,ElemType &e);
    Status GetTop(Sqstack s,ElemType &e);
    void StackPrintf(Sqstack &s);
    int main()
    {
        Sqstack s;
        int n,n1;
        char c;
        InitStack(s);
        int a[] = {1,2,3,4,5,6,7,8,9,10};
        for(int i=0;i<10;i++)
        {
            Push(s,a[i]);
        }
        printf("当前栈内元素:\n");
        StackPrintf(s);
        while(true)
        {
            printf("请选择你想要执行的操作:\n1.元素入栈\n2.元素出栈\n3.取栈顶元素\n4.打印栈\n5.退出程序\n");
            scanf(" %c",&c);
            if(c == '1')
            {
                printf("请输入入栈元素:\n");
                scanf("%d",&n);
                Push(s,n);
                StackPrintf(s);
            }
            else if(c == '2')
            {
                Pop(s,n);
                printf("删除的元素为:%d\n",n);
                StackPrintf(s);
            }
            else if(c == '3')
            {
                if(GetTop(s,n1))
                printf("当前栈顶元素为:%d\n",n1);
            }
            else if(c == '4')
            {
                StackPrintf(s);
            }
            else
            {
                exit(0);
            }
        }
    }
    Status InitStack(Sqstack &s)
    {
        s.base = (ElemType*)malloc(SIZE*sizeof(ElemType));   //为栈底指针申请堆空间
        if(!s.base)
            exit(ERROR);
        s.top = s.base;                      //栈顶指针等于栈底指针，初始为空栈
        s.stacksize = SIZE;                  //stacksize初始化为SIZE
        return OK;
    }
    Status Push(Sqstack &s,ElemType e)       //入栈
    {
        if(s.top-s.base == s.stacksize)     //如果栈顶指针地址-栈底指针地址==栈容量，说明此时栈已满
        {
            printf("栈已满,无法入栈!\n");
            return ERROR;
        }
        *s.top++ = e;   //将e赋给当前top指针所在位置，top指针上移一位
        return OK;
    }
    Status Pop(Sqstack &s,ElemType &e)      //出栈,返回出栈元素（栈顶元素）
    {
        if(s.top == s.base)                 //top==base，此时栈空
        {
            printf("栈已空!\n");
            return ERROR;
        }
        e = *--s.top;                       //先让top指针下移，取出当前top指针所在位置的值赋给e（实际元素还在数组中，只是不显示）
        return OK;
    }
    Status GetTop(Sqstack s,ElemType &e)    //获取栈顶元素
    {
        if(s.top == s.base)
        {
            printf("栈已空!\n");
            return ERROR;
        }
        e = *(s.top-1);                     //取出top指针下一位的元素值赋给e（与出栈操作不同）
        return OK;
    }
    void StackPrintf(Sqstack &s)            //打印栈
    {
        int *p = s.top;                     //p等于top指针
        if(s.top == s.base)
        {
            printf("空栈!\n");
            return;
        }
        else
        {
            while(p>s.base)                 //当p==base指针时，循环终止
            {
                p--;
                printf("%d\t",*p);
            }
        }
        printf("\n");
    }

## **简化版** ##

#include <stdio.h>
    #include <stdlib.h>
    #define SIZE 20
    #define ERROR 0
    #define OK 1
    typedef int ElemType;
    typedef int Status;
    typedef struct
    {
        int data[SIZE];
        int top;
    } Sqstack;
    Status InitStack(Sqstack &s);
    Status Push(Sqstack &s,ElemType e);
    Status Pop(Sqstack &s,ElemType &e);
    Status GetTop(Sqstack s,ElemType &e);
    void StackPrintf(Sqstack &s);
    int main()
    {
        Sqstack s;
        int n,n1;
        char c;
        InitStack(s);
        int a[] = {1,2,3,4,5,6,7,8,9,10};
        for(int i=0; i<10; i++)
        {
            Push(s,a[i]);
        }
        printf("当前栈内元素:\n");
        StackPrintf(s);
        while(true)
        {
            printf("请选择你想要执行的操作:\n1.元素入栈\n2.元素出栈\n3.取栈顶元素\n4.打印栈\n5.退出程序\n");
            scanf(" %c",&c);
            if(c == '1')
            {
                printf("请输入入栈元素:\n");
                scanf("%d",&n);
                Push(s,n);
                StackPrintf(s);
            }
            else if(c == '2')
            {
                Pop(s,n);
                printf("删除的元素为:%d\n",n);
                StackPrintf(s);
            }
            else if(c == '3')
            {
                if(GetTop(s,n1))
                    printf("当前栈顶元素为:%d\n",n1);
            }
            else if(c == '4')
            {
                StackPrintf(s);
            }
            else
            {
                exit(0);
    
            }
        }
    }
    Status InitStack(Sqstack &s)    //初始化栈
    {
        s.top = 0;                  //初始栈顶指针为0
    }
    Status Push(Sqstack &s,ElemType e)       //入栈
    {
        if(s.top == SIZE)
            return ERROR;      //当栈顶指针等于SIZE时，栈满
        s.data[s.top] = e;     
        s.top++;
        return OK;
    }
    Status Pop(Sqstack &s,ElemType &e)      //出栈,返回出栈元素（栈顶元素）
    {
        if(s.top == 0)
            return ERROR;
        e = s.data[--s.top];
        return OK;
    }
    Status GetTop(Sqstack s,ElemType &e)    //获取栈顶元素
    {
        if(s.top == 0)
        {
            printf("栈已空!\n");
            return ERROR;
        }
        e = s.data[s.top-1];             //取出top指针下一位的元素值赋给e（与出栈操作不同）
        return OK;
    }
    void StackPrintf(Sqstack &s)            //打印栈
    {
        int p =s.top;
        if(s.top == 0)
        {
            printf("空栈!\n");
            return;
        }
        else
        {
            while(p!=0)                 //当p=0时循环终止
            {
                p--;
                printf("%d\t",s.data[p]);
            }
        }
        printf("\n");
    }