链式队列的C++实现

一、数据结构

[plain]view
plain copy

struct QNode    //定义队列结点的数据结构  

{  

    QNode *next; //指针域,指向下一个结点  

    double data;    //数据域，存储队列信息  

};  

struct LinkQueue    //定义队列的数据结构  

{  

    QNode *front;      //队首指针,指向QNode类型的指针  

    QNode *rear;       //队尾指针  

};

[cpp]view
plain copy

void InitQueue(LinkQueue &Q)     //构造一个空的队列  

int IsEmpty(LinkQueue &Q)    //判断队列是否为空  

void EnQueue(LinkQueue &Q,double e)     //从队列尾部插入一个结点  

void DeQueue(LinkQueue &Q, double &e)   //从队列首部删除一个结点  

void DestoryQueue(LinkQueue &Q)       //销毁一个队列

二、完整代码

[cpp]view
plain copy

#include "stdafx.h"  

#include <iostream>  

#include <cstdlib>  

using namespace std;  

struct QNode    //定义队列结点的数据结构  

{  

    QNode *next; //指针域,指向下一个结点  

    double data;    //数据域，存储队列信息  

};  

struct LinkQueue    //定义队列的数据结构  

{  

    QNode *front;      //队首指针,指向QNode类型的指针  

    QNode *rear;       //队尾指针  

};  

void InitQueue(LinkQueue &Q)     //构造一个空的队列  

{  

    QNode *q;  

    q = new QNode;    //申请一个结点的空间  

    q->next = NULL;   //当作头结点  

    //队首与队尾指针都指向这个结点，指针域为NULL  

    Q.front = q;  

    Q.rear = q;  

}  

int IsEmpty(LinkQueue &Q)    //判断队列是否为空  

{  

    if (Q.rear == Q.front)  

        return 0;  

    else  

        return 1;  

}  

void EnQueue(LinkQueue &Q,double e)     //从队列尾部插入元素  

{  

    QNode *p;    //新创建一个结点  

    p = new QNode;  

    p->next = NULL;  

    p->data = e;  //输入数据信息  

    //将新结点插入队列尾部  

    Q.rear->next = p;       

    Q.rear = p;       //设置新的尾结点  

}  

void DeQueue(LinkQueue &Q, double &e)   //从队列首部删除一个结点  

{  

    QNode *p;  

    p = Q.front->next;  

    e = p->data;    //保存要出队列的数据  

    Q.front->next = p->next;       //将下一个结点当作头结点后面链接的第一个结点  

    if (Q.rear == p)    //如果要删除的元素即为尾结点，则将头指针赋予尾指针，一同指向头结点，表示队列为空  

        Q.rear = Q.front;  

    delete p;  

}  

void DestoryQueue(LinkQueue &Q)       //销毁一个队列  

{  

    while (Q.front)  

    {  

        Q.rear = Q.front;    //从头节点开始，一个一个删除队列结点，释放空间  

        delete Q.front;  

        Q.front = Q.rear;  

    }  

}  

int _tmain(int argc, _TCHAR* argv[])  

{  

    LinkQueue *Q;  //定义一个队列Q  

    Q = new LinkQueue;    

    InitQueue(*Q);  

    cout << "开始往队列里输入数据，以-1作为结束符" << endl;  

    cout << "请输入一个数：" << endl;  

    double a, x;  

    cin >> a;  

    while (a != -1)  

    {  

        EnQueue(*Q, a);  

        cout << "请输入一个数：" << endl;  

        cin >> a;  

    }  

    //输出队列元素,队首->队尾  

        QNode *p;  

        p = Q->front->next;  

        if (p == NULL)     //如果为空表，直接退出  

        {  

            cout << "队列为空！" << endl;  

            return 0;  

        }  

        cout << "队列数据依次为：" << endl;  

        while (p!=NULL)  

        {  

            cout << p->data << " ";  

            p = p->next;  

        }  

        cout << endl;  

    //删除队列元素  

    while (!IsEmpty(*Q))  

    {  

        DeQueue(*Q, x);  

        cout << x << " ";  

    }  

    //释放内存空间  

    delete Q->front;  

    delete Q;  

    return 0;  

}

三、实验截图

链式队列的C++实现

五、总结

之所以写的这么详细，我是因为深受网络之苦，在老师心中我的智商还蛮高的，但每次自己上网求助，看一些别人写博客时，特别郁闷与无力，有的基本没注释，有的有注释，但太敷衍塞责，有的思路太混乱，自己都没搞清楚，就写出来害人，看着看着就没兴趣了，完全不是给人看的，相信除了作者，没人能够看懂。所以，我本着良心，既然发了博客，就坚持写的能够让绝大部分人看懂，自己宁愿多花点时间写注释，也不愿意网友看了我的博客而扫了兴致。通过这个算法，我对队列有了更好的认识，因为它要定义两个结构体，一般单链表就一个结构体，所以，我刚开始花了些时间才明白为什么，让后自己一个一个函数去实现功能，最后经过main测试，得到最后的想要的结果。我相信实践是最能提升编程水平的，大家自己私下一定要好好思考问题，实在不懂就可以问，查，但最后，自己一定要自己实现一遍，不然忘的会很快。。。后面还会陆续更新严蔚敏的数据结构（c语言版）的各种算法实现，我也是现学现卖，希望各位朋友可以批评指正。

链式队列的C++实现

相关推荐