C语言数据结构之判断循环链表空与满
前言：
何时队列为空？何时为满？
由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。
注：先进入的为‘头'，后进入的为‘尾'。
解决此问题的方法至少有三种：
其一是另设一个布尔变量以匹别队列的空和满；
其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。
第一种方法没有实现，下面实现第二种和第三种：
一、少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即：
队空时： front=rear
队满时： (rear+1)%maxsize=front
front指向队首元素，rear指向队尾元素的下一个元素。
|
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
|
///////////////////////////////////////// // // author: kangquan2008@csdn // ///////////////////////////////////////// #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define QUEUE_SIZE 10 #define EN_QUEUE 1 #define DE_QUEUE 2 #define EXIT 3 typedef int Item; typedef struct QUEUE{ Item * item; int front; int tear; }Queue; int init_queue(Queue * queue) { queue->item = malloc(QUEUE_SIZE * sizeof(Item)); if(!queue->item) { printf("%s\n","Alloc failed,not memory enough"); exit(EXIT_FAILURE); } queue->front = queue->tear = 0; return 1; } int en_queue(Queue * queue, Item item) { if((queue->tear+1) % QUEUE_SIZE == queue->front) { printf("%s\n","The queue is full"); return -1; } queue->item[queue->tear] = item; queue->tear = (queue->tear + 1) % QUEUE_SIZE; return 1; } int de_queue(Queue * queue, Item * item) { if(queue->front == queue->tear) { printf("%s\n","The queue is empty"); return -1; } (*item) = queue->item[queue->front]; queue->front = (queue->front + 1) % QUEUE_SIZE; return 1; } int destroy_queue(Queue * queue) { free(queue->item); } int main() { Queue que; init_queue(&que); int elem; bool flag = true; while(flag) { int choice; printf("1 for en_queue,2 for de_queue,3 for exit\r\nplease input:"); scanf("%d",&choice); switch((choice)) { case EN_QUEUE: printf("input a num:"); scanf("%d",&elem); en_queue(&que,elem); break; case DE_QUEUE: if(de_queue(&que,&elem) == 1) printf("front item is:%d\n",elem); break; case EXIT: flag = false; break; default: printf("error input\n"); break; } } destroy_queue(&que); 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
|
#include <stdio.h> #include <assert.h> #define QueueSize 100typedef char datatype; //队列的数据元素 typedef struct { int front; int rear; int count; //计数器，用来记录元素个数 datatype data[QueueSize]; //数据内容 }cirqueue; //置空队 void InitQueue(cirqueue *q) { q->front = q->rear = 0; q->count = 0; } //判断队满 int QueueFull(cirqueue *q) { return (q->count == QueueSize); } //判断队空 int QueueEmpty(cirqueue *q) { return (q->count == 0); } //入队 void EnQueue(cirqueue *q, datatype x) { assert(QueueFull(q) == 0); //q满，终止程序 q->count++; q->data[q->rear] = x; q->rear = (q->rear + 1)%QueueSize; //循环队列设计，防止内存浪费 } //出队 datatype DeQueue(cirqueue *q) { datatype temp; assert(QueueEmpty(q) == 0);//q空，则终止程序，打印错误信息 temp = q->data[q->front]; q->count--; q->front = (q->front + 1)%QueueSize; return temp; } |
如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/yanzongshuai/article/details/11883625
