Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1058752
  • 博文数量: 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>

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

  7. typedef char STRING[STRINGSIZE];

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

  16. typedef QUEUE * queueptr;

  17. int InitQueue(QUEUE * queue);
  18. int QueueLen(QUEUE queue);
  19. int EnQueue(QUEUE * queue, STRING string);
  20. int DeQueue(QUEUE * queue, STRING string);
  21. int PrintQueue(QUEUE queue);
  22. int DestroyQueue(QUEUE * queue);
  23. int ClearQueue(QUEUE * queue);
  24. int QueueIsEmpty(QUEUE queue);
  25. int GetQueueHead(QUEUE queue, STRING string);

  26. int main(int argc, char ** argv)
  27. {
  28.     
  29.     printf("循环队列的顺序存储结构!\n");
  30.     
  31.     printf("111**************************************************************\n");
  32.     QUEUE queue;
  33.     InitQueue(&queue);
  34.     int flag = -1;
  35.     flag = QueueIsEmpty(queue);
  36.     if(flag == 1)
  37.         printf("空队列!\n");
  38.     else if(flag == 2)
  39.         printf("非空队列!\n");
  40.     
  41.     STRING string;
  42.     
  43.     memset(string, 0, sizeof(STRINGSIZE));
  44.     strcpy(string, "AAA");
  45.     EnQueue(&queue, string);
  46.     
  47.     flag = QueueIsEmpty(queue);
  48.     if(flag == 1)
  49.         printf("空队列!\n");
  50.     else if(flag == 2)
  51.         printf("非空队列!\n");
  52.     
  53.     memset(string, 0, sizeof(STRINGSIZE));
  54.     strcpy(string, "BBB");
  55.     EnQueue(&queue, string);
  56.     memset(string, 0, sizeof(STRINGSIZE));
  57.     strcpy(string, "CCC");
  58.     EnQueue(&queue, string);
  59.     memset(string, 0, sizeof(STRINGSIZE));
  60.     strcpy(string, "DDD");
  61.     EnQueue(&queue, string);
  62.     memset(string, 0, sizeof(STRINGSIZE));
  63.     strcpy(string, "EEE");
  64.     EnQueue(&queue, string);
  65.     memset(string, 0, sizeof(STRINGSIZE));
  66.     strcpy(string, "FFF");
  67.     EnQueue(&queue, string);
  68.     memset(string, 0, sizeof(STRINGSIZE));
  69.     strcpy(string, "GGG");
  70.     EnQueue(&queue, string);
  71.     memset(string, 0, sizeof(STRINGSIZE));
  72.     strcpy(string, "HHH");
  73.     EnQueue(&queue, string);
  74.     memset(string, 0, sizeof(STRINGSIZE));
  75.     strcpy(string, "III");
  76.     EnQueue(&queue, string);
  77.     printf("222**************************************************************\n");
  78.     PrintQueue(queue);
  79.     
  80.     memset(string, 0, sizeof(STRINGSIZE));
  81.     strcpy(string, "JJJ");
  82.     EnQueue(&queue, string);
  83.     printf("333**************************************************************\n");
  84.     PrintQueue(queue);
  85.     
  86.     memset(string, 0, sizeof(STRINGSIZE));
  87.     GetQueueHead(queue, string);
  88.     printf("取得的队首元素=[%s]\n", string);
  89.     
  90.     memset(string, 0, sizeof(STRINGSIZE));
  91.     strcpy(string, "KKK");
  92.     EnQueue(&queue, string);
  93.     memset(string, 0, sizeof(STRINGSIZE));
  94.     strcpy(string, "LLL");
  95.     EnQueue(&queue, string);
  96.     memset(string, 0, sizeof(STRINGSIZE));
  97.     strcpy(string, "MMM");
  98.     EnQueue(&queue, string);
  99.     memset(string, 0, sizeof(STRINGSIZE));
  100.     strcpy(string, "NNN");
  101.     EnQueue(&queue, string);
  102.     memset(string, 0, sizeof(STRINGSIZE));
  103.     strcpy(string, "OOO");
  104.     EnQueue(&queue, string);
  105.     memset(string, 0, sizeof(STRINGSIZE));
  106.     strcpy(string, "PPP");
  107.     EnQueue(&queue, string);
  108.     printf("444**************************************************************\n");
  109.     PrintQueue(queue);
  110.     
  111.     memset(string, 0, sizeof(STRINGSIZE));
  112.     DeQueue(&queue, string);
  113.     printf("出队的元素1=[%s]\n", string);
  114.     memset(string, 0, sizeof(STRINGSIZE));
  115.     DeQueue(&queue, string);
  116.     printf("出队的元素2=[%s]\n", string);
  117.     printf("555**************************************************************\n");
  118.     PrintQueue(queue);
  119.     
  120.     memset(string, 0, sizeof(STRINGSIZE));
  121.     DeQueue(&queue, string);
  122.     memset(string, 0, sizeof(STRINGSIZE));
  123.     DeQueue(&queue, string);
  124.     memset(string, 0, sizeof(STRINGSIZE));
  125.     DeQueue(&queue, string);
  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.     flag = QueueIsEmpty(queue);
  153.     if(flag == 1)
  154.         printf("空队列!\n");
  155.     else if(flag == 2)
  156.         printf("非空队列!\n");
  157.     
  158.     return 0;
  159. }

  160. /*功能:初始化队列*/
  161. int InitQueue(QUEUE * queue)
  162. {
  163.     queue->base = (STRING *)malloc(MAXQSIZE * sizeof(STRING));
  164.     if(queue->base == NULL)
  165.     {
  166.         printf("InitQueue malloc err! 退出程序!\n");
  167.         exit(-1);
  168.     }
  169.     queue->front = queue->rear = 0;
  170.     queue->queuesize = MAXQSIZE;
  171.     
  172.     return 0;
  173. }

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

  194. /*功能:出队:从队列头删除一个元素*/
  195. int DeQueue(QUEUE * queue, STRING string)
  196. {
  197.     if(queue->front == queue->rear)
  198.     {
  199.         printf("队列为空,无元素可出队列!\n");
  200.         return -1;
  201.     }
  202.     strcpy(string, *(queue->base + queue->front));
  203.     queue->front = (queue->front + 1) % queue->queuesize;
  204.     printf("出队一个元素=[%s],队列空间大小=[%d],队列中剩余元素个数=[%d]\n", string, queue->queuesize, QueueLen(*queue));
  205.     
  206.     return 0;
  207. }

  208. /*功能:求队列中所有元素的个数*/
  209. int QueueLen(QUEUE queue)
  210. {
  211.     int len = 0;
  212.     len = (queue.rear - queue.front + queue.queuesize) % queue.queuesize;
  213.     /*
  214.     while(queue.front != queue.rear)
  215.     {
  216.         len++;
  217.         queue.front = (queue.front + 1) % queue.queuesize; //对头指针前移
  218.     }
  219.     */
  220.     return len;
  221. }

  222. /*功能:打印队列中的所有元素*/
  223. int PrintQueue(QUEUE queue)
  224. {
  225.     STRING string;
  226.     int i = 0;
  227.     printf("循环队列空间大小=[%d], 队列中的元素个数=[%d]\n", queue.queuesize, QueueLen(queue));
  228.     printf("从队列头开始;\n");
  229.     while(queue.front != queue.rear)
  230.     {
  231.         i++;
  232.         memset(string, 0 ,sizeof(string));
  233.         strcpy(string, *(queue.base + queue.front));
  234.         printf("(第%d个元素)=[%s],", i, string);
  235.         queue.front = (queue.front + 1) % queue.queuesize; /*对头指针前移*/
  236.     }
  237.     printf("\n");
  238.     
  239.     return 0;
  240. }

  241. /*功能:销毁队列*/
  242. int DestroyQueue(QUEUE * queue)
  243. {
  244.     free(queue->base);
  245.     queue->base = NULL;
  246.     queue->front = 0;
  247.     queue->rear = 0;
  248.     queue->queuesize = 0;
  249.     printf("循环顺序队列已销毁!\n");
  250.     
  251.     return 0;
  252. }

  253. /*功能:将队列中元素清空,变为空队列(队列还在,不是销毁队列)*/
  254. int ClearQueue(QUEUE * queue)
  255. {
  256.     memset(*(queue->base), 0, queue->queuesize);
  257.     queue->front = queue->rear = queue->queuesize = 0;
  258.     printf("循环顺序队列已清空!\n");
  259.     
  260.     return 0;
  261. }

  262. /*功能:判断队列是否是空队列:1:空队列,2:非空队列*/
  263. int QueueIsEmpty(QUEUE queue)
  264. {
  265.     if(queue.front == queue.rear) /*空队列*/
  266.         return 1;
  267.     else
  268.         return 2;
  269. }

  270. /*功能:取得队列头元素,并不移动队列头指针*/
  271. int GetQueueHead(QUEUE queue, STRING string)
  272. {
  273.     if(queue.front == queue.rear)
  274.     {
  275.         printf("队列为空,无队列头元素可出队列!\n");
  276.         return -1;
  277.     }
  278.     strcpy(string, *(queue.base + queue.front));
  279.     return 0;
  280. }

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

上一篇:链式队列

下一篇:链式栈

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