循环队列的实现与运算

1、电子信息学院实验报告书课程名：数据结构题目：循环队列的实现和运算实验类别设计班级：BX1001学号：101003020141姓名：赵艳2011年10月10日1、实验题目(1)掌握队列“先进先出”的特点；(2)复习队列的入队、出队、插入、删除等基本运算。(3)掌握循环队列的特点，以及循环队列的应用。2、实验内容(1) 在顺序存储结构上实现输出受限制的双端循环队列的入队和出队(只允许队头输出)算法。(2) 设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于对头和队尾作业的平均时间，则插入在队头，否则插入在队尾。(3) 循环

2、队列数据类型：#defineMAXLEN10typedefstructintdataMAXLEN;intfront,rear;csequeue;(4)入队作业处理的预计执行时间可以用随机数函数rand()产生，也可以从键盘输入。3、实验要求(1) 利用C(C+)语言完成算法设计和程序设计。(2) 上机调试通过实验程序。(3) 输入数据，检验程序运行结果。(4) 给出具体的算法分析，包括时间复杂度和空间复杂度等。(5) 撰写实验报告。4、实验步骤与源程序实验步骤首定义MAXLEN=10然后初始化队列，再定义数据类型、头、尾指针。下面定义五个函数，分别是入队函数、出队函数、显示函数和长度计算函数。

3、在入队时要判断是否队满，队满不能入队。出队要判断队是否为空，队空不能出队。判断队列长度的函数，用队尾指针与队首指针之差来计算。最后的主函数是一个队列菜单和相应的对函数的调用，菜单界面主要通过printf()函数来实现，下面一一对应有switch()语句来实现。源代码#include<stdio.h>#defineMAXLEN10typedefstructintdataMAXLEN;/定义数据的类型intfront,rear;/定义队头、队尾指针csequeue;csequeueq;voidIniQueue()/q.front=q.rear=MAXLEN-1;)voidInQueue

4、()/intx;printf("ntt输入一个入队的整数数据：");scanf("%d",&x);if(q.front=(q.rear+1)%MAXLEN)printf("ntt队满，不能入队！n");return;q.rear=(q.rear+1)%MAXLEN;q.dataq.rear=x;printf("ntt入队成功！n");voidOutsequeue()/if(q.front=q.rear)printf("ntt此队列为空！");return;/else初始化队列入队函数出队

5、函数队空不能出队q.front=(q.front+1)%MAXLEN;printf("ntt出队元素为：%dn",q.dataq.front);/return;输出队头元素voidShowQueue()/显示函数intk=q.front;if(k=q.rear)printf("ntt此队列为空!n");return;printf("ntt此队列元素为：");dok=(k+1)%MAXLEN;printf("%4d",q.datak);while(k!=q.rear);intlength()intk;k=(q.rea

6、r-q.front+MAXLEN)%MAXLEN;returnk;voidmain()/主函数inti=1;intchoice;IniQueue();while(i)printf("ntt循环队列n");printf("ntt*1显示*"printf("ntt*2进队*"printf("ntt*3出队*"printf("ntt*4求队列长度*"printf("ntt*0返回*");););););printf("ntt*");printf("nt

7、t*");printf("nntt请选择菜单号：");scanf("%d",&choice);switch(choice)case 1: ShowQueue();break;case 2: InQueue();break;case 3: Outsequeue();break;case4:printf("ntt队列长度为：%dn",length();break;case0:i=0;break;算法设计与分析实验报告-4-)5、测试数据与实验结果(可以抓图粘贴)12340队队-回长列队进出显求返请选择菜单号：1循环队列IIIK-MW队队一回长列12340请选择菜单号:3此队列元素为工【心队队一长列进出显求返12340请选择菜单号;4队列长度为：36、结果分析与实验体会程序可以运行，结果正确，在实验中是对五个函数的调用，我在实验中更清楚的认识到队列跟栈的不同，队列是先进先出，栈是后进先出。但这个程序只有对一个元素的处理，入队、出队、显示、求长度，出栈后队列长度为00进队是通过把新元素插入队尾，出队是输出队头元素。我再次加深了入队要判断栈满，用语句q.front=(q.rear+1)%MAXLEN判断，入队有两种输入方法，队首和队尾。出队要判断队是否为空，用语句q.front=q.rear判断。如果不判断，会