(C语言队列的顺序实现(数据结构十)

梦里梦外; 2022-09-17 10:25 244阅读 0赞

1.数据类型定义

在代码中为了清楚的表示一些错误和函数运行状态，我们预先定义一些变量来表示这些状态。在head.h头文件中有如下定义：

  1. //定义数据结构中要用到的一些变量和类型
  2. #ifndef HEAD_H
  3. #define HEAD_H
  5. #include <stdio.h>
  6. #include <malloc.h>
  7. #include <stdlib.h>
  9. #define TRUE  1
  10. #define FALSE 0
  11. #define OK    1
  12. #define ERROR  0
  13. #define INFEASIBLE -1
  14. #define OVERFLOW   -2    //分配内存出错
  16. typedef int  Status;     //函数返回值类型
  17. typedef int  ElemType;   //用户定义的数据类型
  19. #endif

2.数据结构定义

  1. typedef struct Queue{
  2.     ElemType *data;
  3.     int      head;
  4.     int      tail;
  5.     int      capacity;
  6. }Queue,*pQueue;

3.队列顺序实现

LinerQueue.h中实现代码如下： 

  1. #ifndef LINARQUEUE_H
  2. #define LINARQUEUE_H
  4. #include "head.h"
  6. #define  INIT_QUEUE_CAPACITY 100
  7. #define  QUEUE_ICREMENT_SIZE 10
  9. typedef struct Queue{
  10.     ElemType *data;
  11.     int      head;
  12.     int      tail;
  13.     int      capacity;
  14. }Queue,*pQueue;
  17. //初始化队列
  18. Status InitQueue(pQueue &Q){
  19.     Q=(pQueue)malloc(sizeof(Queue));
  20.     if(!Q) return OVERFLOW;
  21.     Q->data=(ElemType*)malloc(INIT_QUEUE_CAPACITY*sizeof(ElemType));
  22.     if(!Q->data) return OVERFLOW;
  23.     Q->head=0;
  24.     Q->tail=0;
  25.     Q->capacity=INIT_QUEUE_CAPACITY;
  26.     return OK;
  27. }
  28. //销毁队列
  29. Status DestroyQueue(pQueue &Q){
  30.     free(Q->data);
  31.     Q->head=0;
  32.     Q->tail=0;
  33.     Q->capacity=0;
  34.     free(Q);
  35.     Q=NULL;
  36.     return OK;
  37. }
  38. //清空队列
  39. Status ClearQueue(pQueue &Q){
  40.     if(Q==NULL) return ERROR;
  41.     Q->head=0;
  42.     Q->tail=0;
  43.     Q->capacity=INIT_QUEUE_CAPACITY;
  44.     return OK;
  45. }
  46. //队列是否为空
  47. Status QueueEmpty(pQueue Q){
  48.     if(Q==NULL) return ERROR;
  49.     return Q->head==Q->tail;
  50. }
  51. //队列长度
  52. Status QueueLength(pQueue Q){
  53.     if(Q==NULL) return ERROR;
  54.     return Q->tail-Q->head;
  55. }
  56. //取得队头数据
  57. Status GetHead(pQueue Q,ElemType &e){
  58.     if(QueueLength(Q)==0) return ERROR;
  59.     e=Q->data[Q->head];
  60.     return OK;
  61. }
  62. //从队尾插入数据
  63. Status InsertQueue(pQueue &Q,ElemType e){
  64.     if(QueueLength(Q)>=Q->capacity){
  65.         Q->data=(ElemType*)realloc(Q->data,(Q->capacity+QUEUE_ICREMENT_SIZE)*sizeof(ElemType));
  66.         if(!Q->data) return OVERFLOW;
  67.         Q->capacity+=QUEUE_ICREMENT_SIZE;
  68.     }
  69.     Q->data[Q->tail++]=e;
  70.     return OK;
  71. }
  72. //从队头删除数据
  73. Status DeleteQueue(pQueue &Q,ElemType &e){
  74.     if(Q==NULL) return ERROR;
  75.     GetHead(Q,e);
  76.     for (int i=Q->head+1;i<=Q->tail;i++)
  77.     {
  78.         Q->data[i-1]=Q->data[i];
  79.     }
  80.     Q->tail--;
  81.     return OK;
  82. }
  83. //用(*visit)()遍历队列
  84. Status QueueTraverse(pQueue &Q,Status (*visit)(ElemType)){
  85.     for (int i=Q->tail-1;i>=Q->head;i--)
  86.     {
  87.         (*visit)(Q->data[i]);
  88.     }
  89.     return OK;
  90. }
  91. Status print(ElemType e){
  92.     printf("%d->",e);
  93.     return true;
  94. }
  95. //输出队列
  96. Status printQueue(pQueue Q){
  97.     if(Q==NULL) return ERROR;
  98.     printf("\ntail->");
  99.     QueueTraverse(Q,print);
  100.     printf("head\n");
  101.     return true;
  102. }
  104. #endif

4.测试栈

  1. #include "LinerQueue.h"
  2. void main(){
  3.     pQueue Q;
  4.     InitQueue(Q);
  5.     for (int i=0;i<10;i++)
  6.     {
  7.         InsertQueue(Q,i);
  8.     }
  10.     ElemType e2;
  11.     DeleteQueue(Q,e2);
  12.     printf("\n删除队列头：%d",e2);
  15.     printQueue(Q);
  17.     printf("\n队列长度：%d",QueueLength(Q));
  18.     ElemType e;
  19.     GetHead(Q,e);
  20.     printf("\n队列头:%d",e);
  23.     ClearQueue(Q);
  24.     DestroyQueue(Q);
  27. }

5.测试结果

  1. 删除队列头：0
  2. tail->9->8->7->6->5->4->3->2->1->head
  4. 队列长度：9
  5. 队列头:1

发表评论

表情：
评论列表 （有 0 条评论，244人围观）

还没有评论，来说两句吧...

相关阅读