数据结构-链队

待我称王封你为后i 2022-07-28 05:04 126阅读 0赞

/*
    编写一个程序，实现链队的各种基本运算（假设栈中元素类型为char）。并完成下面功能：
    （1）初始化链队q;
    （2）判断链队q是否非空；
    （3）依次进队元素a,b,c;
    （4）出队一个元素，并输出该元素；
    （5）输出队列q的元素个数；
    （6）依次进链队元素d,e,f；
    （7）输出链队q的元素个数；
    （8）输出出队序列；
    （9）释放链队。
    */
    
    #include <iostream>
    #include <malloc.h>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    typedef char ElemType;
    typedef struct qnode
    {
        ElemType data;
        struct qnode *next;
    }QNode;                  //链队数据节点类型定义
    
    typedef struct
    {
        QNode *front;
        QNode *rear;
    }LiQueue;                 //链队类型定义
    
    void InitQueue(LiQueue *&q)           //初始化链队q
    {
        q=(LiQueue *)malloc(sizeof(LiQueue));
        q->front=q->rear=NULL;
    }
    
    bool QueueEmpty(LiQueue *q)           //判断链队q是否非空；
    {
        return (q->rear!=NULL);
    }
    
    void enQueue(LiQueue *&q,ElemType e)      //进队
    {
        QNode *p;
        p=(QNode *)malloc(sizeof(QNode));
        p->data=e;
        p->next=NULL;
        if(q->rear==NULL)
            q->front=q->rear=p;
        else
        {
            q->rear->next=p;
            q->rear=p;
        }
    }
    
    bool deQueue(LiQueue *&q,ElemType &e)   //出队，并输出
    {
        QNode *t;
        if(q->rear==NULL)
            return false;
        t=q->front;
        if(q->front==q->rear)
            q->front=q->rear=NULL;
        else
            q->front=q->front->next;
        e=t->data;
        free(t);
        return true;
    }
    
    int getLength(LiQueue *q)            //输出链队q的元素个数
    {
        int length=0;
        QNode *p=q->front;
        while(p!=NULL)
        {
            length++;
            p=p->next;
        }
        return length;
    }
    
    void DestoryQueue(LiQueue *&q)      //释放链队
    {
        QNode *p=q->front,*r;
        if(p!=NULL)
        {
            r=p->next;
            while(r!=NULL)
            {
                free(p);
                p=r;
                r=p->next;
            }
        }
        free(p);
        free(q);
    }
    
    int main()
    {
        ElemType a[10],e;
        LiQueue *q;
        InitQueue(q);
        cout<<"链队q是否非空？";
        if(QueueEmpty(q))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        cout<<"输入要进队元素:";
        gets(a);
        for(int i=0;i<strlen(a);i++)
        {
            enQueue(q,a[i]);
        }
        cout<<"元素已进队"<<endl;
        cout<<"链队是否非空？";
        if(QueueEmpty(q))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        deQueue(q,e);
        cout<<"出队一个元素并输出："<<e<<endl;
        cout<<"链队q的元素个数："<<getLength(q)<<endl;
        cout<<"输入要进队元素:";
        gets(a);
        for(int i=0;i<strlen(a);i++)
        {
            enQueue(q,a[i]);
        }
        cout<<"元素已进队"<<endl;
        cout<<"链队q的元素个数："<<getLength(q)<<endl;
        cout<<"输出出队序列：";
        for(int i=getLength(q)-1;i>=0;i--)
        {
            deQueue(q,e);
            cout<<e<<" ";
        }
        cout<<endl;
        cout<<"链队q是否非空？";
        if(QueueEmpty(q))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        DestoryQueue(q);
        cout<<"链队已释放！"<<endl;
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220727/6901f1a6e0f14c4ebf07322e25e5a88e.png