队列的链式存储C语言实现_请设计void clearqueue(linkqueue *q)函数。 该函数清除不带头节点的链队q

参考资料为《大话数据结构》

typedef int ElemType;
typedef struct {       //结点
	ElemType data;
	struct QNode* next;
}QNode, * QueuePtr;

typedef struct {      //队列链表结构
	QueuePtr front, rear;
}LinkQueue;
1
2
3
4
5
6
7
8
9

1、初始化

//初始化
void InitQueue(LinkQueue* Q) {
	Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q->front) {
		printf("初始化失败\n");
	}
	Q->front->next = NULL;  //带头结点（front指向头结点）
}
1
2
3
4
5
6
7
8

2、清除队列

//清除队列
void DestoryQueue(LinkQueue* Q) {
	while (Q->front) {
		Q->rear = Q->front->next;
		free(Q->front);
		Q->front = Q->rear;
	}
}
1
2
3
4
5
6
7
8

3、清空队列

//清空队列
void ClearQueue(LinkQueue* Q) {
	QueuePtr p, q;
	Q->rear = Q->front;
	p = Q->front->next;
	Q->front->next = NULL;
	while (p) {
		q = p;
		p = p->next;
		free(q);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

4、判断是否为空

//判断是否为空队列
bool QueueEmpty(LinkQueue Q) {
	if (Q.rear == Q.front) {
		return true;
	}
	else {
		return false;
	}
}
1
2
3
4
5
6
7
8
9

5、求队列长度

//求队列长度
int QueueLength(LinkQueue Q) {
	QueuePtr p;
	p = Q.front;
	int i = 0;
	while (Q.rear != p) {
		i++;
		p = p->next;
	}
	return i;
}
1
2
3
4
5
6
7
8
9
10
11

6、获取队头元素

//获取队头元素
bool GetHead(LinkQueue Q, ElemType* e) {
	if (Q.rear == Q.front) {   //队列为空
		return false;
	}
	else {
		QueuePtr p;
		p = Q.front->next;
		*e = p->data;
		return true;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

7、插入元素

//插入元素
bool EnQueue(LinkQueue* Q, ElemType e) {
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
	if (!s) {
		//printf("插入失败\n");
		return false;
	}
	else {
		s->data = e;
		Q->rear->next = s;
		s->next = NULL;
		Q->rear = s;
		return true;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

8、删除元素

//删除元素
bool DeQueue(LinkQueue* Q, ElemType* e) {
	QueuePtr p;
	if (Q->front == Q->rear) {
		return false;
	}
	else {
		p = Q->front->next;
		*e = p->data;
		Q->front->next = p->next;
		if (Q->rear == p) {   //若队头已经是队尾，则让队尾指针指向头结点，队列变空
			Q->rear = Q->front;
		}
		free(p);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

9、输出

//输出
void ShowQueue(LinkQueue Q) {
	QueuePtr p;
	p = Q.front->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10

10、完整+测试程序

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdbool.h>
#include <stdio.h>
typedef int ElemType;
typedef struct {       //结点
	ElemType data;
	struct QNode* next;
}QNode, * QueuePtr;

typedef struct {      //队列链表结构
	QueuePtr front, rear;
}LinkQueue;

//初始化
void InitQueue(LinkQueue* Q) {
	Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q->front) {
		printf("初始化失败\n");
	}
	Q->front->next = NULL;  //带头结点（front指向头结点）
}

//清除队列
void DestoryQueue(LinkQueue* Q) {
	while (Q->front) {
		Q->rear = Q->front->next;
		free(Q->front);
		Q->front = Q->rear;
	}
}

//清空队列
void ClearQueue(LinkQueue* Q) {
	QueuePtr p, q;
	Q->rear = Q->front;
	p = Q->front->next;
	Q->front->next = NULL;
	while (p) {
		q = p;
		p = p->next;
		free(q);
	}
}

//判断是否为空队列
bool QueueEmpty(LinkQueue Q) {
	if (Q.rear == Q.front) {
		return true;
	}
	else {
		return false;
	}
}

//求队列长度
int QueueLength(LinkQueue Q) {
	QueuePtr p;
	p = Q.front;
	int i = 0;
	while (Q.rear != p) {
		i++;
		p = p->next;
	}
	return i;
}

//获取队头元素
bool GetHead(LinkQueue Q, ElemType* e) {
	if (Q.rear == Q.front) {   //队列为空
		return false;
	}
	else {
		QueuePtr p;
		p = Q.front->next;
		*e = p->data;
		return true;
	}
}

//插入元素
bool EnQueue(LinkQueue* Q, ElemType e) {
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
	if (!s) {
		//printf("插入失败\n");
		return false;
	}
	else {
		s->data = e;
		Q->rear->next = s;
		s->next = NULL;
		Q->rear = s;
		return true;
	}
}

//删除元素
bool DeQueue(LinkQueue* Q, ElemType* e) {
	QueuePtr p;
	if (Q->front == Q->rear) {
		return false;
	}
	else {
		p = Q->front->next;
		*e = p->data;
		Q->front->next = p->next;
		if (Q->rear == p) {   //若队头已经是队尾，则让队尾指针指向头结点，队列变空
			Q->rear = Q->front;
		}
		free(p);
	}
}

//输出
void ShowQueue(LinkQueue Q) {
	QueuePtr p;
	p = Q.front->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

//TEST
int main(void) {
	LinkQueue Q;
	InitQueue(&Q);
	ElemType n, d;
	int i;
	printf("是否空队列？%d(1:空 0:否)  ", QueueEmpty(Q));
	printf("队列的长度为%d\n", QueueLength(Q));
	printf("请输入整数（-1表示结束输入）：\n");
	int flag = 1;
	while (flag) {
		scanf("%d", &n);
		if (n == -1) {
			flag = 0;
			break;
		}
		EnQueue(&Q, n);
	}
	printf("插入元素后,队列的长度为%d\n", QueueLength(Q));
	printf("是否空队列？%d(1:空 0:否)  \n", QueueEmpty(Q));
	printf("队列的元素依次为：");
	ShowQueue(Q);
	i = GetHead(Q, &d);
	if (i) {
		printf("队头元素是：%d\n", d);
	}
	DeQueue(&Q, &d);
	printf("删除了队头元素%d\n", d);
	i = GetHead(Q, &d);
	if (i) {
		printf("新的队头元素是：%d\n", d);
	}
	return 0;
}
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