打印

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

[复制链接]
1017|2
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
韩山童|  楼主 | 2017-1-6 10:15 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
上一次我们简单实现了堆栈,这次让我们用C语言实现队列,也就是FIFO。不足之处请大神们指点赐教。再次先行谢过。我本人比较钟爱于链表,如果朋友有需要的话,我会补充队列的数组实现。好了,下面进入正题。
1.首先,我们定义队列的节点数据类型:
typedef int ElemType; //队列中的实际数据

//队列的节点数据类型
typedef struct _Node
{
    ElemType data;
    _Node* next;
}Node,*PNode;


2.队列主要有两个操作:入队和出队。下面分别实现。
(1)入队操作:

void enqueue(PQueue q,ElemType e)
{
    if (NULL == q->Front)//如果队列开始时是空的
    {
        PNode s = (PNode)malloc(sizeof(Node));
        s->data = e;
        s->next = NULL;
        q->Front = s;
        q->Rear = s;
        return;
    }

    //队列非空
    PNode s = (PNode)malloc(sizeof(Node));
    s->data = e;
    q->Rear->next = s;
    s->next = NULL;
    q->Rear = s;

}


这样就实现了入队操作。如果有朋友不熟悉链表,我会后续补充一下。
(2)出队操作:

void dequeue(PQueue q,ElemType ret)
{
    PNode tmp = NULL;
    if (NULL == q->Front)//队列为空的话 直接返回。
    {
        printf("队列已经为空!!!\n");
        return;
    }

    //队列不为空
    tmp = q->Front;   //获取对头节点
    if (q->Front == q->Rear)//如果队列中只有一个节点
    {
        q->Front = q->Rear = NULL;
    }
    else   //队列中由多个元素
    {
         q->Front = q->Front->next;
         ret = tmp->data;
         free(tmp);
         tmp = NULL;  //这一步最好加上,避免野指针
   }
}

3.测试:
(1)输出队列中的元素:
void print(PQueue q)
{
    PNode p = q->Front;
    while (NULL != p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
}


(2)main函数:
#include "Queue.h"
int main()
{
    Queue q={NULL,NULL};
    ElemType e;
    enqueue(&q,1);
    enqueue(&q,2);
    enqueue(&q,3);
    enqueue(&q,4);
    enqueue(&q,5);

    print(&q);

    return 0;
}
输出:1 2 3 4 5
好了,这样,一个简单的队列就实现了。这里只是给出了队列的简单实现,大家可以根据需要去优化一下这个代码。蟹蟹各位的支持!

相关帖子

沙发
Meyeah| | 2017-1-6 18:06 | 只看该作者
咋不用C++实现啊?

使用特权

评论回复
板凳
韩山童|  楼主 | 2017-1-6 18:14 | 只看该作者
Meyeah 发表于 2017-1-6 18:06
咋不用C++实现啊?

该网站用C语言的偏多吧

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

10

主题

43

帖子

1

粉丝