高
0%

C和数据结构——队列的两种实现

Posted on Edited on In
队列的两种实现和相关操作

静态

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
/*
插入：进队：队尾
删除：出队：队头
可以想象一下啊买东西排队的情况
First In First Out
F I F O
允许插入的一端成为队尾，允许删除的一端称为队头。
所以我们再学习这一部分知识的时候一定要对头插法和
尾插法有着熟练的掌握！

！！！模型一：！！！
front： 头指针，指向队列头元素
rear:  尾指针，指向尾元素的下一个
队空条件：front == rear
队满条件：rear - front ==0
这里读者可以自己试试几种队满和对空的情况

通过不断的测试，我们发现，如果仅仅根据rear =MAXSIZE
判断队满的情况是不合理的，因为再实际的生活和问题中我们知道
，一个队伍可以站多少人，完全取决于总的人数，也就是MAXSIZE
，而不是取决于最后一个人是不是站在了某一个地方，也就是rear==MAXSIZE
，如果那样的话，显然会造成存储空间的大大浪费，所以，
模型二：
我们这里不妨1设想，即使使用数组，数组也是一个循环或者说是一个front 和
rear连在一起环状数组，数组的下标同样成立，比如，当MAXSIZE=5,front =4时
,按照道理说此时的rear已经起码为5了（其实按照道理是不可以的），也就是说不能再进队了，
但是可以想到，在front 的前面应该还有4个位置，所以根据循环数组
的假设，我们知道此时的rear应该是rear = 1，而不是5，可以继续
在top处入队，假设此时处于4的位置元素为a,=进入新的元素b,之后，
b就在4的位置了，而a就在0的位置了，此时相应的rear的位置应该为1，也就是
队头指针进一：front=(front+) MOD MAXSIZE
队尾元素进一： rear = (rear+1) MOD MAXSIZE,
而不是简单的加一操作了。
如此继续进行入队，我们发现：
当队满的时候，front = rear但是不等于0，而且不同的入队和出队的情况下，队满的
情况也不一样，最为头疼的是，我们好像没法判断队空了，因为此时队空和队满都
是front = rear,!!所以，为了可以区分这个问题我们
规定：
1，当rear = front时，队空
2，当(rear+1)MOD MAXSIZE = front 时，队满
由2的规定我们不难发现，按照这种情况下的队满，不是真正意义上的队满，
比如此时rear = 3，front  = 4，由2的规定，我们知道已经满足，但是
由于rear并不会指向元素，所以当队满的时候，实际上还是可以加入一个
元素，但是不得不说，这个相对于模型一已经有巨大的改进了；
可以归纳如下：
队空：Q.front == Q.rear
对满： (Q.rear+1)%MAXSIZE == Q.front 
进队： Q.data[Q.rear]=x; Q.rear =(Q.rear+1)%MAXSIZE;
出队： x=Q.data[Q.front]; Q.front = (Q.front+1)%MAXSIZE;
模型三：
可以设置一个flag标识，每次

*/
//静态存储
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 20
typedef char ElemType;
//typedef struct
//{
//    ElemType data[MAX_SIZE]; //所有元素
//    int front, raer;         //队尾和队头
//} SqQueue;
#define MAXQSIZE 100 //最大的队列长度+1
typedef struct
{
    ElemType *base; //用来初始化分配空间
    int front;
    int rear;

} SqQueue;

//初始化队列
void InitQueue(SqQueue &Q)
{
    Q.base = (ElemType *)malloc(MAXQSIZE * sizeof(ElemType));
    if (!Q.base)
        exit(OVERFLOW); //判断是否分配成功
    Q.front = Q.rear = 0;
}

//销毁队列
void DestroyQueue(SqQueue Q)
{
    if (Q.base)
    //如果队不是空
    {
        free(Q.base);
        Q.base = NULL;
        Q.front = Q.rear = 0; //这里的表参数也要改变
    }
}

//入队列
int EnQueue(SqQueue &Q,ElemType e{
    if ((Q.rear + 1) % MAXQSIZE == Q.front)
        return 0; //判断是否队满
    Q.base[Q.rear] = 0;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return 1;
}

//出队
int DeQueue(SqQueue &Q,Elemtype &e){
    if (Q.front == Q.rear) //如果为空，删除并返回队头元素
        return 0;          //否则返回0
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return 1;
}

//取队头元素
int GetHead(SqQueue Q,Elemtype &e){
    if (Q.front == Q.rear)
        return 0;
    e = Q.base[Q.front];
    return 1;
}

//判断队空
int QueueEmpty(SqQueue Q){
    if (Q.front == Q.rear)
        return 1;
    else
        return 0;
}


//求队列中元素的个数(循环队列)
int QueueLength(SqQueue Q){
    /*其实我自己的想法是根据队满条件建立循环，但是总结发现
    这个方法确实成立，而且很简便*/
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

/*如果只有front队头指针，一个计数器count, 大小为MAXSIZE的
环形数组，问
1，最多可以容纳多少元素
2，设计相关算法*/
#define MaxSize 10
typedef struct{
    int data[MaxSize];
    int front;
    int count;
}SQ;
//SQ为空：sq.count == 0;
//队满： sq.count == MaxSize;
//队尾元素的位置： (sq.front +sq.count)%MaxSize;

//初始化
void InitSQ(SQ &qu){
    qu.front = qu.count = 0;

}

//销毁队列不需要，因为没有malloc

//入队
int EnSQ(SQ &sq,int x){
    if (sq.count == MaxSize)
        return 0;
    sq.data[(sq.front + sq.count) % MaxSize] = x;
    sq.count++; //计数器
    return 1;
}

//出队
int DeSQ(SQ &sq,int &x){
    if (sq.count == 0)
        return 0;
    x = sq.data[sq.front];
    sq.front = (sq.front + 1) % MaxSize; //重要
    sq.count--;                          //计数器
    return 1;
}

//取队头元素
int GetSQ(SQ sq,int &x){
    if (sq.count == 0) //判断队是否为空
        return 0;
    x = sq.data[sq.front];
    return 1;
}

//判断队空
int SQEmpty(SQ sq){
    if (sq.count == 0)
        return 1; //如果队空，返回1；
    else
        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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//带有头结点的单链表
//数据结点

typedef struct
{
    char data;          //存放对元素
    struct QNode *next; //指向下一结点
} QNode, *QueuePtr;

//链队结点
typedef struct
{
    QNode *front; //队头指针，删除使用
    QNode *rear;  //队尾指针，加入使用
} LinkQueue;

//判断条件
//队空：Q.front->next==NULL
//队满：基本不可能
//进队: 同链表，创建结点。插入队尾，并由Q.rear指向它，也就是尾插法
//出队；删除队头的结点

//初始化链队列
void InitQueueLink(LinkQueue &Q)
{
    if (!Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)))
        exit(OVERFLOW);
    Q.front->next = NULL;
}

//销毁队列
void DestroyQueue(LinkQueue &Q)
{
    while (Q.front) //这是一个循环，rear是front的同步指针，来循环遍历删除
    {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    Q.front = Q.rear = NULL;
}

//入队列
void EnQueue(LinkQueue &Q, char e)
{
    QueuePtr p; //存放新的元素
    if (!p = (QueuePtr)malloc(sizeof(QNode)))
        exit(OVERFLOW); //这句话不但申请了空间，还进行了检查
    p->data = e;
    p->next = NULL;
    Q.rear->next = p; //链接
    Q.rear = p;       //更新rear位置
}

//出队列,其实就是头插法
int DeQueue(LinkQueue &Q, char &e)
{
    QueuePtr p;
    if (Q.front == Q.rear)
        return 0;
    p = Q.front->next;       //让p和首元素在指向同一块区域，也就是找到要释放的地方
    e = p->data;             //将数据存在p中
    Q.front->next = p->next; //将front 链接到要释放的地方的后面
    if (Q.rear == p)         //如果只有一个元素的话，队列为空
        Q.rear = Q.front;
    free(p); //释放p和它对应的结点
    return 1;
}

//取队头元素
int GetHead(LinkQueue Q, char &e)
{
    QueuePtr p; //这里不定义这个指针也行，但是要保证队不为空，此时直接e = Q.front->next->data;
    if (Q.rear = Q.front)
    {
        return 0;
    }
    p = Q.front->next;
    e = p->data;
    return 1;
}

//判断队空
int QueueEmpty(LinkQueue Q)
{
    if (!Q.front->next == NULL)
        return 0;
    else
        return 1;
}

/*实例：
使用不带头结点的循环链表来表示队列，Q是这样的链表中尾节点指针
基于此，给出入队和出队算法
*/
//审题：虽然=题目没有设置队头结点。但是由于是循环单链表，reae->next就是首结点
//同理，如果Q.rear == NULL;那么队列为空；
//如果Q.rear->next  == Q,那就是只有一个结点
typedef struct node
{
    char data;         //数据域
    struct node *next; //指针域
} QNode;               //结点数据类型

//入队列
void EnterQueue(QNode *&Q, char x)
{
    QNode *s;
    s = (QNode *)malloc(sizeof(QNode));
    s->data = x;
    if (Q == NULL) //如果原队为空，那就原地打转一次
    {
        Q = s;
        Q->next = Q;
    }
    else
    {
        s->next = Q->next; //先让s指向首元素
        Q->next = s;       //链接
        Q = s;             //更新尾结点的位置
    }
}

//出队列
int ExitQueue(QNode *&Q, char &x)
{
    QNode *s;
    if (Q == NULL) //队为空的情况
        return 0;
    if (Q->next == Q) //只有一个结点的情况
    {
        x = Q->data;
        free(Q);
        Q = NULL;
    }
    else
    {
        s = Q->next; //让s和首元素的位置一样
        x = s->data;
        Q->next = s->next; //链接
        free(s);           //释放
    }
    return 1;
}