链式队列的实现 |flying0033

winston

/*        队列是一种先进先出线性表,队列是线性表的特化        也具有线性表的性质分为:顺序队列与链式队列        链式队列与线性表的单链表相似只不过链式队列只        允许从头部进行删除、尾部进行插入.需要为链式队列        创建一个头结点包括两个指针,指向队头的指针(front)        与指向队尾的指针(rear).当两个指针相等时队列为空*/

1. #ifndef LINKQUEUE_H
2. #define LINKQUEUE_H
3. typedef int ElemType;  //队列的数据类型
4. typedef struct node{
5.         ElemType data; //队列的数据类型
6.         struct node *next; //指向下一个结点
7. }QueNode,*QuePtr;
8. typedef struct{
9.         QuePtr front; //指向队头的指针
10.         QuePtr rear; //指向队尾的指针
11. }LinkQueue;
13. void InitQueue(LinkQueue *q); //初始化队列
15. void CreateQueue(LinkQueue *q); //创建队列
17. void EnQueue(LinkQueue *q,ElemType e); //进队操作,将元素e压入队列中
19. void DeQueue(LinkQueue *q,ElemType *e); //出队操作,将出队的元素存入*e中
21. int GetQueueLength(LinkQueue *q); //获取队列的长度
23. void Print(LinkQueue *q); //打印队列的元素
25. void Clear(LinkQueue *q); //清空队列
27. void TopQueue(LinkQueue *q,ElemType *e); //返回队头的元素
29. #endif //LINKQUEUE_H
31. #include "LinkQueue.h"
32. #include <stdio.h>
33. #include <stdlib.h>
34. void InitQueue(LinkQueue *q) //初始化队列
35. {
36.         q->front = q->rear = (QuePtr)malloc(sizeof(QueNode)); //初始化队头与队尾的指针指向头结点
37.         q->front->next = NULL;
38. }
40. void CreateQueue(LinkQueue *q) //创建队列
41. {
42.         InitQueue(q);
43.         printf("请输入要进队的元素以CTRL+Z结尾\n");
44.         int k;
45.         while((scanf("%d",&k)) != EOF)
46.                 EnQueue(q,k);
47. }
49. void EnQueue(LinkQueue *q,ElemType e) //将元素e进队
50. {
51.         QuePtr temp = (QuePtr)malloc(sizeof(QueNode)); //创建新结点
52.         if(temp) //如果内存分配成功
53.         {
54.                 temp->data = e; //初始化新结点的数据为e
55.                 temp->next = NULL; //队列只能从队尾插入所以下一个结点初始化为NULL
56.                 q->rear->next = temp; //将队尾结点的指针指向新结点,如果新结点为第一个结点则q->rear->next相当于q->front->next
57.                 q->rear = temp; //将指向队尾的指针指向新结点
58.         }
59. }
61. void DeQueue(LinkQueue *q,ElemType *e) //队头的结点出队,将出队的结点的元素存入*e
62. {
63.         if(q->front == q->rear) //队列为空
64.                 return;
65.         QuePtr temp = q->front->next; //初始化temp为要出队的结点的指针
66.         if(q->front->next == q->rear) //如果要出队的结点为最后一个结点,使q->rear指向头结点防止出现悬空的指针
67.                 q->rear = q->front;
68.         *e = temp->data; //将出队的数据元素存入*e
69.         q->front->next = temp->next; //使下一个结点成为队头,如果没有下一个结点则为NULL
70.         free(temp); //删除要出队的结点
71. }
73. bool IsEmpty(LinkQueue *q) //判断队列是否为空
74. {
75.         if(q->front == q->rear)
76.                 return true;
77.         return false;
78. }
80. int GetQueueLength(LinkQueue *q) //返回队列的长度
81. {
82.         QuePtr temp = q->front;
83.         int i = 0;
84.         while(temp != q->rear)
85.         {
86.                 ++i;
87.                 temp = temp->next;
88.         }
89.         return i;
90. }
92. void Clear(LinkQueue *q) //清空队列
93. {
94.         QuePtr temp = q->front->next;
95.         while(temp)
96.         {
97.                 QuePtr tp = temp;
98.                 temp = temp->next;
99.                 free(tp);
100.         }
101.         temp = q->front;
102.         q->front = q->rear = NULL;
103.         free(temp);
104. }
105. void Print(LinkQueue *q) //打印队列的元素
106. {
107.         if(q->front == q->rear)
108.                 return;
109.         QuePtr temp = q->front->next;
110.         while(temp != q->rear)
111.         {
112.                 printf("%d ",temp->data);
113.                 temp = temp->next;
114.         }
115.         printf("%d",temp->data);
116.         printf("\n");
117. }
118. void TopQueue(LinkQueue *q,ElemType *e) //返回队头的结点元素存入*e
119. {
120.         if(q->front == q->rear)
121.                 return;
122.         *e = q->front->next->data;
123. }       
126. #include "LinkQueue.h"
127. #include <stdio.h>
128. int main()
129. {
130.         LinkQueue q;
131.         CreateQueue(&q);
132.         Print(&q);
133.         int top;
134.         TopQueue(&q,&top);
135.         printf("队头的元素为:%d\n",top);
136.         int len = GetQueueLength(&q);
137.         int k;
138.         printf("将队列中的所有元素出队:\n");
139.         for(int i = 0;i < len;++i)
140.         {
141.                 DeQueue(&q,&k);
142.                 printf("%d ",k);
143.         }
144.         printf("\n");
145.         Clear(&q);               
146.         return 0;
147. }

复制代码

作者：flying0033 发表于2011-12-23 23:58:54 原文链接