数据结构：链表队列的实现

快速开始

　　队列是一种和栈相反的，遵循先进先出原则的线性表。此文章使用链表来实现队列。

　　如上图所示，就像一个自来水管，先进入水管的水先从水龙头出来，即Front位置的元素最先出队列，因为它们是最先入队列的。

2、实现队列

　　本代码是严蔚敏教授的数据结构书上面的伪代码的C语言实现代码。

　　一定要多思考，多问为什么！

　　首先我们定义了一些常量：

#include <stdio.h>

#include <stdlib.h>

#define OK 1

#define ERROR 0

typedef int QElemtype;

typedef int status;

2.1、对队列和节点的结构定义

　　既然底层是链表，那么每个节点不仅要保存当前值，还要指向下一个节点的地址。

　　对于队列来说，每次插入值都是在队尾（rear），每次取出值都是在队首（head），所以，我们一定是有两个变量来指向队头与队尾的。

　　综上所述，我们结构定义代码如下：

typedef struct QNode //对节点的结构定义

{

    QElemtype data;

    struct QNode *next;

}QNode,*QueuePtr;

typedef struct{     //对队列的结构定义

    QueuePtr head;

    QueuePtr rear;

}LinkQueue;

2.2、队列初始化

　　初始化主要是对为队列中的两个重要节点分配空间，这里我们需要注意的是初始化时头指针和尾指针指向同一个节点。

　　代码如下：

status initQueue(LinkQueue* que) //初始化队列

{

    que->head=que->rear=(QueuePtr)malloc(sizeof(QNode));

    if(!que->head)  //这段代码对队列里面的用户自定义数据类型进行了初始化

        return ERROR;

    return OK;

}

2.3、入队操作

　　一定要搞清指针的概念。

　　首先rear和head指向同一个元素。然后，我们使rear的next指向新元素，这样rear指向的元素（即1）的next就是新元素了。最后，我们让rear指向新元素。这样一个入队操作就完成了。

　　代码如下：

status enQueue(LinkQueue* que,QElemtype e)

{

    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));

    if(!p) //若未能申请到空间，便退出

        return ERROR;

    p->data=e;

    p->next=NULL;

    que->rear->next = p;

    que->rear=p;

    return OK;

}

2.4、出队操作

　　我们来思考这个过程，在下图队列中，我们出队的第一个元素是元素A，不是1。（因为1不是插入进来了的，而是我们初始化时就有的）。我们首先让*t等于head的next，即元素A。然后修改head的next指向为元素A的next。

这样head的next就会指向元素B。出队操作就完成了。

　　代码如下：

status delQueue(LinkQueue* que,QElemtype *t)

{

    if(que->rear==que->head)

        return ERROR; //队列为空

    QueuePtr p = que->head->next;

    *t=p->data;

    que->head->next=p->next;

    if(que->rear==p) //这个判断是 确保在清空队列的时候，让rear指针归位。

        que->rear=que->head;

    free(p);

    return OK;

}

2.5、回收队列

　　回收可以快速取消队列，方法是让头尾碰面即可。

status destoryQueue(LinkQueue* que) //回收队列

{

    if(que->head)

    {

        que->rear = que->head->next;

        free(que->head);

        que->head=que->rear;

    }

    return OK;

}

2.6、遍历队列和测试方法

　　提供一个简单的方法来测试链表队列。

status viewQueue(LinkQueue* que)

{

    if(que->rear == que->head)

        return ERROR;

    QueuePtr p =que->head->next;

    while(p)

    {

        printf("val:%d",p->data);

        p=p->next;

    }

    return OK;

}

int main(int argc, char **argv)

{

    LinkQueue myQueue;

    initQueue(&myQueue);

    for(int i=1;i<=5;i++)

        enQueue(&myQueue,i);

    viewQueue(&myQueue);

    QElemtype a;

    for(int i=0;i<5;i++)

    {

        delQueue(&myQueue,&a);

        printf("%d\n",a);

    }

    destoryQueue(&myQueue);

    printf("fuck !");

    return 0;

}

巴特西

数据结构：C_链表队列的实现

数据结构：链表队列的实现

快速开始

2、实现队列

2.1、对队列和节点的结构定义

2.2、队列初始化

2.3、入队操作

2.4、出队操作

2.5、回收队列

2.6、遍历队列和测试方法

最新文章

热门文章