链队列

  1 /*
  2 链队列
  3 LJK 2018-07-04
  4 */
  5 #include<stdio.h>
  6 #include<stdlib.h>
  7 #include<math.h>
  8 
  9 #define OK 1
 10 #define ERROR 0
 11 #define TRUE 1
 12 #define FALSE 0
 13 
 14 typedef int QElemType;
 15 typedef int Status;
 16 
 17 typedef struct qNode
 18 {
 19     QElemType data;
 20     struct  qNode *next;
 21 }QNode;
 22 
 23 typedef struct
 24 {
 25     QNode *front, *rear;
 26 }LinkQueue;
 27 
 28 // 初始化链队列时，生成一个头结点，此时front、rear同时指向头节点
 29 // 头节点data中是随机值
 30 Status InitQueue(LinkQueue *Q)
 31 {
 32     Q->front = Q->rear = (QNode*)malloc(sizeof(QNode));
 33     if (!Q->front) exit(OVERFLOW);
 34     Q->front->next = NULL;
 35     return OK;
 36 }
 37 
 38 Status QueueEmpty(LinkQueue Q)
 39 {
 40     if (Q.front == Q.rear) return TRUE;
 41     else return FALSE;
 42 }
 43 
 44 int QueueLen(LinkQueue Q)
 45 {
 46     int i = 0;
 47     QNode *p;
 48     p = Q.front;
 49     while (p!=Q.rear)
 50     {
 51         i++;
 52         p = p->next;
 53     }
 54     return i;
 55 }
 56 
 57 // 入队操作
 58 Status EnQueue(LinkQueue *Q, QElemType e)
 59 {
 60     QNode *s = (QNode*)malloc(sizeof(QNode));
 61     if (!s) exit(OVERFLOW);
 62     s->data = e;
 63     s->next = NULL;
 64     Q->rear->next = s;
 65     Q->rear = s;
 66     return OK;
 67 }
 68 
 69 Status QueueTraverse(LinkQueue Q)
 70 {
 71     QNode *p = Q.front->next;
 72     while (p)
 73     {
 74         printf("%d ", p->data);
 75         p = p->next;
 76     }
 77     printf("
");
 78     return OK;
 79 }
 80 
 81 Status GetHead(LinkQueue Q, QElemType *e)
 82 {
 83     if (Q.front == Q.rear) return ERROR;
 84     *e = Q.front->next->data;
 85     return OK;
 86 }
 87 
 88 // 出队操作
 89 Status DeQueue(LinkQueue *Q, QElemType *e)
 90 {
 91     QNode *p;
 92     if (Q->front == Q->rear) return ERROR;
 93     p = Q->front->next;
 94     *e = p->data;
 95     Q->front->next = p->next;
 96     if (p == Q->rear) Q->rear = Q->front;
 97     free(p);
 98     return OK;
 99 }
100 
101 Status ClearQueue(LinkQueue *Q)
102 {
103     QNode *p, *q;
104     Q->rear = Q->front;
105     p = Q->front->next;
106     Q->front->next = NULL;
107     while (p)
108     {
109         q = p;
110         p = p->next;
111         free(q);
112     }
113     return OK;
114 }
115 
116 // 销毁队列
117 Status DestroyQueue(LinkQueue *Q)
118 {
119     while (Q->front)
120     {
121         Q->rear = Q->front->next;
122         free(Q->front);
123         Q->front = Q->rear;
124     }
125     return OK; 
126 }
127 
128 int main()
129 {
130     int i;
131     QElemType d;
132     LinkQueue q;
133 
134     i = InitQueue(&q);
135     if (i) printf("队列构造成功!!!
");
136     printf("IsEmpty? %d (1:空  0:非空)
", QueueEmpty(q));
137     printf("LenQueue = %d

", QueueLen(q));
138 
139     EnQueue(&q, -5);
140     EnQueue(&q, 5);
141     EnQueue(&q, 10);
142     printf("插入三个元素后：
");
143     printf("LenQueue = %d
", QueueLen(q));
144     printf("IsEmpty? %d (1:空  0:非空)
", QueueEmpty(q));
145     printf("QueueData:");
146     QueueTraverse(q);
147     printf("
");
148 
149     i = GetHead(q, &d);
150     if (i == OK) printf("HeadData = %d
", d);
151     DeQueue(&q, &d);
152     printf("Delete HeadData:%d
", d);
153     i = GetHead(q, &d);
154     if (i == OK) printf("New HeadData = %d

", d);
155 
156     printf("QueueData:");
157     QueueTraverse(q);
158     printf("
");
159 
160     ClearQueue(&q);
161     printf("Clear Queue:q.front = %p q.rear = %p  q.front->next = %p

", q.front, q.rear, q.front->next);
162 
163     DestroyQueue(&q);
164     printf("Destroy Queue:q.front = %p q.rear = %p
", q.front, q.rear);
165 
166     getchar();
167     return 0;
168 }