数据结构-链栈

约定不等于承诺〃 2022-07-28 04:30 197阅读 0赞

/*
    编写一个程序，实现链栈（假设栈中元素类型为char）的各种基本运算。并完成下面功能：
    （1）初始化链栈s;
    （2）判断链栈s是否非空；
    （3）依次进链栈元素a,b,c,d,e;
    （4）判断链栈s是否非空；
    （5）输出链栈长度；
    （6）输出从栈顶到栈底元素；
    （7）输出出链栈序列；
    （8）判断链栈s是否非空；
    （9）释放链栈。
    */
    
    #include <iostream>
    #include <malloc.h>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    typedef char ElemType;
    typedef struct linknode
    {
        ElemType data;
        struct linknode *next;
    }LiStack;               //定义链栈类型
    
    void InitStack(LiStack *&s)           //初始化链栈s
    {
        s=(LiStack *)malloc(sizeof(LiStack));
        s->next=NULL;
    }
    
    bool StackEmpty(LiStack *s)           //判断链栈s是否非空
    {
        return (s->next!=NULL);
    }
    
    void Push(LiStack *&s,ElemType e)      //进栈
    {
        LiStack *p;
        p=(LiStack *)malloc(sizeof(LiStack));
        p->data=e;
        p->next=s->next;
        s->next=p;
    }
    
    int getLength(LiStack *s)            //输出链栈长度
    {
        int i=0;
        LiStack *p=s->next;
        while(p!=NULL)
        {
            i++;
            p=p->next;
        }
        return (i);
    }
    
    void DispStack(LiStack *s)    //输出从栈顶到栈底元素
    {
        LiStack *p=s->next;
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
    }
    bool Pop(LiStack *&s,ElemType &e)   //出栈
    {
        LiStack *p;
        if(s->next==NULL)
            return false;
        p=s->next;
        e=p->data;
        s->next=p->next;
        free(p);
        return true;
    }
    
    void DestoryStack(LiStack *&s)      //释放链栈
    {
        LiStack *p=s,*q=s->next;
        while(q!=NULL)
        {
            free(p);
            p=q;
            q=p->next;
        }
    }
    
    int main()
    {
        ElemType a[10],b;
        LiStack *s;
        InitStack(s);
        cout<<"链栈是否非空？";
        if(StackEmpty(s))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        cout<<"输入要进栈元素:";
        gets(a);
        for(int i=0;i<strlen(a);i++)
        {
            Push(s,a[i]);
        }
        cout<<"元素已进栈"<<endl;
        cout<<"链栈是否非空？";
        if(StackEmpty(s))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        cout<<"栈的长度："<<getLength(s)<<endl;
        cout<<"输出从栈顶到栈底元素:";
        DispStack(s);
        cout<<"链栈是否非空？";
        if(StackEmpty(s))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        cout<<"输出出栈序列：";
        for(int i=getLength(s)-1;i>=0;i--)
        {
            Pop(s,b);
            cout<<b<<" ";
        }
        cout<<endl;
        cout<<"链栈是否非空？";
        if(StackEmpty(s))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        DestoryStack(s);
        cout<<"栈已释放！"<<endl;
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220727/45a6be872c404f6a8501fc76c7cdcdf3.png