循环队列的实现与运算

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

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

3、，分别 是入队函数、出队函数、显示函数和长度计算函数。在入队时要判断是否队满，队满不能入队。出 队要判断队是否为空，队空不能出队。判断队列长度的函数，用队尾指针与队首指针之差来计算。最后的主函数是一个队列菜单和相应的对函数的调用，菜单界面主要通过printf （）函数来实现,下面一一对应有switch （）语句来实现。源代码#in clude<stdio.h>#defi ne MAXLEN 10typedef struct int dataMAXLEN;/定义数据的类型算法设计与分析实验报告-# -算法设计与分析实验报告-2 -int fron t,rear;/定义队头、队尾指针算

4、法设计与分析实验报告-3 -csequeue;csequeue q;初始化队列void Ini Queue()/ q.fro nt=q.rear=MAXLEN-1;入队函数void In Queue()/ int x ;prin tf("ntt输入一个入队的整数数据：");scan f("%d"，& x);if (q.fro nt=(q.rear+1) % MAXLEN ) printf("ntt队满，不能入队！ n”)； return; q.rear=(q.rear+1) % MAXLEN;q.dataq.rear=x;prin tf

5、("nttvoid Outsequeue() if (q.fron t=q.rear) printf ("ntt入队成功！ n");/此队列为空! "); return ;/出队函数队空不能出队算法设计与分析实验报告-# -算法设计与分析实验报告-# -else q.fro nt=(q .fron t+1) % MAXLEN;prin tf("ntt出队元素为：%dn",q.dataq.fro nt); /输出队头元素算法设计与分析实验报告-# -算法设计与分析实验报告-5 -return;显示函数void ShowQueue()/

6、int k=q.fr ont;此队列为空！ n"); return;此队列元素为：");if (k=q.rear) prin tf("nttprin tf("nttdo k=(k+1)%MAXLEN;prin tf("%4d",q.datak); while(k!=q.rear);prin tf("n");int len gth() int k;k=(q.rear-q.fro nt+MAXLEN)% MAXLEN;return k;void main()/主函数 int i=1;int choice;Ini Que

7、ue();while (i)prin tf("ntt循环队列n");prin tf("ntt* *");prin tf("ntt*");prin tf("ntt*");prin tf("ntt*");prin tf("ntt*");prin tf("ntt*");prin tf("ntt* *");prin tf("nntt请选择菜单号：”);scan f("%d",&choice); switch

8、(choice)case 1: ShowQueue(); break;case 2: In Queue(); break;case 3: Outsequeue(); break;case 4: prin tf("ntt队列长度为：%d n",length();break;case 0: i=0; break;5、测试数据与实验结果（可以抓图粘贴）循环队列12 3 4 0队队-回长列队进出显求返请选择菜单号：1输入一个入队的整数数据；1循坏队列12 3 4 0H H H 丹仔K-MK-MT 丹叶算法设计与分析实验报告-# -算法设计与分析实验报告-# -请选择菜单号：3此队列

9、元素为乂1 13循环队列算法设计与分析实验报告-# -算法设计与分析实验报告-# -三二队队-$!回长列进出显求返12 3 4 0M w M M M二二沁算法设计与分析实验报告-6 -请选择菜单号：4 队列长度为：36、结果分析与实验体会程序可以运行，结果正确，在实验中是对五个函数的调用，我在实验中更清楚的 认识到队列跟栈的不同，队列是先进先出，栈是后进先出。但这个程序只有对一个元 素的处理，入队、出队、显示、求长度，出栈后队列长度为0。进队是通过把新元素插入队尾，出队是输出队头元素。我再次加深了入队要判断栈满，用语句q.fro nt=（q.rea叶1）% MAXLEW断，入队有两种输入方法，队首和队尾。出队要判断队是否为空，用语句q.fro nt=q.