c语言数据结构链式队列,c语言实现循环队列
简单的书代码已经上传到GitHub上了。 单击以去GitHub查看代码
有关队列的APP应用程序已更新：杨辉三角
如果有错误，请务必在信息中指出会忘记的期待！
一.队列是什么？
与堆栈的特性相反，队列是先进先出(FIFO )的线性表。 队列只允许在表的一端插入，而在另一端允许删除操作。
在队列中，允许插入操作的一侧称为队列末尾(rear )，允许删除操作的一侧称为队列开头(front )。
如果队列Q=(A1、a2、a3、a4 )，则a1是团队领导元素，a4是团队领导元素。 a1也是第一个进入队列的元素，a4是刚刚插入的元素。 因此，插入顺序为a1、a2、a3、a4，删除顺序为a4、a3、a2、a1。
队列--图像源网络
2 .如何实现顺序存储结构的队列？
一摸队伍，心里就想：“这还不简单吗？ 不是和前面的顺序堆栈一样吗？ 只是删除操作改变了方向.但是，开始写之后.就像这样：
吓一跳
？ 如果直接为队列分配一定的存储空间，然后退出队列入队……整个队列一直向前移动……可能会浪费以前分配的空间，容易引起内存溢出。
那之后，脑袋发光了，我每次出队都把整个队伍往后挪不就行了吗？ 我带着兴趣慢慢地去写了。 准备刚开始，我又想了一下。 每次删除元素时，时间的复杂性是o(n )。 一定有更好的解决方法。 嗯，是循环队列。
当队伍的末尾移动到队列空间的末尾时，接下来我们移动到队伍的头部，就相当于连接队伍的末尾和队伍的头部。 这将充分利用无法用于移动的空间。
3 .队列结构定义：
需要保存队列空间地址的基址
需要两个表示索引的整数front、rear，访问第一个团队的末尾
定义如下。
类型定义结构{
//初始化空间基地址
QElemtype *base；
//团队领导指针
int front；
//小组表指针
int rear；
} sq队列；
重点是从这里开始，这是循环队列中必须完成的基本操作
真滑稽
四.队列基本操作：
初始化队列：
分配空间并为团队领导的末尾索引分配值
//队列初始化
statusinitqueue(sqqueueq ) {
q.base=(qelemtype* ) malloc ) sizeof (qelemtype ) ) * MAXQSIZE )；
if (！ Q.base
打印机(错误： initsqueuefail (n )；
返回溢出；
}
//初始队列的先头队的末尾指向base
Q.front=Q.rear=0；
返回确定；
}
销毁队列：
释放空间并为base分配空值
最好避免二次空间释放
//销毁队列
statusdestroyqueue(sqqueueq ) {
free(q.base )；
Q.base=NULL；
返回确定；
}
清空队列：
先头队末尾的索引可以是0
//清空队列
statusclearqueue(sqqueueq ) {
Q.front=Q.rear=0；
返回确定；
}
判断队列是否为空的：
队列的第一个索引==队列的末尾索引为空
//判断是否为空
statusqueueempty(sqqueueq ) {
return Q.front==Q.rear？ 真：假；
}
获取队列长度：
因为是循环队列，所以末尾的地址不一定比末尾的地址大
实际长度必须为队列的“空间大小”
//获取队列长度
intqueueLength(sqqueueq ) {
//循环队列Q.rear - Q.front可能是负的
return((q.rear-q.frontmaxqsize ) % MAXQSIZE )；
}
6 .获得团队领导要素：
//获得团队领导要素
Statusgethead(SQqueueq，QElemtype e ) {
//如果不为空，则返回队列头元素
if(q.rear！=Q.front
>e = Q.base[Q.front];
return OK;
}
printf("error: SqQueue is Empty\n");
return ERROR;
}
队尾插入元素：
插入前判断队列是否已满
插入后更新队尾索引(记住这是个循环队列)
// 队尾插入元素
Status EnQueue(SqQueue& Q, QElemtype e){
//对列满
if((Q.rear + 1) % MAXQSIZE == Q.front)
return ERROR;
// 插入元素
Q.base[Q.rear] = e;
//更新队尾
Q.rear = (Q.rear + 1) % MAXQSIZE;
return OK;
}
删除队头元素：
重点和7点类似
// 删除队头元素
Status DeQueue(SqQueue& Q, QElemtype& e){
//空对列
if(Q.front == Q.rear)
return ERROR;
// 用e返回队头
e = Q.base[Q.front];
// 更新队头
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
9.遍历队列：
// 从队头到队尾visit遍历
Status QueueTraverse(SqQueue Q, void (*visit)(QElemtype)){
//空对列
if(Q.front == Q.rear)
return ERROR;
for(int i = Q.front ;i != Q.rear ; i = (i + 1) % MAXQSIZE){
visit(Q.base[i]);
}
return OK;
}
都是套路
五.循环队列的应用
再这里不得不又写到约瑟夫问题了：线性表解法
因为循环队列的特性(先进先出)，这时候我们只要在计数的同时，删除队头元素，添加至队尾，就可以实现了。
#include "SqQueue.h"
int main(){
int n, m;
scanf("%d %d", &n, &m);
SqQueue q;
InitQueue(q);
//赋值(编号)
for(int i = 1 ; i <= n ; ++i){
EnQueue(q, i);
}
int count = 0, e = 0;
while(QueueLength(q) > 1){
//如果数到m，删除队头元素
if(++count % m == 0){
DeQueue(q, e);
//否则将队头元素删除，添加至队尾
}else{
DeQueue(q, e);
EnQueue(q, e);
}
}
GetHead(q, e);
DestroyQueue(q);
printf("num: %d\n", e);
return 0;
}
另外，有兴趣的话可以看看约瑟夫问题的数学解法。比较n大了这样写还是没有数学解法来的高效：约瑟夫环数学解法
六.完整代码：
#include
#include
//最大队列长度
#define MAXQSIZE 100
//定义状态
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define True 1
#define False 0
typedef int QElemtype;
typedef int Status;
typedef struct{
// 初始化空间基址
QElemtype *base;
// 队头指针
int front;
// 队尾指针
int rear;
}SqQueue;
// 初始化队列
Status InitQueue(SqQueue& Q){
Q.base = (QElemtype*)malloc(sizeof(QElemtype) * MAXQSIZE);
if(!Q.base){
printf("error: InitSqQueue fail\n");
return OVERFLOW;
}
// 初始队列队头队尾指向base
Q.front = Q.rear = 0;
return OK;
}
// 销毁队列
Status DestroyQueue(SqQueue& Q){
free(Q.base);
Q.base = NULL;
return OK;
}
// 清空队列
Status ClearQueue(SqQueue& Q){
Q.front = Q.rear = 0;
return OK;
}
// 判断是否为空
Status QueueEmpty(SqQueue& Q){
return Q.front == Q.rear ? True : False;
}
// 获取队列长度
int QueueLength(SqQueue Q){
// 循环队列Q.rear - Q.front可能为负
return ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);
}
// 获得队头元素
Status GetHead(SqQueue Q, QElemtype& e){
// 非空则返回队头元素
if(Q.rear != Q.front){
e = Q.base[Q.front];
return OK;
}
printf("error: SqQueue is Empty\n");
return ERROR;
}
// 队尾插入元素
Status EnQueue(SqQueue& Q, QElemtype e){
//对列满
if((Q.rear + 1) % MAXQSIZE == Q.front)
return ERROR;
// 插入元素
Q.base[Q.rear] = e;
//更新队尾
Q.rear = (Q.rear + 1) % MAXQSIZE;
return OK;
}
// 删除队头元素
Status DeQueue(SqQueue& Q, QElemtype& e){
//空对列
if(Q.front == Q.rear)
return ERROR;
// 用e返回队头
e = Q.base[Q.front];
// 更新队头
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
// 从队头到队尾visit遍历
Status QueueTraverse(SqQueue Q, void (*visit)(QElemtype)){
//空对列
if(Q.front == Q.rear)
return ERROR;
for(int i = Q.front ;i != Q.rear ; i = (i + 1) % MAXQSIZE){
visit(Q.base[i]);
}
return OK;
}
每天进步一点，加油！
End
END