Chinaunix首页 | 论坛 | 博客
  • 博客访问: 230961
  • 博文数量: 127
  • 博客积分: 34
  • 博客等级: 民兵
  • 技术积分: 655
  • 用 户 组: 普通用户
  • 注册时间: 2012-10-03 10:53
文章分类

全部博文(127)

文章存档

2013年(19)

2012年(108)

分类: C/C++

2013-02-04 21:09:44

原文地址:数据结构之队列 作者:


 
  与栈相反,队列是一种先进先出的线性表,它只允许在表的一端进行,而在另一端删除元

素。

   在队列中,允许插入的一端叫做队尾,允许删除的一端则称为队头。


1、链队列——队列的链式表示和实现

   用链表表示的队列简称为链队列,一个链队列显然需要两个分别指示对头和队尾的指针

(分别称为头指针和尾指针)才能唯一确定。这里,和线性表的单链表一样,为了操作方便起

见,我们也给队列添加一个头结点。

   链队列的操作即为单链表的插入和删除操作的特殊情况,只是尚需修改尾指针或头指针。

   单链队列——队列的链式存储结构,如下所示。

  1. //单链队列,队列的链式存储结构
  2. typedef struct QNode
  3. {
  4.     ElemType data;
  5.     struct QNode *next;
  6. }QNode, *QueuePtr;

  7. typedef struct
  8. {
  9.     QueuePtr front;            //队头指针
  10.     QueuePtr rear;            //队尾指针
  11. }LinkQueue;

2、单链队列的C语言操作

  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. #define ElemType int

  4. #define OK 1
  5. #define ERROR 0


  6. //单链队列,队列的链式存储结构
  7. typedef struct QNode
  8. {
  9.     ElemType data;
  10.     struct QNode *next;
  11. }QNode, *QueuePtr;

  12. typedef struct
  13. {
  14.     QueuePtr front;            //队头指针
  15.     QueuePtr rear;            //队尾指针
  16. }LinkQueue;

  17. //构造一个空队列
  18. int InitQueue(LinkQueue *q)
  19. {
  20.     //
  21.     q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));
  22.     if(q->front == NULL)
  23.     {
  24.         fprintf(stderr, "malloc() error.\n");
  25.         return ERROR;
  26.     }

  27.     q->front->next = NULL;
  28.     q->rear->next = NULL;

  29.     return OK;
  30. }

  31. //销毁队列,Q不在存在
  32. int DestroyQueue(LinkQueue *q)
  33. {
  34.     //
  35.     while(q->front)
  36.     {
  37.         q->rear = q->front->next;
  38.         free(q->front);
  39.         q->front = q->rear;
  40.     }
  41.     return OK;
  42. }

  43. //判断队列是否为空
  44. int IsEmptyQueue(LinkQueue *q)
  45. {
  46.     return (q->front->next == NULL && q->rear->next == NULL);
  47. }

  48. //插入元素e为新的队尾元素
  49. int InsertQueue(LinkQueue *q, ElemType e)
  50. {
  51.     //
  52.     QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
  53.     if(p == NULL)
  54.     {
  55.         fprintf(stderr, "malloc() error.\n");
  56.         return ERROR;
  57.     }
  58.     
  59.     p->data = e;
  60.     p->next = NULL;
  61.     
  62.     //如果队列为空
  63.     if(IsEmptyQueue(q))
  64.     {
  65.         q->front->next = p;
  66.         q->rear = p;
  67.     }
  68.     else
  69.     {
  70.         q->rear->next = p;
  71.         q->rear = p;            //不要忘记这句啊
  72.     }
  73.     return OK;
  74. }

  75. //若队列不空,则删除队头元素,用e返回其值,并返回OK
  76. int DeQueue(LinkQueue *q, ElemType *e)
  77. {
  78.     //
  79.     if(IsEmptyQueue(q))
  80.     {
  81.         fprintf(stdout, "the queue is null.\n");
  82.         return ERROR;
  83.     }

  84.     //注意有队头结点
  85.     QueuePtr temp;
  86.     temp = q->front->next;
  87.     *e = temp->data;

  88.     q->front->next = temp->next;

  89.     //一个元素
  90.     if(q->rear == temp)
  91.     {
  92.         q->rear = q->front;
  93.     }

  94.     free(temp);

  95.     return OK;
  96. }

  97. //打印队列
  98. void printQueue(LinkQueue *q)
  99. {
  100.     QueuePtr temp;
  101.     temp = q->front->next;

  102.     while(temp != NULL)
  103.     {
  104.         printf("%d ", temp->data);
  105.         temp = temp->next;
  106.     }

  107. }

  108. int main(int argc, char **argv)
  109. {
  110.     LinkQueue *q;
  111.     InitQueue(q);

  112.     srand(time(NULL));

  113.     int i = 0;
  114.     for(i = 0; i < 10; i++)
  115.     {
  116.         InsertQueue(q, i);
  117.     }

  118.     printf("插入队列的元素为:\n");
  119.     printQueue(q);

  120.     int e;
  121.     DeQueue(q, &e);
  122.     printf("队头元素为: %d\n", e);

  123.     return 0;
  124. }

3、循环队列定义

   单链队列时,当队列为空时,front等于rear,现在循环队列当队列满时,也是front等

rear,那么如何判断此时的队列究竟是空还是满呢?

   办法一是设置一个标志变量flag,当front == rear,且flag = 0时为队列空,当front 

==rear,且flag = 1时为队列满;

   办法二是当队列空时,条件就是front == rear,当队列为满时,我们修改其条件,保留一

个元素空间。也就是说,队列满时,数组中还有一个空闲单元。例如下图所示,我们就认为此

队列已经满了,也就是说,我们不允许下图中的右图情况出现。

   我们重点来讨论第二种方法,由于rear可能比front大,也可能比front小,所以,尽管它

们只相差一个位置时就说满的情况,但也有可能是相差整整一圈。所以,若队列的最大尺寸为

QueueSize,那么队列满的条件是(rear + 1) % QueueSize == front(取模"%"的目的就说为

了整合rear与front大小为一个问题)。比如上面这个例子,QueueSzie = 5,上图中的左图中

front = 0,而rear = 4,(4 + 1) % 5 = 0,所以,此时队列满。再看右图,front = 2, 

而rear = 1,(1 + 1) %5 = 2,所以,此时队列也是满的。但是也有例外的情况。

   另外,通用的计算队列长度的公式为:(rear - front + QueueSize) % QueueSize

   循环队列的顺序存储结构,如下所示。

  1. #define ElemType int 

  2. typedef struct
  3. {
  4.     ElemType data[MAXSIZE];
  5.     int front; //头指针
  6.     int rear; //尾指针,若队列不为空时,rear指向队列尾元素的下一个位置
  7. }SqQueue;



4、循环队列的C操作

  1. #define ElemType int

  2. #define MAXSIZE 100

  3. typedef struct
  4. {
  5.     ElemType data[MAXSIZE];
  6.     int front;                //头指针
  7.     int rear;                //尾指针,若队列不为空时,rear指向队列尾元素的下一个位置
  8. }SqQueue;


  9. #define OK     1
  10. #define ERROR 0
  11. //初始化一个空队列
  12. int InitQueue(SqQueue *q)
  13. {
  14.     q->front = 0;
  15.     q->rear = 0;

  16.     return OK;
  17. }

  18. //循环队列求队列长度
  19. //返回队列的元素的个数,也就是队列的当前长度
  20. int QueueLength(SqQueue *q)
  21. {
  22.     return (q->rear - q->front + MAXSIZE) % MAXSIZE;
  23. }

  24. //循环队列的入队操作
  25. //若队列未满,则插入元素e为队列新的队尾元素
  26. int EnQueue(SqQueue *q, ElemType e)
  27. {
  28.     if((q->rear + 1) % MAXSIZE == q->front)    //队列满的判断
  29.     {
  30.         return ERROR;
  31.     }

  32.     q->data[q->rear] = e;                    //将元素e赋值给队尾
  33.     q->rear = (q->rear + 1) MAXSIZE;        //rear指向后移一位置,若到最后则转为数组头部
  34.                                             //注意
  35.     return OK;
  36. }

  37. //循环队列的出对操作
  38. //若队列不空,则删除q中队头元素,用e返回值
  39. int DeQueue(SqQueue *q, ElemType *e)
  40. {
  41.     if(q->rear == q->front)                //队列空的判断
  42.     {
  43.         return ERROR;
  44.     }
  45.     
  46.     *e = q->data[q->front];                //将队头元素赋值给e
  47.     q->front = (q->front + 1) % MAXSIZE;//front指针向后一位置,若到最后,则转到数组头部

  48.     return OK;
  49. }





          参数:严蔚敏老师之《数据结构》、《大话数据结构》


                                                   梦醒潇湘love
                                                 2013-01-12 19:37
阅读(2366) | 评论(0) | 转发(0) |
0

上一篇:数据结构之堆排序

下一篇:数据结构之栈

给主人留下些什么吧!~~