Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1727636
  • 博文数量: 782
  • 博客积分: 2455
  • 博客等级: 大尉
  • 技术积分: 4140
  • 用 户 组: 普通用户
  • 注册时间: 2011-04-06 21:37
个人简介

Linux ,c/c++, web,前端,php,js

文章分类

全部博文(782)

文章存档

2015年(8)

2014年(28)

2013年(110)

2012年(307)

2011年(329)

分类:

2011-12-27 09:16:30

原文地址:C语言链队列的实现 作者:renjian2011

未测
  1. /*
  2.  * An implement of Queue data structure.
  3.  * 一个链队列的实现方式来说,基本问题是如何判空。
  4.  * 即认定front==rear时队列为空还是有一个结点;
  5.  * 也就是带不带头结点。
  6.  * 不带头结点,则(NULL==front && NULL==rear)为空
  7.  * 带头结点, 则(front==rear)就是空了。
  8. */

  9. #ifndef Queue_H
  10. #define Queue_H
  11. /*---------------------------*/
  12. #include <stdio.h>
  13. #include <malloc.h>
  14. #include <assert.h>

  15. #define ERROR -1
  16. #define OK 1
  17. #define elem_t int

  18. #define WITH_HEAD_OF_FRONT

  19. /*
  20.  * Queue: |--------------------------|
  21.  * front: ...some nodes... rear:
  22.  * |data| |data|
  23.  * |next| |next|
  24.  * front is a node, rear is another if Queue not empty.
  25.  */

  26. typedef struct node_q
  27. {
  28.     elem_t data;
  29.     struct node_q *next;
  30. }QNode;

  31. typedef struct
  32. {
  33.     QNode *front;
  34.     QNode *rear;
  35.     int size;
  36. }Queue;

  37. Queue* InitQueue()
  38. {
  39.     Queue *pQ = (Queue *)malloc(sizeof(Queue));
  40.     if(!pQ) exit(ERROR);
  41. #ifdef WITH_HEAD_OF_FRONT
  42.     pQ->front = pQ->rear = (QNode *)malloc( sizeof(QNode) );
  43.     if(!pQ->front)
  44.         exit(ERROR);
  45.     pQ->front->next = NULL;
  46. #else
  47.     pQ->front = pQ->rear = NULL;
  48. #endif
  49.     pQ->size = 0;
  50.     return pQ;
  51. }

  52. int QueueEmpty(Queue *pQueue)
  53. {
  54. #ifdef WITH_HEAD_OF_FRONT
  55.     if( pQueue->front == pQueue->rear )
  56. #else
  57.     if(NULL == pQueue->front && NULL == pQueue->rear)
  58. #endif
  59.      return 1;
  60.     return 0;
  61. }

  62. int EnQueue(Queue *pQueue, elem_t e)
  63. {
  64.     QNode *p = (QNode)malloc(sizeof(QNode));
  65.     if(!p) exit(ERROR);
  66.     p->data = e;
  67.     p->next = NULL;
  68.     pQueue->rear->next = p;
  69.     pQueue->rear = p;
  70.     pQueue->size++;
  71.     printf("%d: %c ", pQueue->size, (char)e);
  72.     return OK;
  73. }

  74. /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
  75. int DeQueue(Queue *pQueue, elem_t *e)
  76. {
  77.     assert(pQueue);
  78.     QNode *pnode;
  79. #ifdef WITH_HEAD_OF_FRONT
  80.     if(pQueue->front == pQueue->rear)//QueueEmptry
  81.         return ERROR;
  82.     pnode = pQueue->front->next;//first node after head
  83.     if(e != NULL) *e = p->data;
  84.     // try to delete pnode
  85.     pQueue->front->next = pnode->next;// pnode became "another head"
  86.     // front is actually head, so we leave it alone, change rear if empty
  87.     if(pnode == pQueue->rear ) // seems to be Empty, so
  88.         pQueue->rear = pQueue->front; //make it empty.
  89.     free(pnode);
  90. #else
  91.     pnode = pQueue->front;
  92.     if(QueueEmpty(pQueue) || NULL == pnode)
  93.     return ERROR;
  94.     
  95.     if(e != NULL)
  96.         *e = pnode->data;
  97.     pQueue->size--;
  98.     pQueue->front = pnode->next; //may be null
  99.     free(pnode);
  100.     if(pQueue->front == pQueue->rear) //Empty, and to make sure it's empty
  101.     {
  102.         pQueue->rear = NULL;
  103.         pQueue->size = 0;
  104.     }
  105. #endif
  106.     return OK;
  107. }

  108. void DestroyQueue(Queue *pQueue)
  109. {
  110.     assert(pQueue);
  111. #ifdef WITH_HEAD_OF_FRONT
  112.     while(pQueue->front)
  113.     {
  114.     // use rear as temp to delete node
  115.         pQueue->rear = pQueue->front->next;
  116.         free(pQueue->front);
  117.         pQueue->front = pQueue->rear;
  118.     }
  119. #else
  120.     while(QueueEmpty(pQueue))
  121.     {
  122.         DeQueue(pQueue, NULL);
  123.     }
  124.     // free the Queue itself
  125.     free(pQueue);
  126. #endif
  127. }

  128. int QueueLength(Queue *pQ)
  129. {
  130.     int i = 0;
  131. #ifdef WITH_HEAD_OF_FRONT
  132.     QNode *ptmp = pQ->front;
  133.     while(ptmp != pQ->rear)
  134.     {
  135.         ++i;
  136.         ptmp = ptmp->next;
  137.     }
  138.     return i;
  139. #else
  140.     return pQ->size;
  141. #endif
  142.     
  143. }

  144. int getFront(Queue *pQ, elem_t *e)
  145. {
  146. //both WITH_HEAD_OF_FRONT or not is OK
  147.     assert(pQ);
  148.     if( ! QueueEmpty(pQ) )
  149.         return -1;
  150.     *e = pQ->front->data;
  151.     return OK;
  152. }

  153. // Test
  154. int main()
  155. {
  156.     int i, item;
  157.     Queue * pTestQ = InitQueue();
  158.     printf("ABCD...EnQueue:\n");
  159.     for(i = 'A'+0; i <= 'K'+0; ++i)
  160.     {
  161.         EnQueue(pTestQ, i);
  162.     }
  163.     printf("\nABCD...DeQueue:\n");
  164.     for(i = 'A'+0; i <= 'K'+0; ++i)
  165.     {
  166.         DeQueue(pTestQ, &item);
  167.         printf("%c ", (char)item);
  168.     }
  169.     DestroyQueue(pTestQ);
  170. }

  171. /*----------------------------*/
  172. #endif
阅读(691) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~