数据结构-链式队列的实现-蒲公英云

数据结构-链式队列的实现

青旅半醒 2022-08-24 11:46 262阅读 0赞

头文件Queue.h

#ifndef Queue_H
#define Queue_H
typedef int Item;
typedef struct node * PNode;
typedef struct node
{
    Item data;
    PNode next;
}Node;
typedef struct
{
    PNode front;
    PNode rear;
    int size;
}Queue;
/*构造一个空队列*/
Queue *InitQueue();
/*销毁一个队列*/
void DestroyQueue(Queue *pqueue);
/*清空一个队列*/
void ClearQueue(Queue *pqueue);
/*判断队列是否为空*/
int IsEmpty(Queue *pqueue);
/*返回队列大小*/
int GetSize(Queue *pqueue);
/*返回队头元素*/
PNode GetFront(Queue *pqueue,Item *pitem);
/*返回队尾元素*/
PNode GetRear(Queue *pqueue,Item *pitem);
/*将新元素入队*/
PNode EnQueue(Queue *pqueue,Item item);
/*队头元素出队*/
PNode DeQueue(Queue *pqueue,Item *pitem);
/*遍历队列并对各数据项调用visit函数*/
void QueueTraverse(Queue *pqueue,void (*visit)());
#endif

实现代码Queue.c如下:

#include"Queue.h"
#include<malloc.h>
#include<stdio.h>
/*构造一个空队列*/
Queue *InitQueue()
{
    Queue *pqueue = (Queue *)malloc(sizeof(Queue));
    if(pqueue!=NULL)
    {
        pqueue->front = NULL;
        pqueue->rear = NULL;
        pqueue->size = 0;
    }
    return pqueue;
}
/*销毁一个队列*/
void DestroyQueue(Queue *pqueue)
{
    if(IsEmpty(pqueue)!=1)
        ClearQueue(pqueue);
    free(pqueue);
}
/*清空一个队列*/
void ClearQueue(Queue *pqueue)
{
    while(IsEmpty(pqueue)!=1)
    {
        DeQueue(pqueue,NULL);
    }
}
/*判断队列是否为空*/
int IsEmpty(Queue *pqueue)
{
    if(pqueue->front==NULL&&pqueue->rear==NULL&&pqueue->size==0)
        return 1;
    else
        return 0;
}
/*返回队列大小*/
int GetSize(Queue *pqueue)
{
    return pqueue->size;
}
/*返回队头元素*/
PNode GetFront(Queue *pqueue,Item *pitem)
{
    if(IsEmpty(pqueue)!=1&&pitem!=NULL)
    {
        *pitem = pqueue->front->data;
    }
    return pqueue->front;
}
/*返回队尾元素*/
PNode GetRear(Queue *pqueue,Item *pitem)
{
    if(IsEmpty(pqueue)!=1&&pitem!=NULL)
    {
        *pitem = pqueue->rear->data;
    }
    return pqueue->rear;
}
/*将新元素入队*/
PNode EnQueue(Queue *pqueue,Item item)
{
    PNode pnode = (PNode)malloc(sizeof(Node));
    if(pnode != NULL)
    {
        pnode->data = item;
        pnode->next = NULL;
        if(IsEmpty(pqueue))
        {
            pqueue->front = pnode;
        }
        else
        {
            pqueue->rear->next = pnode;
        }
        pqueue->rear = pnode;
        pqueue->size++;
    }
    return pnode;
}
/*队头元素出队*/
PNode DeQueue(Queue *pqueue,Item *pitem)
{
    PNode pnode = pqueue->front;
    if(IsEmpty(pqueue)!=1&&pnode!=NULL)
    {
        if(pitem!=NULL)
            *pitem = pnode->data;
        pqueue->size--;
        pqueue->front = pnode->next;
        free(pnode);
        if(pqueue->size==0)
            pqueue->rear = NULL;
    }
    return pqueue->front;
}
/*遍历队列并对各数据项调用visit函数*/
void QueueTraverse(Queue *pqueue,void (*visit)())
{
    PNode pnode = pqueue->front;
    int i = pqueue->size;
    while(i--)
    {
        visit(pnode->data);
        pnode = pnode->next;
    }
}

简单测试程序Test.c

#include"Queue.h"
#include<stdio.h>
void print(Item i)
{
    printf("该节点元素为%d\n",i);
}
main()
{
    Queue *pq = InitQueue();
    int i,item;
    printf("0-9依次入队并输出如下：\n");
    for(i=0;i<10;i++)
    {
        EnQueue(pq,i);
        GetRear(pq,&item);
        printf("%d ",item);
    }
    printf("\n从队头到队尾遍历并对每个元素执行print函数：\n");    
    QueueTraverse(pq,print);
    printf("队列中元素依次出队列并输出如下：\n");
    for(i=0;i<10;i++)
    {
        DeQueue(pq,&item);
        printf("%d ",item);
    }
    ClearQueue(pq);
    if(IsEmpty(pq))
        printf("\n将队列置空成功\n");
    DestroyQueue(pq);
    printf("队列已被销毁\n");
}