链队列的基本操作

比眉伴天荒 2022-05-27 00:45 192阅读 0赞

将队列的基本运算实现  
EnQueue()  
DeQueue()  
InitQueue()  
GetHead()  
QueueEmpty()  
QueueLength()

写在queue.c中，对应的函数原型写在queue.h中。

queue.h

#ifndef QUEUE_H_INCLUDED
    #define QUEUE_H_INCLUDED
    #include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR 0
    #define TRUE  1
    typedef int ElemType;
    typedef int status;
    typedef struct Qnode
    {
        ElemType data;
        struct Qnode *next;
    }Qnode,*QuePtr;
    
    typedef struct
    {
        QuePtr front;
        QuePtr rear;
    }LinkQueue,*pLinkQueue;
    
    status InitQueue(pLinkQueue L);//构造一个空队列
    void DestoryQueue(pLinkQueue L);//销毁队列
    //判断队列是否为空
    status QueueEmpty(pLinkQueue L);
    //获得队列长度
    int QueueLength(pLinkQueue L);
    //新元素入队 [先进先出原则：在队尾的位置插入] element-要插入元素
    status EnQueue(pLinkQueue L,ElemType element);
    //新元素出队,同时保存出队的元素 [先进先出原则：在队头的位置删除]
    status DeQueue(pLinkQueue L,ElemType *pElement);
    //遍历队列
    void queueTraverse(pLinkQueue L);
    
    #endif // QUEUE_H_INCLUDED

queue.c

#include "queue.h"
    
    status InitQueue(pLinkQueue L)//构造一个空队列
    {
        L->front = L->rear = (QuePtr)malloc(sizeof(Qnode));
    
        if(!L->front)
        {
            printf("申请内存失败！\n");
            return ERROR;
        }
    
        L->front->next = NULL;//设置头结点指针域为空
        return TRUE;
    }
    
    void DestoryQueue(pLinkQueue L)//销毁队列
    {
        free(L->front);
        free(L->rear);
        L->front = L->rear = NULL;
    
    }
    //判断队列是否为空
    status QueueEmpty(pLinkQueue L)
    {
        if(L->front == L->rear)
            return TRUE;
        return ERROR;
    }
    //获得队列长度
    int QueueLength(pLinkQueue L)
    {
        int length = 0;
        QuePtr temp = L->front;
        while(temp != L->rear)
        {
            length ++;
            temp = temp->next;
        }
    
        return length;
    }
    
    //新元素入队 [先进先出原则：在队尾的位置插入] element-要插入元素
    status EnQueue(pLinkQueue L,ElemType element)
    {
        QuePtr q = (QuePtr)malloc(sizeof(Qnode));
        if(!q)
        {
            printf("申请内存失败！\n");
            return ERROR;
        }
    
        q->data = element;
        q->next = NULL;
    
        L->rear->next = q;//rear作为最后一个结点，next指向新申请的内存
        L->rear = q;//让q作为最后一个结点
        return TRUE;
    
    }
    
    //新元素出队,同时保存出队的元素 [先进先出原则：在队头的位置删除]
    status DeQueue(pLinkQueue L,ElemType *pElement)
    {
        QuePtr q;
        q = L->front->next;
    
        //如果出列的为第一个结点，则指向头结点，以免指针悬空
    
        if(L->front->next == L->rear)
        {
            L->rear = L->front;
        }
    
        *pElement  = q->data;
        L->front->next = q->next;
        free(q);
        q = NULL;
        return TRUE;
    
    }
    
    //遍历队列
    void queueTraverse(pLinkQueue L)
    {
        QuePtr q;
        q = L->front;
         printf("将队列中的所有元素出队:\n");
         while(q != L->rear)
        {
    
            q = q->next;
            printf("%d  ", q->data);
        }
        printf("\n");
    }

main.c

#include <stdio.h>
    #include <stdlib.h>
    #include "queue.h"
    int main()
    {
       int e;          //用于保存出队的元素
    
        //给头结点申请内存
        QuePtr head= (QuePtr)malloc(sizeof(Qnode));
        if(!head) //检测是否申请失败
        {
            printf("申请内存失败！\n");
            return ERROR;
        }
    
        //调用初始化队列的函数
       InitQueue(head);
        //调用出队函数
        EnQueue(head, 1);
        EnQueue(head, 2);
        EnQueue(head, 3);
        EnQueue(head, 4);
        EnQueue(head, 5);
        EnQueue(head, 6);
        EnQueue(head, 7);
        EnQueue(head, 8);
        //调用遍历队列的函数
        queueTraverse(head);
    
        //调用出队函数
        if(DeQueue(head, &e))
        {
            printf("出队一次，元素为：%d\n", e);
        }
        queueTraverse(head);
        if(DeQueue(head, &e))
        {
            printf("出队一次，元素为：%d\n", e);
        }
        queueTraverse(head);
    
        printf("队列长度是%d\n",QueueLength(head));
    
        //clearQueue(head);   //清空队列
        //queueTraverse(head);
    
        free(head);
        head = NULL;
    
        return 0;
    }