首页天道酬勤c语言数据结构链式队列,c语言实现循环队列

c语言数据结构链式队列,c语言实现循环队列

张世龙 05-06 11:32 45次浏览

简单的书代码已经上传到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

循环队列图解,循环队列是队列的一种