亲宝软件园·资讯

展开

C语言实现数据结构 队列 C利用语言实现数据结构之队列

柳兮 人气:0
想了解C利用语言实现数据结构之队列的相关内容吗,柳兮在本文为您仔细讲解C语言实现数据结构 队列的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C语言,数据结构,队列,下面大家一起来学习吧。

前言:

队列在生活中也比较常见,例如购物排队——新来的成员总是加入队尾,每次离开的成员总是队列头上的。

队列按存储方式可以分为两种:顺序队列和链队列。

一、链队列

链式队列中每个元素定义成一个结点,含数据域与指针域(指向下一结点),并设头尾指针。用图表示就是。

二、链队的表示

前面的链式结构,总是使用一个结点的结构来表示链表,但是在这里使用新的存储结构。定义一个结点结构,和一个队列结构。两个结构嵌套。

//定义节点结构
typedef struct QNode
{
    QElemType   data;   /*数据域*/
    struct QNode   * next;   /*指针域*/
 }QNode, *QueuePtr;
//定义队列结构
 typedef struct
 {
    QueuePtr front;
    QueuePtr rear;
 }LinkQueue;

三、链队的基本操作

1. 链队的初始化

Status initQueue(LinkQueue *Q)
{ 
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->next = NULL;
    return OK;
}

2. 链队的销毁

Status destroyQueue(LinkQueue *Q)
{
    while (Q.front)
    {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
   return OK;
}

3. 入队

Status enQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    //插入数据
    p->data = e;
    p->next = NULL;
    //Q.rear一直指向队尾
    Q.rear->next = p;
    Q.rear = p;
    return OK;
 }

4. 出队

Status deQueue(LinkQueue *Q, QElemType e)
{
    if(Q.front == Q.rear) return ERROR;
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;   //队头元素p出队
    if(Q.rear == p)   //如果队中只有一个元素p, 则p出队后成为空队
    Q.rear = Q.front;     //给队尾指针赋值
    free(p);   //释放存储空间
    return OK;
}

四、顺序队列

用一组连续的存储单元依次存放队列的元素,并设两个指针frontrear分别指示队头和队尾元素的位置。
front:指向实际的队头;rear:指向实际队尾的下一位置。
初态front=rear=0;队空:front=rear;队满:rear=M;
入队q[rear]=x; rear= rear+1; 出队:x=q[front];front=front+1;

顺序队列的表示:

#define MAXQSIZE  100
typedef struct
{
    QElemType *base;
    int  front;   //头指针指示器 
    int  rear;  //尾指针指示器
} SqQueue;

存在的问题:

随着入队、出队操作的进行,整个队列会整体向后移动,这样就出现了下图的现象:队尾指针虽然已经移到了最后,而队列却未真满的“假溢出”现象,使得队列的空间没有得到有效的利用

那我们该如何解决假溢出的问题呢?

有以下两种方法:

五、循环队列

在循环队列中,不可以根据等式front == rear可以判别队满和队空。因为此时条件是相同的,解决这种问题的方法一般有两种。

少用(损失)一个空间,以尾指针加1等于头指针作为队满的标志。因此:当front==rear,表示循环队列为空;当front ==(rear+1)% MAXLEN,表示循环队列为满。
在定义结构体时,附设一个存储循环队列中元素个数的变量n,当n==0时表示队空;当n==MAXLEN时为队满。

循环队列的基本操作:

1. 初始化

Status initQueue (SqQueue *Q)
{
    Q.base=(QElemType *) malloc(MAXQSIZE * sizeof(QElemType));
    if (!Q.base) exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}

2. 求队列长度

int queueLength(SqQueue *Q)
{
    return (Q.rear - Q.front+MAXQSIZE) % MAXQSIZE;
}

3. 入队

Status enQueue (SqQueue *Q, QElemType e)
{
    if((Q.rear+1)%MAXQSIZE == Q.front)  return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear+1) % MAXQSIZE;
    return OK;
}

4. 出队

Status deQueue (SqQueue *Q, QElemType e)
{
    if(Q.front == Q.rear)
    return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front+1)%MAXQSIZE;
    return OK;
}

加载全部内容

相关教程
猜你喜欢
用户评论