数据结构上机实践第七周项目2 - 自建算法库——链队（链式队列）

/*   
copyright （t） 2016，烟台大学计算机学院   
*All rights reserved.   
*文件工程名称：1.cbd   
*作者：田长航  
完成日期：2017年12月22日  
*版本号：v1.0   
*问题描述：定义链队存储结构，实现其基本运算，并完成测试。   
要求：   
    1、头文件liqueue.h中定义数据结构并声明用于完成基本运算的函数。对应基本运算的函数包括：   
    void InitQueue(LiQueue *&q);  //初始化链队   
    void DestroyQueue(LiQueue *&q); //销毁链队   
    bool QueueEmpty(LiQueue *q);  //判断链队是否为空   
    int QueueLength(LiQueue *q);   //返回链队中元素个数，也称队列长度   
    bool enQueue(LiQueue *&q,ElemType e);   //进队   
    bool deQueue(LiQueue *&q,ElemType &e);  //出队   
　　2、在liqueue.cpp中实现这些函数   
　　3、在main函数中完成测试，包括如下内容：   
    (1)初始化队列q   
    (2)依次进队列元素a,b,c   
    (3)判断队列是否为空   
    (4)出队一个元素   
    (5)输出队列中元素个数   
    (6)依次进队列元素d,e,f   
    (7)输出队列中元素个数   
    (8)将队列中所有元素删除，并输出序列   
    (9)释放队列   
*输入描述：无   
*程序输出：完成测试后的运行结果   
*/    
typedef char ElemType;                      //自定义字符型数据类型    
typedef struct qnode                        //链队中数据节点的类型    
{    
    ElemType data;    
    struct qnode *next;    
} QNode;    
typedef struct                              //链队节点的类型    
{    
    QNode *front;    
    QNode *rear;    
} LiQueue;    
void InitQueue(LiQueue *&q);                //初始化链队    
void DestroyQueue(LiQueue *&q);             //销毁链队    
bool QueueEmpty(LiQueue *q);                //判断链队是否为空    
int QueueLength(LiQueue *q);                //返回链队中元素个数，也称队列长度    
void enQueue(LiQueue *&q,ElemType e);       //进队    
bool deQueue(LiQueue *&q,ElemType &e);      //出队    

#include <malloc.h>    
#include "liqueue.h"    
void InitQueue(LiQueue *&q)                 //初始化链队    
{    
    q=(LiQueue *)malloc(sizeof(LiQueue));    
    q->front=q->rear=NULL;    
}    
void DestroyQueue(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);    
}    
bool QueueEmpty(LiQueue *q)                 //判断链队是否为空    
{    
    return (q->rear==NULL);    
}    
int QueueLength(LiQueue *q)                 //返回链队中元素个数，也称队列长度    
{    
    QNode *p=q->front;    
    int length=0;                           //设计数变量，记录表长    
    while(p!=NULL)    
    {    
        length++;    
        p=p->next;    
    }    
    return length;    
}    
void enQueue(LiQueue *&q,ElemType e)        //进队    
{    
    QNode *p;    
    p=(QNode *)malloc(sizeof(QNode));    
    p->data=e;    
    p->next=NULL;                           //创建data域为e、指针域为NULL的数据节点*p    
    if(q->rear==NULL)    
        q->front=q->rear=p;    
    else    
    {    
        q->rear->next=p;    
        q->rear=p;    
    }    
}    
bool deQueue(LiQueue *&q,ElemType &e)       //出队 需考虑队列为空的情况，故设置函数类型为bool型    
{    
    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;    
}    

#include <stdio.h>    
#include <malloc.h>    
#include "liqueue.h"    
int main()    
{    
    LiQueue *q;    
    ElemType e;    
    InitQueue(q);                           //初始化队列q    
    printf("该队列已被初始化！\n");    
    if(QueueEmpty(q))                       //判断队列是否为空    
        printf("该队列为空\n");    
    else    
        printf("该队列不为空\n");    
    enQueue(q,'a');                         //依次进队列元素a,b,c    
    enQueue(q,'b');    
    enQueue(q,'c');    
    printf("元素a,b,c进队后，");    
    if(QueueEmpty(q))                       //判断队列是否为空    
        printf("该队列为空\n");    
    else    
        printf("该队列不为空\n");    
    if(deQueue(q,e)==0)                     //出队一个元素    
        printf("此队列已为空，出队操作失败！\n");    
    printf("出队成功，出队元素为%c\n",e);    
    printf("此时队列中元素个数为：%d\n",QueueLength(q));   //输出队列中元素个数    
    enQueue(q,'d');                         //依次进队列元素d,e,f    
    enQueue(q,'e');    
    enQueue(q,'f');    
    printf("元素d,e,f进队后，队列中元素个数为：%d\n",QueueLength(q));   //输出队列中元素个数    
    printf("出队序列为：");                 //将队列中所有元素删除，并输出序列    
    while(!QueueEmpty(q))    
    {    
        deQueue(q,e);    
        printf("%c",e);    
    }    
    printf("\n");    
    DestroyQueue(q);                        //释放队列    
    printf("该队列已释放！\n");    
    return 0;    
}