| 数据结构 | 您所在的位置：网站首页 › 循环队列的队满条件 › 数据结构 |
数据结构
|
数据结构–循环队列的c语言实现（超详细注释/实验报告）
知识小回顾
队列（Queue)是另一种限定性的线性表，它只允许再表的一端插入元素，而再另一端删除元素，多以队列具有先进先出（First In First Out,FIFO)的特性。这与我们日常生活中的排队是一样的，最早进入队列的人最早离开，新来的人总是加入到队尾。在队列中，允许插入的一端称为队尾（Rear），允许删除的一端则称为队头（Front）。 队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业在运行。如果运行的结果都需要通过通道输出，那么就要按请求输出的先后次序排队。凡是申请输出的作业都从队尾进入队列。 循环队列是队列的一种顺序表示和实现方法。与顺序栈类似，在队列的顺序存储结构中，用一组地址连续的存储单元依次存放从队头到队尾的元素。此外，由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针front和rear，分别知识队头元素和队尾元素在数组中的位置。 普通的顺序队列会有假溢出，一个巧妙的办法就是将顺序队列的数组看成一个环状的空间，即规定最后一个单元的后继为第一个单元，我们形象地称之为循环队列。 实验题目实现循环队列基本运算 实验目的 掌握队列的逻辑结构和操作规则，能在相应的实际问题中正确选用。熟练掌握循环队列基本运算的实现 实验要求 以循环队列作为存储结构；实现循环队列的建立；实现循环队列的入队运算；实现循环队列的出队运算。 实验内容和实验步骤 1.需求分析 以菜单的形式作为用户与程序的接口，用户输入菜单号来实行相应的操作。 2. 概要设计 设计几个函数来实现初始化、插入、删除和查找的功能，然后再主函数中调用函数来实现操作。 3. 详细设计导入一些库，并定义队列的大小以及队列中元素的类型。 #include #include #include #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"); }主函数部分，用一种“菜单”的形式使线性表的操作更加地清晰地展示出来。 实验结果很不错，所有操作都能正常执行，并且自己加入了“清屏”选项，使得界面更加的整洁。 实验总结循环链表比较简单，多多重复，百炼成钢！ 最后附上完整的代码 #include #include //#include #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 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("请输入你选择的菜单号:\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; } } } |
【本文地址】
公司简介
联系我们