C严蔚敏数据结构-链队

末蓝、 2022-03-24 14:38 243阅读 0赞

## 链队的初始化 ##

>  *  **生成新节点作为头节点，队头和队尾指向此节点**
>  *  **头节点的指针域置空**

Status InitQueue(LinkQueue &q)
    {
        q.front = q.rear = (Queue*)malloc(sizeof(Queue));   //生成新节点作为头节点，队头和队尾指向此节点
        q.front->next = NULL;               //头结点指针域置空
        return OK;
    }

## **链队的入队** ##

>  *  **为入队元素申请堆空间，用指针p指向**
>  *  **将新节点数据域置为e**
>  *  **将新节点插入到队尾**
>  *  **修改队尾指针为p**

Status EnQueue(LinkQueue &q,ElemType e)
    {
        Queue *p = (Queue*)malloc(sizeof(Queue));   //为入队元素申请堆空间，用p节点指向
        p->data = e;            //将新节点的数据域置为e
        p->next = NULL;         //新节点的的指针域置空
        q.rear->next = p;       //新节点插入到表尾
        q.rear = p;             //修改表尾指针
        return OK;
    }

## 链队的出队 ##

>  *  **判断队列是否为空，若空则返回ERROR**
>  *  **临时保存队头元素的空间，以备释放**
>  *  **修改头节点的指针域，指向下一个节点**
>  *  **判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值，指向头节点**
>  *  **释放原队头元素的空间**

Status DeQueue(LinkQueue &q,ElemType &e)
    {
        Queue *p = q.front->next;   //定义指针p,指向队列的第一个节点
        if(q.front == q.rear)       //如果q.front == q.rear ，则队列为空
            return ERROR;
        e = p->data;                //返回删除队头元素的值
        q.front->next = p->next;    //队头节点指针域指向待删除节点的下一个节点
        if(q.rear == p)             //如果最后一个元素被删除，队尾指针指向队头指针
            q.rear = q.front;
        free(p);                    //释放原队头元素的节点空间
        return OK;
    }

## 取队头元素 ##

> **与循环队列一样，当队列非空时，此操作返回当前队头元素的值，队头指针保持不变**

Status GetHead(LinkQueue q,ElemType &e)
    {
        if(q.front!=q.rear)
        {
            e = q.front->next->data;
        }
        else return ERROR;
        return OK;
    }

#include <stdio.h>
    #include <stdlib.h>
    #define ERROR 0
    #define OK 1
    typedef int ElemType;
    typedef int Status;
    typedef struct queue
    {
        ElemType data;
        struct queue *next;
    } Queue,*QueuePtr;
    typedef struct
    {
        QueuePtr front;
        QueuePtr rear;
    } LinkQueue;
    Status InitQueue(LinkQueue &q);
    Status EnQueue(LinkQueue &q,ElemType e);
    Status DeQueue(LinkQueue &q,ElemType &e);
    Status GetHead(LinkQueue q,ElemType &e);
    void QueuePrintf(LinkQueue q);
    int main()
    {
        LinkQueue q;
        char c;
        int n;
        int a[] = {1,2,3,4,5};
        InitQueue(q);
        for(int i=0; i<5; i++)
        {
            EnQueue(q,a[i]);
        }
        printf("当前链队为:\n");
        QueuePrintf(q);
        while(true)
        {
            printf("请输入你想要执行的操作:\n1.元素入队\n2.元素出队\n3.取队头元素\n4.打印链队\n5.退出程序\n");
            scanf(" %c",&c);
            if(c=='1')
            {
                printf("请输入入队元素:\n");
                scanf("%d",&n);
                EnQueue(q,n);
                QueuePrintf(q);
            }
            else if(c=='2')
            {
                if(DeQueue(q,n))
                {
                    printf("删除的元素为:%d\n",n);
                    QueuePrintf(q);
                }
                else
                {
                    printf("队列已空!\n");
                }
            }
            else if(c=='3')
            {
                if(GetHead(q,n))
                {
                    printf("队头元素为:%d\n",n);
                }
                else
                {
                    printf("队列为空!\n");
                }
            }
            else if(c=='4')
            {
                QueuePrintf(q);
            }
            else
            {
                exit(0);
            }
        }
    }
    Status InitQueue(LinkQueue &q)
    {
        q.front = q.rear = (Queue*)malloc(sizeof(Queue));   //生成新节点作为头节点，队头和队尾指向此节点
        q.front->next = NULL;               //头结点指针域置空
        return OK;
    }
    Status EnQueue(LinkQueue &q,ElemType e)
    {
        Queue *p = (Queue*)malloc(sizeof(Queue));   //为入队元素申请堆空间，用p节点指向
        p->data = e;            //将新节点的数据域置为e
        p->next = NULL;         //新节点的的指针域置空
        q.rear->next = p;       //新节点插入到表尾
        q.rear = p;             //修改表尾指针
        return OK;
    }
    Status DeQueue(LinkQueue &q,ElemType &e)
    {
        Queue *p = q.front->next;   //定义指针p,指向队列的第一个节点
        if(q.front == q.rear)       //如果q.front == q.rear ，则队列为空
            return ERROR;
        e = p->data;                //返回删除队头元素的值
        q.front->next = p->next;    //队头节点指针域指向待删除节点的下一个节点
        if(q.rear == p)             //如果最后一个元素被删除，队尾指针指向队头指针
            q.rear = q.front;
        free(p);                    //释放原队头元素的节点空间
        return OK;
    }
    Status GetHead(LinkQueue q,ElemType &e)
    {
        if(q.front!=q.rear)
        {
            e = q.front->next->data;
        }
        else return ERROR;
        return OK;
    }
    void QueuePrintf(LinkQueue q)   //打印队列
    {
        Queue *p = q.front->next;
        while(p)                    //当p为空时循环终止
        {
            printf("%d\t",p->data);
            p = p->next;
        }
        printf("\n");
    }