数据结构-队列的链式存储（链队列）

  1 #include "stdio.h"
  2 #include "stdlib.h"
  3 
  4 #define OK 1
  5 #define ERROR 0
  6 #define OVERFLOW -2
  7 typedef int Status;        //基本操作函数返回类型
  8 typedef int QElemType;    //数据基本存储类型
  9 
 10 /*结点结构*/
 11 typedef struct QNode
 12 {
 13     QElemType data;        //数据域
 14     struct QNode *next;    //指针域
 15 }*QueuePtr;
 16 
 17 /*队列结构*/
 18 typedef struct
 19 {
 20     QueuePtr froot;    //队头指针
 21     QueuePtr rear;    //队尾指针
 22 }LinkQueue;
 23 
 24 /*构造一个空队列Q*/
 25 Status InitQueue(LinkQueue &Q)
 26 {
 27 
 28     Q.froot = (QueuePtr)malloc(sizeof(QNode));    //分配空间赋给队头
 29     if(!Q.froot)
 30         exit(OVERFLOW);        //分配失败退出
 31     Q.rear = Q.froot;        //队尾初始指向队头并且next为空
 32     Q.froot->next = NULL;
 33     return OK;
 34 }
 35 
 36 /*销毁队列Q，Q不在存在*/
 37 Status DestroyQueue(LinkQueue &Q)
 38 {
 39     while(Q.froot)    //循环判断队头并用队尾指针做垫脚，顺链表加下去直到为空
 40     {
 41         Q.rear = Q.froot->next;
 42         free(Q.froot);
 43         Q.froot = Q.rear;
 44     }
 45     return OK;
 46 }
 47 
 48 /*重置队列Q为空*/
 49 Status ClearQueue(LinkQueue &Q)
 50 {
 51     //先循环清空队列除队头指针，在使队尾指向队头并且next为空
 52     QueuePtr p = Q.froot->next,q;
 53     while(p)
 54     {
 55         q = p->next;
 56         free(p);
 57         p = q;
 58     }
 59     Q.froot->next = NULL;
 60     Q.rear = Q.froot;
 61     return OK;
 62 }
 63 
 64 /*若队列Q为空队列则返回true，否则返回false*/
 65 Status QueueEmpty(LinkQueue Q)
 66 {
 67     if(Q.froot == Q.rear)    //队头与队尾相等代表空队列
 68         return true;
 69     else
 70         return false;
 71 }
 72 
 73 /*返回队列的长度*/
 74 int QueueLength(LinkQueue Q)
 75 {
 76     int j = 0;    //记录长度
 77     QueuePtr p = Q.froot;    //遍历队列指针
 78     while(p !=Q.rear)
 79     {
 80         j++;
 81         p = p->next; 
 82     }
 83     return j;
 84 }
 85 
 86 /*若队列不为空，则用e返回队头元素应返回OK否则返回ERROR*/
 87 Status GetQueue(LinkQueue Q, QElemType &e)
 88 {
 89     if(Q.froot == Q.rear)
 90         return ERROR;
 91     e = Q.froot->next->data;
 92     return OK;
 93 }
 94 
 95 /*插入元素e为新的队尾元素*/
 96 Status EnQueue(LinkQueue &Q, QElemType e)
 97 {
 98     QueuePtr p = (QueuePtr)malloc(sizeof(QNode));    //创建一个新的结点并分配空间
 99     if(!p) 
100         exit(OVERFLOW);
101     p->data = e;
102     p->next = NULL;
103     Q.rear->next = p;    //使队尾指向新结点
104     Q.rear = p;            //移动队尾指针
105     return OK;
106 }
107 
108 /*若队列不空，则删除队头元素，并用e返回其值应返回OK，否则返回ERROR*/
109 Status DeQueue(LinkQueue &Q, QElemType &e)
110 {
111     if(Q.froot == Q.rear)
112         return ERROR;
113     e = Q.froot->next->data;
114     QueuePtr p = Q.froot->next;
115     Q.froot->next = p->next;
116     if(p == Q.rear)
117         Q.rear = Q.froot;
118     free(p);
119     return OK;
120 }
121 
122 /*从队头到队尾依次遍历Visit函数一旦失败则返回操作失败*/
123 Status QueueTraverse(LinkQueue Q, bool (*Visit)(QElemType))
124 {
125     QueuePtr p = Q.froot->next;
126     while(p)
127     {
128         if(!Visit(p->data))
129             return ERROR;
130         p = p->next;
131     }
132     printf("
");
133     return OK;
134 }
135 
136 /*QueueTraverse调用函数
137 /*此处做输出元素用*/
138 bool Visit(QElemType e)
139 {
140     printf("%d ",e);
141     return true;
142 }