数据结构 -- 链队列

工程目录结构图:

common.h:

 1 //#ifndef __common_h__
 2 //#define __common_h__
 3 
 4 #define OK 1
 5 #define ERROR 0
 6 #define TRUE 1
 7 #define FALSE 0 
 8 
 9 #define MAXSIZE 20
10 
11 typedef int Status;        //函数的返回结果，OK、ERREO、TRUE、FALSE
12 typedef int ElemType;   //结点数据域的数据类型
13 
14 //#endif

common.c:

1 #include "common.h"
2 
3 Status visit(ElemType e)
4 {
5     printf("%d , ", e);
6     return OK;
7 }

LinkQueue.h:

 1 //链队列结点结构
 2 typedef struct QNode
 3 {
 4     ElemType data;
 5     struct QNode *next;
 6 }QNode, *QNodePtr;
 7 
 8 //链队列,带有头结点
 9 typedef struct
10 {
11     QNodePtr front, rear;
12 }LinkQueue;

LinkQueue.c:

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #include "common.h"
  4 #include "LinkQueue.h"
  5 
  6 Status InitLinkQueue(LinkQueue *Q)
  7 {
  8     Q->front = Q->rear = (QNodePtr)malloc(sizeof(QNode));
  9     if (!Q->front)
 10         return FALSE;
 11     Q->front->next = NULL;
 12     return OK;
 13 }
 14 
 15 Status LinkQueueEmpty(LinkQueue Q)
 16 {
 17     if (Q.front == Q.rear)
 18         return TRUE;
 19     else
 20         return FALSE;
 21 }
 22 
 23 int GetLinkQueueLegth(LinkQueue Q)
 24 {
 25     int length = 0;
 26 
 27     QNodePtr ptr = Q.front;
 28     while (ptr != Q.rear)
 29     {
 30         ++length;
 31         ptr = ptr->next;
 32     }
 33 
 34     return length;
 35 }
 36 
 37 Status EnLinkQueue(LinkQueue *Q, ElemType e)
 38 {
 39     QNodePtr ptr = (QNodePtr)malloc(sizeof(QNode));
 40     if (!ptr)
 41         return ERROR;
 42     ptr->data = e;
 43     ptr->next = NULL;
 44 
 45     Q->rear->next = ptr; //把新结点ptr赋值给原队尾结点的后继
 46     Q->rear = ptr;       //把新结点ptr设置为队尾结点
 47 
 48     return OK;
 49 }
 50 
 51 
 52 Status DeLinkQueue(LinkQueue *Q, ElemType *e)
 53 {
 54     if (Q->front == Q->rear)
 55         return ERROR;
 56     QNodePtr ptr = Q->front->next;
 57     *e = ptr->data;
 58 
 59     Q->front->next = ptr->next;
 60     if (ptr == Q->rear)
 61         Q->rear = Q->front;
 62 
 63     free(ptr);
 64     return OK;
 65 }
 66 
 67 Status ClearLinkQueue(LinkQueue *Q)
 68 {
 69     if (Q->front == Q->rear)
 70         return OK;
 71 
 72     Q->rear = Q->front;
 73     QNodePtr p, q;
 74     p = Q->front->next;
 75     Q->front->next = NULL;
 76 
 77     while (p)
 78     {
 79         q = p;
 80         p = p->next;
 81         free(q);
 82     }
 83 
 84     return OK;
 85 }
 86 
 87 Status DestroyLinkQueue(LinkQueue *Q)
 88 {
 89     while (Q->front)
 90     {
 91         Q->rear = Q->front->next;
 92         free(Q->front);
 93         Q->front = Q->rear;
 94     }
 95     return OK;
 96 }
 97 
 98 Status GetLinkHead(LinkQueue *Q, ElemType *e)
 99 {
100     if (Q->front == Q->rear)
101         return ERROR;
102 
103     *e = Q->front->next->data;
104     return OK;
105 }
106 
107 Status LinkQueueTraverse(LinkQueue Q)
108 {
109     QNodePtr ptr = Q.front->next;
110     while (ptr)
111     {
112         visit(ptr->data);
113         ptr = ptr->next;
114     }
115 
116     return OK;
117 }
118 
119 void LinkQueueStart()
120 {
121     LinkQueue Q;
122 
123     if (OK == InitLinkQueue(&Q))
124         printf("
链队列初始化完成
");
125 
126     if (LinkQueueEmpty(Q))
127         printf("
链队列为空!
");
128     else
129         printf("
链队列不为空，队列长度: %d
", GetLinkQueueLegth(Q));
130 
131     for (int i = 1; i <= 5; ++i)
132         EnLinkQueue(&Q, i);
133 
134     printf("
入队 1-5 后的队列长度: %d
", GetLinkQueueLegth(Q));
135 
136     LinkQueueTraverse(Q);
137 
138     if (LinkQueueEmpty(Q))
139         printf("

链队列为空!
");
140     else
141         printf("
链队列不为空，队列长度: %d
", GetLinkQueueLegth(Q));
142 
143     ElemType e;
144     GetLinkHead(&Q, &e);
145     printf("
对头元素为: %d
", e);
146 
147     DeLinkQueue(&Q, &e);
148     printf("
对头出列: %d
", e);
149 
150     printf("
对头出列后的队列长度: %d
", GetLinkQueueLegth(Q));
151 
152     ClearLinkQueue(&Q);
153     printf("
清空列后的队列长度: %d
", GetLinkQueueLegth(Q));
154 
155     DestroyLinkQueue(&Q);
156     printf("
销毁队列后,Q.front= %u Q.rear= %u
", Q.front, Q.rear);
157 
158 }

main.c:

 1 int main()
 2 {
 3     //LinkListStart();
 4     //StackStart();
 5     //LinkStackStart();
 6     //StartQueue();
 7     LinkQueueStart();
 8     getchar();
 9     return 0;
10 }