数据结构--循环队列的c语言实现(超详细注释/实验报告)
队列(Queue)是另一种限定性的线性表,它只允许再表的一端插入元素,而再另一端删除元素,多以队列具有先进先出(First In First Out,FIFO)的特性。这与我们日常生活中的排队是一样的,最早进入队列的人最早离开,新来的人总是加入到队尾。在队列中,允许插入的一端称队尾(Rear),允许删除的一端则称为队头(Front)。队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业
数据结构–循环队列的c语言实现(超详细注释/实验报告)
知识小回顾
队列(Queue)是另一种限定性的线性表,它只允许再表的一端插入元素,而再另一端删除元素,多以队列具有先进先出(First In First Out,FIFO)的特性。这与我们日常生活中的排队是一样的,最早进入队列的人最早离开,新来的人总是加入到队尾。在队列中,允许插入的一端称为队尾(Rear),允许删除的一端则称为队头(Front)。
队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中,同时有几个作业在运行。如果运行的结果都需要通过通道输出,那么就要按请求输出的先后次序排队。凡是申请输出的作业都从队尾进入队列。
循环队列是队列的一种顺序表示和实现方法。与顺序栈类似,在队列的顺序存储结构中,用一组地址连续的存储单元依次存放从队头到队尾的元素。此外,由于队列中队头和队尾的位置都是动态变化的,因此需要附设两个指针front和rear,分别知识队头元素和队尾元素在数组中的位置。
普通的顺序队列会有假溢出,一个巧妙的办法就是将顺序队列的数组看成一个环状的空间,即规定最后一个单元的后继为第一个单元,我们形象地称之为循环队列。
实验题目
实现循环队列基本运算
实验目的
- 掌握队列的逻辑结构和操作规则,能在相应的实际问题中正确选用。
- 熟练掌握循环队列基本运算的实现
实验要求
- 以循环队列作为存储结构;
- 实现循环队列的建立;
- 实现循环队列的入队运算;
- 实现循环队列的出队运算。
实验内容和实验步骤
1.需求分析
以菜单的形式作为用户与程序的接口,用户输入菜单号来实行相应的操作。
2. 概要设计
设计几个函数来实现初始化、插入、删除和查找的功能,然后再主函数中调用函数来实现操作。
3. 详细设计
导入一些库,并定义队列的大小以及队列中元素的类型。
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MAXSIZE 50//队列最大长度
循环队列类型定义如下
typedef int QueueElementType;
typedef struct
{
QueueElementType element[MAXSIZE];//队列的元素空间(一个数组)
int front;//头指针(指示器)
int rear;//尾指针(指示器)
}SeqQueue;
循环队列初始化操作
//循环队列初始化操作
SeqQueue*InitQueue()
{
//将Q初始化为一个空的循环队列
SeqQueue *Q;
Q=(SeqQueue*)malloc(sizeof(SeqQueue));
Q->front=Q->rear=0;//一开始两个指示器都在最前面
return Q;
}
循环队列入队操作
- 在非空循环队列中,队头指针始终指向当前队头元素,而队尾指针始终指向真正队尾与那苏后面的单元。当队列空间被占满时,队尾指针追上队头指针,所以有:front=rear。反之,队列是空的时候,队头指针追上队尾指针,此时也有:front=rear。可见,只凭front=rear无法判断队列是“满”还是“空”。解决这个问题的办法就是:损失一个元素,当队尾指针所指向的空单元的后继单元是队头元素所在的单元时,则停止入队。
//循环队列入队操作
void EnterQueue(SeqQueue *Q,QueueElementType x)
{
//printf("入队开始\n");
if((Q->rear+1)%MAXSIZE==Q->front)//牺牲了一个空间
{
printf("循环队列已满");
}
else
{
//printf("入队else开始\n");
Q->element[Q->rear]=x;
Q->rear=(Q->rear+1)%MAXSIZE;
}
//printf("入队结束\n");
}
循环队列出队操作
//循环队列出队操作
void DeleteQueue(SeqQueue *Q)
{
if(Q->front==Q->rear)
{
printf("队列为空");
}
else
{
Q->front=(Q->front+1)%MAXSIZE;
}
}
循环队列显示操作
//循环队列显示操作
void DisplayQueue(SeqQueue *Q)
{
//printf("display开始\n");
int i;
for(i=Q->front;i!=Q->rear;i=(i+1)%MAXSIZE)
{
printf("%d ",Q->element[i]);
}
//printf("display结束\n");
}
主函数部分,用一种“菜单”的形式使线性表的操作更加地清晰地展示出来。
//主函数
int main()
{
SeqQueue *Q;
//InitQueue(Q);
Q=InitQueue();
int a,i=1,x;
for(a=1;a<5;a++)
{
EnterQueue(Q,a);
}
//DisplayQueue(Q);
system("cls");
while(i)//保证一直进行
{
printf("当前的循环队列如下(队首->队尾):\n");
DisplayQueue(Q);
printf("\n------------------------------------\n");
printf(" Main Menu \n");
printf(" 1 进队 \n");
printf(" 2 出队 \n");
printf(" 3 清屏 \n");
printf(" 0 结束程序 \n");
printf("------------------------------------\n");
printf("请输入你选择的菜单号<1, 2, 3, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
printf("请输入进队元素:");
scanf("%d",&x);
EnterQueue(Q,x);
printf("\n\n");
break;
case 2:
DeleteQueue(Q);
printf("\n\n");
break;
case 3:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("输入有误~\n");
break;
}
}
}
4. 调试分析
遇到的问题及解决方法
- 教材上的初始化操作报错,用来实验指导书上的代码后就没有报错了。
算法的时空分析
- 循环链表比较简单,都是依托着数组来实现的,所以整体难度不大,最多也就一层循环
实验结果
实验结果很不错,所有操作都能正常执行,并且自己加入了“清屏”选项,使得界面更加的整洁。
实验总结
循环链表比较简单,多多重复,百炼成钢!
最后附上完整的代码
#include<stdio.h>
#include<stdlib.h>
//#include<malloc.h>
#define MAXSIZE 50//队列最大长度
typedef int QueueElementType;
typedef struct
{
QueueElementType element[MAXSIZE];//队列的元素空间(一个数组)
int front;//头指针(指示器)
int rear;//尾指针(指示器)
}SeqQueue;
//循环队列初始化操作
//void InitQueue(SeqQueue * Q)
SeqQueue*InitQueue()
{
//将Q初始化为一个空的循环队列
SeqQueue *Q;
Q=(SeqQueue*)malloc(sizeof(SeqQueue));
Q->front=Q->rear=0;//一开始两个指示器都在最前面
return Q;
}
//循环队列入队操作
void EnterQueue(SeqQueue *Q,QueueElementType x)
{
//printf("入队开始\n");
if((Q->rear+1)%MAXSIZE==Q->front)//牺牲了一个空间
{
printf("循环队列已满");
}
else
{
//printf("入队else开始\n");
Q->element[Q->rear]=x;
Q->rear=(Q->rear+1)%MAXSIZE;
}
//printf("入队结束\n");
}
//循环队列出队操作
void DeleteQueue(SeqQueue *Q)
{
if(Q->front==Q->rear)
{
printf("队列为空");
}
else
{
Q->front=(Q->front+1)%MAXSIZE;
}
}
//循环队列显示操作
void DisplayQueue(SeqQueue *Q)
{
//printf("display开始\n");
int i;
for(i=Q->front;i!=Q->rear;i=(i+1)%MAXSIZE)
{
printf("%d ",Q->element[i]);
}
//printf("display结束\n");
}
//主函数
int main()
{
SeqQueue *Q;
//InitQueue(Q);
Q=InitQueue();
int a,i=1,x;
for(a=1;a<5;a++)
{
EnterQueue(Q,a);
}
//DisplayQueue(Q);
system("cls");
while(i)//保证一直进行
{
printf("当前的循环队列如下(队首->队尾):\n");
DisplayQueue(Q);
printf("\n------------------------------------\n");
printf(" Main Menu \n");
printf(" 1 进队 \n");
printf(" 2 出队 \n");
printf(" 3 清屏 \n");
printf(" 0 结束程序 \n");
printf("------------------------------------\n");
printf("请输入你选择的菜单号<1, 2, 3, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
printf("请输入进队元素:");
scanf("%d",&x);
EnterQueue(Q,x);
printf("\n\n");
break;
case 2:
DeleteQueue(Q);
printf("\n\n");
break;
case 3:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("输入有误~\n");
break;
}
}
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)