Chinaunix首页 | 论坛 | 博客

oops

首页　| 　博文目录　| 　关于我

王贤才

  • 博客访问： 1064469
  • 博文数量： 573
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 66
  • 用 户 组： 普通用户
  • 注册时间： 2016-06-28 16:21
文章分类

全部博文（573）

文章存档

2018年（3）

2016年（48）

2015年（522）

我的朋友
最近访客
推荐博文
相关博文
顺序队列

分类： C/C++

2015-12-02 14:50:38


点击(此处)折叠或打开

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

  5. #define MAXQSIZE 10
  6. #define QINCREASESZIE 5
  7. #define STRINGSIZE 128

  9. typedef char STRING[STRINGSIZE];

  11. /*定义顺序队列的结构体:描述了队列的所有要素*/
  12. typedef struct queue
  13. {
  14.     STRING * base; /*队列中元素的指针，永远指向开辟的第一个空间的首地址*/
  15.     int front; /*队首指针:类似数组的下标值*/
  16.     int rear; /*对尾指针:类似数组的下标值*/
  17.     int queuesize; /*队列的容量*/
  18. }QUEUE;

  20. typedef QUEUE * queueptr;

  22. int InitQueue(QUEUE * queue);
  23. int QueueLen(QUEUE queue);
  24. int EnQueue(QUEUE * queue, STRING string);
  25. int DeQueue(QUEUE * queue, STRING string);
  26. int PrintQueue(QUEUE queue);
  27. int DestroyQueue(QUEUE * queue);
  28. int ClearQueue(QUEUE * queue);
  29. int QueueIsEmpty(QUEUE queue);
  30. int GetQueueHead(QUEUE queue, STRING string);

  32. int main(int argc, char ** argv)
  33. {
  34.     
  35.     printf("循环队列的顺序存储结构！\n");
  36.     
  37.     printf("111**************************************************************\n");
  38.     QUEUE queue;
  39.     InitQueue(&queue);
  40.     int flag = -1;
  41.     flag = QueueIsEmpty(queue);
  42.     if(flag == 1)
  43.         printf("空队列！\n");
  44.     else if(flag == 2)
  45.         printf("非空队列！\n");
  46.     
  47.     STRING string;
  48.     
  49.     memset(string, 0, sizeof(STRINGSIZE));
  50.     strcpy(string, "AAA");
  51.     EnQueue(&queue, string);
  52.     
  53.     flag = QueueIsEmpty(queue);
  54.     if(flag == 1)
  55.         printf("空队列！\n");
  56.     else if(flag == 2)
  57.         printf("非空队列！\n");
  58.     
  59.     memset(string, 0, sizeof(STRINGSIZE));
  60.     strcpy(string, "BBB");
  61.     EnQueue(&queue, string);
  62.     memset(string, 0, sizeof(STRINGSIZE));
  63.     strcpy(string, "CCC");
  64.     EnQueue(&queue, string);
  65.     memset(string, 0, sizeof(STRINGSIZE));
  66.     strcpy(string, "DDD");
  67.     EnQueue(&queue, string);
  68.     memset(string, 0, sizeof(STRINGSIZE));
  69.     strcpy(string, "EEE");
  70.     EnQueue(&queue, string);
  71.     memset(string, 0, sizeof(STRINGSIZE));
  72.     strcpy(string, "FFF");
  73.     EnQueue(&queue, string);
  74.     memset(string, 0, sizeof(STRINGSIZE));
  75.     strcpy(string, "GGG");
  76.     EnQueue(&queue, string);
  77.     memset(string, 0, sizeof(STRINGSIZE));
  78.     strcpy(string, "HHH");
  79.     EnQueue(&queue, string);
  80.     memset(string, 0, sizeof(STRINGSIZE));
  81.     strcpy(string, "III");
  82.     EnQueue(&queue, string);
  83.     printf("222**************************************************************\n");
  84.     PrintQueue(queue);
  85.     
  86.     memset(string, 0, sizeof(STRINGSIZE));
  87.     strcpy(string, "JJJ");
  88.     EnQueue(&queue, string);
  89.     printf("333**************************************************************\n");
  90.     PrintQueue(queue);
  91.     
  92.     memset(string, 0, sizeof(STRINGSIZE));
  93.     GetQueueHead(queue, string);
  94.     printf("取得的队首元素=[%s]\n", string);
  95.     
  96.     memset(string, 0, sizeof(STRINGSIZE));
  97.     strcpy(string, "KKK");
  98.     EnQueue(&queue, string);
  99.     memset(string, 0, sizeof(STRINGSIZE));
  100.     strcpy(string, "LLL");
  101.     EnQueue(&queue, string);
  102.     memset(string, 0, sizeof(STRINGSIZE));
  103.     strcpy(string, "MMM");
  104.     EnQueue(&queue, string);
  105.     memset(string, 0, sizeof(STRINGSIZE));
  106.     strcpy(string, "NNN");
  107.     EnQueue(&queue, string);
  108.     memset(string, 0, sizeof(STRINGSIZE));
  109.     strcpy(string, "OOO");
  110.     EnQueue(&queue, string);
  111.     memset(string, 0, sizeof(STRINGSIZE));
  112.     strcpy(string, "PPP");
  113.     EnQueue(&queue, string);
  114.     printf("444**************************************************************\n");
  115.     PrintQueue(queue);
  116.     
  117.     memset(string, 0, sizeof(STRINGSIZE));
  118.     DeQueue(&queue, string);
  119.     printf("出队的元素1=[%s]\n", string);
  120.     memset(string, 0, sizeof(STRINGSIZE));
  121.     DeQueue(&queue, string);
  122.     printf("出队的元素2=[%s]\n", string);
  123.     printf("555**************************************************************\n");
  124.     PrintQueue(queue);
  125.     
  126.     memset(string, 0, sizeof(STRINGSIZE));
  127.     DeQueue(&queue, string);
  128.     memset(string, 0, sizeof(STRINGSIZE));
  129.     DeQueue(&queue, string);
  130.     memset(string, 0, sizeof(STRINGSIZE));
  131.     DeQueue(&queue, string);
  132.     memset(string, 0, sizeof(STRINGSIZE));
  133.     DeQueue(&queue, string);
  134.     memset(string, 0, sizeof(STRINGSIZE));
  135.     DeQueue(&queue, string);
  136.     memset(string, 0, sizeof(STRINGSIZE));
  137.     DeQueue(&queue, string);
  138.     memset(string, 0, sizeof(STRINGSIZE));
  139.     DeQueue(&queue, string);
  140.     memset(string, 0, sizeof(STRINGSIZE));
  141.     DeQueue(&queue, string);
  142.     memset(string, 0, sizeof(STRINGSIZE));
  143.     DeQueue(&queue, string);
  144.     memset(string, 0, sizeof(STRINGSIZE));
  145.     DeQueue(&queue, string);
  146.     memset(string, 0, sizeof(STRINGSIZE));
  147.     DeQueue(&queue, string);
  148.     memset(string, 0, sizeof(STRINGSIZE));
  149.     DeQueue(&queue, string);
  150.     memset(string, 0, sizeof(STRINGSIZE));
  151.     DeQueue(&queue, string);
  152.     memset(string, 0, sizeof(STRINGSIZE));
  153.     DeQueue(&queue, string);
  154.     memset(string, 0, sizeof(STRINGSIZE));
  155.     DeQueue(&queue, string);
  156.     memset(string, 0, sizeof(STRINGSIZE));
  157.     DeQueue(&queue, string);
  158.     flag = QueueIsEmpty(queue);
  159.     if(flag == 1)
  160.         printf("空队列！\n");
  161.     else if(flag == 2)
  162.         printf("非空队列！\n");
  163.     
  164.     return 0;
  165. }

  167. /*功能：初始化队列*/
  168. int InitQueue(QUEUE * queue)
  169. {
  170.     queue->base = (STRING *)malloc(MAXQSIZE * sizeof(STRING));
  171.     if(queue->base == NULL)
  172.     {
  173.         printf("InitQueue malloc err! 退出程序!\n");
  174.         exit(-1);
  175.     }
  176.     queue->front = queue->rear = 0;
  177.     queue->queuesize = MAXQSIZE;
  178.     
  179.     return 0;
  180. }

  182. /*功能：入队:从队列尾插入一个元素*/
  183. int EnQueue(QUEUE * queue, STRING string)
  184. {
  185.     /*这里判断队列满时：牺牲了一个元素的存储空间,所以当入队第10个元素时，就会增加存储空间*/
  186.     if((queue->rear + 1) % queue->queuesize == queue->front) /*队列满，要重新调整空间*/
  187.     {
  188.         queue->base = (STRING *)realloc(queue->base, (MAXQSIZE + QINCREASESZIE) * sizeof(STRING));
  189.         if(queue->base == NULL)
  190.         {
  191.             printf("EnQueue realloc err! 退出程序!\n");
  192.             exit(-1);
  193.         }
  194.         queue->queuesize = queue->queuesize + QINCREASESZIE;
  195.     }
  196.     strcpy(*(queue->base + queue->rear), string); /*插入string元素*/
  197.     queue->rear = (queue->rear + 1) % queue->queuesize; /*入队：队尾指针加1，插入后，若队列满了，则rear从头开始指向*/
  198.     printf("入队一个元素=[%s],队列空间大小=[%d],队列中元素个数=[%d]\n", string, queue->queuesize, QueueLen(*queue));
  199.     
  200.     return 0;
  201. }

  203. /*功能：出队：从队列头删除一个元素*/
  204. int DeQueue(QUEUE * queue, STRING string)
  205. {
  206.     if(queue->front == queue->rear)
  207.     {
  208.         printf("队列为空，无元素可出队列！\n");
  209.         return -1;
  210.     }
  211.     strcpy(string, *(queue->base + queue->front));
  212.     queue->front = (queue->front + 1) % queue->queuesize;
  213.     printf("出队一个元素=[%s],队列空间大小=[%d],队列中剩余元素个数=[%d]\n", string, queue->queuesize, QueueLen(*queue));
  214.     
  215.     return 0;
  216. }

  218. /*功能：求队列中所有元素的个数*/
  219. int QueueLen(QUEUE queue)
  220. {
  221.     int len = 0;
  222.     len = (queue.rear - queue.front + queue.queuesize) % queue.queuesize;
  223.     /*
  224.     while(queue.front != queue.rear)
  225.     {
  226.         len++;
  227.         queue.front = (queue.front + 1) % queue.queuesize; //对头指针前移
  228.     }
  229.     */
  230.     return len;
  231. }

  233. /*功能：打印队列中的所有元素*/
  234. int PrintQueue(QUEUE queue)
  235. {
  236.     STRING string;
  237.     int i = 0;
  238.     printf("循环队列空间大小=[%d], 队列中的元素个数=[%d]\n", queue.queuesize, QueueLen(queue));
  239.     printf("从队列头开始；\n");
  240.     while(queue.front != queue.rear)
  241.     {
  242.         i++;
  243.         memset(string, 0 ,sizeof(string));
  244.         strcpy(string, *(queue.base + queue.front));
  245.         printf("(第%d个元素)=[%s]，", i, string);
  246.         queue.front = (queue.front + 1) % queue.queuesize; /*对头指针前移*/
  247.     }
  248.     printf("\n");
  249.     
  250.     return 0;
  251. }

  253. /*功能：销毁队列*/
  254. int DestroyQueue(QUEUE * queue)
  255. {
  256.     free(queue->base);
  257.     queue->base = NULL;
  258.     queue->front = 0;
  259.     queue->rear = 0;
  260.     queue->queuesize = 0;
  261.     printf("循环顺序队列已销毁！\n");
  262.     
  263.     return 0;
  264. }

  266. /*功能：将队列中元素清空,变为空队列（队列还在，不是销毁队列）*/
  267. int ClearQueue(QUEUE * queue)
  268. {
  269.     memset(*(queue->base), 0, queue->queuesize);
  270.     queue->front = queue->rear = queue->queuesize = 0;
  271.     printf("循环顺序队列已清空！\n");
  272.     
  273.     return 0;
  274. }

  276. /*功能：判断队列是否是空队列：1：空队列，2：非空队列*/
  277. int QueueIsEmpty(QUEUE queue)
  278. {
  279.     if(queue.front == queue.rear) /*空队列*/
  280.         return 1;
  281.     else
  282.         return 2;
  283. }

  285. /*功能：取得队列头元素，并不移动队列头指针*/
  286. int GetQueueHead(QUEUE queue, STRING string)
  287. {
  288.     if(queue.front == queue.rear)
  289.     {
  290.         printf("队列为空，无队列头元素可出队列！\n");
  291.         return -1;
  292.     }
  293.     strcpy(string, *(queue.base + queue.front));
  294.     return 0;
  295. }

阅读(658) | 评论(0) | 转发(0) |
0

上一篇：链式队列

下一篇：链式栈

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6