数据结构严薇敏——队列的链式存储（C语言）

r囧r小猫 2022-05-18 01:56 166阅读 0赞

**如果用户的应用程序中设有循环队列，必须设定一个最大队列长度，若无法估计队列的长度，则采用链队列。**

**关于队列的描述请看前面的博客。**

## **链队列代码：** ##

**它的数据结构定义为：**

typedef int ElemType;
    
    typedef struct QNode
    {
        ElemType data;
        struct QNode *next;
    }QNode;
    typedef struct LinkQueue
    {
        QNode *front;
        QNode *rear;
        int size;         //用来计数元素个数
    }LinkQueue;

**头文件\#include"LinkQueue.h"**

#ifndef LINKQUEUE_H_INCLUDED
    #define LINKQUEUE_H_INCLUDED
    
    #include<stdio.h>
    #include<stdlib.h>
    
    #define TURE 1
    #define FALSE 0
    
    typedef int ElemType;
    
    typedef struct QNode
    {
        ElemType data;
        struct QNode *next;
    }QNode;
    typedef struct LinkQueue
    {
        QNode *front;
        QNode *rear;
        int size;
    }LinkQueue;
    
    //初始化一个空队列
    LinkQueue *Init_Queue();
    //销毁
    void Destory_Queue(LinkQueue *Q);
    //清空队列
    void Clear_Queue(LinkQueue *Q);
    //是否为空
    int IsEmpty_Queue(LinkQueue *Q);
    //队列的长度
    int Length_Queue(LinkQueue *Q);
    //获得队头元素
    ElemType GetHead_Queue(LinkQueue *Q);
    //插入
    void Enter_Queue(LinkQueue *Q,ElemType e);
    //删除
    void Delete_Queue(LinkQueue *Q);
    //遍历
    void Traverse_Queue(LinkQueue *Q);
    
    #endif // LINKQUEUE_H_INCLUDED

**头文件中函数实现LinkQueue.c**

#include"LinkQueue.h"
    //初始化
    LinkQueue *Init_Queue()
    {
        LinkQueue *Q = (LinkQueue *)malloc(sizeof(LinkQueue));
        Q->front = Q->rear = (QNode *)malloc(sizeof(QNode));
        Q->front->next = NULL;
        Q->size = 0;
        printf("空队列构造成功！\n");
        return Q;
    }
    //销毁
    void Destory_Queue(LinkQueue *Q)
    {
        if(Q == NULL)
        {
            printf("\n队列为空！\n");
            return;
        }
        while(Q->front)
        {
            Q->rear = Q->front->next;
            free(Q->front);
            Q->front = Q->rear;
            Q->size--;
        }
        free(Q);
        printf("\n队列销毁成功！\n");
    }
    //清空队列
    void Clear_Queue(LinkQueue *Q)
    {
        if(IsEmpty_Queue(Q))
        {
            printf("\n队列为空，不需要进行清空！\n");
            return;
        }
         while(Q->front)
        {
            Q->rear = Q->front->next;
            free(Q->front);
            Q->front = Q->rear;
            Q->size--;
        }
        printf("\n队列清空成功！\n");
    }
    //是否为空
    int IsEmpty_Queue(LinkQueue *Q)
    {
        if(Q->size == 0)
            return TURE;
        else
            return  FALSE;
    }
    //队列的长度
    int Length_Queue(LinkQueue *Q)
    {
        return  Q->size;
    }
    //获得队头元素
    ElemType GetHead_Queue(LinkQueue *Q)
    {
        return Q->front->next->data;
    }
    //插入
    void Enter_Queue(LinkQueue *Q,ElemType e)
    {
        if(!Q)
        {
            printf("队列不存在，请初始化一个队！\n");
            return;
        }
        QNode *current = (QNode *)malloc(sizeof(QNode));
        current->data = e;
        current ->next = NULL;
        Q->rear->next = current;
        Q->rear = current;
        Q->size++;
    }
    //删除
    void Delete_Queue(LinkQueue *Q)
    {
        if(IsEmpty_Queue(Q))
        {
            printf("\n队为空！\n");
            return;
        }
        QNode *current = Q->front->next;
        Q->front->next = current->next;
        if(Q->rear == current)
            Q->rear = Q->front;
        free(current);
        Q->size--;
    }
    //遍历
    void Traverse_Queue(LinkQueue *Q)
    {
        if(IsEmpty_Queue(Q))
        {
            printf("\n队列为空！\n");
            return;
        }
        QNode *current = Q->front->next;
        int i;
        for(i = 0; i < Q->size; i++)
        {
            printf("%d\t",current ->data);
            current = current->next;
        }
        printf("\n队列遍历成功！\n");
    }

**主函数main**

#include<stdio.h>
    #include<stdlib.h>
    
    #include"LinkQueue.h"
    
    void test()
    {
        LinkQueue *Q = Init_Queue();
        int i;
        for(i = 0;i < 5;i++)
        {
            Enter_Queue(Q,i);
        }
        Traverse_Queue(Q);
        Delete_Queue(Q);
        Traverse_Queue(Q);
        printf("当前的队头元素是：%d\n",GetHead_Queue(Q));
        printf("当前队列的长度是：%d\n",Length_Queue(Q));
        //Clear_Queue(Q);
        Destory_Queue(Q);
        printf("当前的队头元素是：%d\n",GetHead_Queue(Q));
        printf("当前队列的长度是：%d\n",Length_Queue(Q));
    
    }
    int main()
    {
        test();
        system("pause");
        return 0;
    }