『代码』··By/蜜汁炒酸奶

队列的动态链式存储实现—C语言

头文件

ElemType.h

/***
*ElemType.h - ElemType的定义
*
****/

#ifndef ELEMTYPE_H
#define ELEMTYPE_H

typedef int ElemType;

int  compare(ElemType x, ElemType y);
void visit(ElemType e);

#endif /* ELEMTYPE_H */
1
2
3
4
5
6
7
8
9
10
11
12
13
14

DynaLnkQueue.h

/***
*DynaLnkQueue.h - 动态链式队列的定义
*
****/

#if !defined(DYNALNKQUEUE_H)
#define DYNALNKQUEUE_H

#include "ElemType.h"

/*------------------------------------------------------------
// 链式队列结构的定义
------------------------------------------------------------*/

typedef struct Node
{
	ElemType data;				// 元素数据
	struct Node *next;			// 链式队列中结点元素的指针
} QNode, *QueuePtr;

typedef struct
{
	QueuePtr front;				// 队列头指针
	QueuePtr rear;				// 队列尾指针
} LinkQueue;

/*------------------------------------------------------------
// 链式队列的基本操作
------------------------------------------------------------*/

bool InitQueue(LinkQueue *Q);
void DestroyQueue(LinkQueue *Q);
bool QueueEmpty(LinkQueue Q);
int  QueueLength(LinkQueue Q);
bool GetHead(LinkQueue Q, ElemType *e);
void QueueTraverse(LinkQueue Q, void (*fp)(ElemType));
void ClearQueue(LinkQueue *Q);
bool EnQueue(LinkQueue *Q, ElemType e);
bool DeQueue(LinkQueue *Q, ElemType *e);

#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

主函数

Lab.cpp

#include <stdio.h>
#include <stdlib.h>
#include "DynaLnkQueue.h"

int main()
{
	LinkQueue *Q;
	ElemType e=3;
	 InitQueue(&Q);
	DestroyQueue(&Q);
	QueueEmpty(&Q);
	QueueLength(&Q);
	GetHead(&Q,e);
	QueueTraverse(&Q, visit(e));
	ClearQueue(&Q);
	EnQueue(&Q,e);
	DeQueue(&Q,&e);
	system("pause");
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

实现函数

ElemType.cpp

/***
*ElemType.cpp - ElemType的实现
*
****/

#include <stdio.h>
#include "ElemType.h"

int compare(ElemType x, ElemType y)
{
	return(x-y);
}

void visit(ElemType e)
{
	printf("%dn", e);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

DynaLnkQueue.cpp

/***
*DynaLnkQueue.cpp - 动态链式队列,即队列的动态链式存储实现
*
*
*题目:实验4 队列的动态链式存储实现
*

*
****/

#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <assert.h>
#include "DynaLnkQueue.h"

/*------------------------------------------------------------
操作目的:	初始化队列
初始条件:	无
操作结果:	构造一个空的队列
函数参数:
		LinkQueue *Q	待初始化的队列
返回值:
		bool			操作是否成功
------------------------------------------------------------*/
bool InitQueue(LinkQueue *Q)//初始化带头结点的队列
{
	Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q->front)
	{
		return false;
	}
    Q->front->next = NULL;
	return true;

}

/*------------------------------------------------------------
操作目的:	销毁队列
初始条件:	队列Q已存在
操作结果:	销毁队列Q
函数参数:
		LinkQueue *Q	待销毁的队列
返回值:
		无
------------------------------------------------------------*/
void DestroyQueue(LinkQueue *Q)
{
	while(Q->front)
	{
		Q->rear = Q->front->next;
		free(Q->front);
		Q->front = Q->rear;
	}

}

/*------------------------------------------------------------
操作目的:	判断队列是否为空
初始条件:	队列Q已存在
操作结果:	若Q为空队列,则返回true,否则返回false
函数参数:
		LinkQueue Q		待判断的队列
返回值:
		bool			是否为空
------------------------------------------------------------*/
bool QueueEmpty(LinkQueue Q)
{
	if (Q.front!=Q.rear)
	{
		return false;
	}
	return true;
}

/*------------------------------------------------------------
操作目的:	得到队列的长度
初始条件:	队列Q已存在
操作结果:	返回Q中数据元素的个数
函数参数:
		LinkQueue Q		队列Q
返回值:
		int				数据元素的个数
------------------------------------------------------------*/
int QueueLength(LinkQueue Q)
{
	int i;
	QueuePtr p= Q.front;
	while(p)
	{
		p = p->next;
		i++;
	}
	return i;
}

/*------------------------------------------------------------
操作目的:	得到队列首元素
初始条件:	队列Q已存在
操作结果:	用e返回队列首元素
函数参数:
		LinkQueue Q		队列Q
		ElemType *e		队列首元素的值
返回值:
		bool			操作是否成功
------------------------------------------------------------*/
bool GetHead(LinkQueue Q, ElemType *e)
{
	if (Q.front == Q.rear)
	{
		return false;
	}
	*e = Q.front->data;
	return true;
}

/*------------------------------------------------------------
操作目的:	遍历队列
初始条件:	队列Q已存在
操作结果:	依次对Q的每个元素调用函数fp
函数参数:
		LinkQueue Q		队列Q
		void (*fp)()	访问每个数据元素的函数指针
返回值:
		无
------------------------------------------------------------*/
void QueueTraverse(LinkQueue Q, void (*fp)(ElemType))
{
    QueuePtr p = Q.front->next;
	while(p)
	{
         fp(p->data);
		 p = p->next;
	}
}

/*------------------------------------------------------------
操作目的:	清空队列
初始条件:	队列Q已存在
操作结果:	将队列清空
函数参数:
		LinkQueue *Q	队列Q
返回值:
		无
------------------------------------------------------------*/
void ClearQueue(LinkQueue *Q)
{
	   QueuePtr p=Q->front->next;
      while(p)
	  {
         p->data = NULL;
		 p= p->next;
	  }
}

/*------------------------------------------------------------
操作目的:	在队列末尾插入元素e
初始条件:	队列Q已存在
操作结果:	插入元素e作为队列新的尾结点
函数参数:
		LinkQueue *Q		队列Q
		ElemType e		待插入的数据元素
返回值:
		bool			操作是否成功
------------------------------------------------------------*/
bool EnQueue(LinkQueue *Q, ElemType e)
{
   QueuePtr p =(QueuePtr)malloc(sizeof(QNode));
   if (!p)
   {
	   return false;
   }
   p->data = e;
   p->next = NULL;
   Q->rear->next = p;
   Q->rear = p;
	return true;

}

/*------------------------------------------------------------
操作目的:	删除链式队列的头结点
初始条件:	队列Q已存在
操作结果:	删除链式队列的头结点
函数参数:
		LinkQueue *Q		队列Q
		ElemType *e		待插入的数据元素
返回值:
		bool			操作是否成功
------------------------------------------------------------*/
bool DeQueue(LinkQueue *Q, ElemType *e)
{
	QueuePtr p =Q->front->next;
	if (Q->front == Q->rear)
	{
		return false;
	}
	*e = p->data;
	Q->front->next = p->next;
	if (!p->next)
	{
		Q->rear = Q->front;
	}
	free(p);


	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208

预览
Loading comments...
3 条评论
  • W

    记得以前写过。还有Gravatar头像挂了好忧伤

  • W

    函数什么的最头疼····

    • W

      回复 @Me.稀奇: 恩,开始是很头痛,但要是把自己写进去就是享受

example
预览