数据结构-实验4-循环队列的实现和运算

《算法设计与分析》实验报告-1-1、实验目的（1)掌握队列“先进先出”的特点；（2)复习队列的入队、出对、插入、删除等基本操作；（3)掌握循环队列的特点，以及循环队列的应用。2、实验内容（1)在顺序存储结构上实现输出受限制的双端循环队列的入队和出队（只允许队头输出）算法；（2)设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在对头，否则插入在队尾；（3)循环队列数据类型：#defineMAXLEN10typedefstruct{intdata[MAXLEN];Intfront,rear;}csequeue;（4)入队作业处理的预计时间可以用随机函数rand()产生，也可以从键盘输入。3、实验要求（1)用C（C++）语言完成算法设计和程序设计。（2)上机调试通过实验程序。（3)输入数据，检验程序运行结果。（4)给出具体的算法分析，包括时间复杂度和空间复杂度等。（5)撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。4、实验步骤与源程序⑴实验步骤先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，其中，需要设计一个主函数来实现菜单的输出，设计另外五个函数来求分别实现初始化队列，入队，出队，显示，求队列长度，最后，串接函数，并调试程序，在调试的时候，我先进行入队操作，输入9个数据之后，程序显示队满，不能入队，然后开始出队操作，输出9个数字之后，程序显示队空，再进行入队，显示队中的各个元素，并求队长，多次调试后，发现没有问题，得出实验结果，并截图。⑵源代码#includestdio.h#defineMAXLEN10typedefstruct{intdata[MAXLEN];//定义数据的类型intfront,rear;//定义队头、队尾指针}csequeue;csequeueq;《算法设计与分析》实验报告-2-voidIniQueue()//初始化队列{q.front=q.rear=MAXLEN-1;}voidInQueue()//入队函数{intx;printf(\n\t\t输入一个入队的整数数据：);scanf(%d,&x);if(q.front==(q.rear+1)%MAXLEN){printf(\n\t\t队满，不能入队!\n);return;}q.rear=(q.rear+1)%MAXLEN;q.data[q.rear]=x;printf(\n\t\t入队成功!\n);}voidOutsequeue()//出队函数{if(q.front==q.rear){printf(\n\t\t此队列为空!);return;}//队空不能出队else{q.front=(q.front+1)%MAXLEN;printf(\n\t\t出队元素为：%d\n,q.data[q.front]);//输出队头元素return;}}voidShowQueue()//显示函数{intk=q.front;if(k==q.rear){printf(\n\t\t此队列为空!\n);return;}printf(\n\t\t此队列元素为：);do{k=(k+1)%MAXLEN;printf(%4d,q.data[k]);}while(k!=q.rear);《算法设计与分析》实验报告-3-printf(\n);}intlength(){intk;k=(q.rear-q.front+MAXLEN)%MAXLEN;returnk;}voidmain()//主函数{inti=1;intchoice;IniQueue();while(i){printf(\n\t\t循环队列\n);printf(\n\t\t***********************************************);printf(\n\t\t*1----------进队*);printf(\n\t\t*2----------出队*);printf(\n\t\t*3----------显示*);printf(\n\t\t*4----------求队列长度*);printf(\n\t\t*0----------返回*);printf(\n\t\t***********************************************);printf(\n\n\t\t请选择菜单号:);scanf(%d,&choice);switch(choice){case1:InQueue();break;case2:Outsequeue();break;case3:ShowQueue();break;case4:printf(\n\t\t队列长度为:%d\n,length());break;case0:i=0;break;}}《算法设计与分析》实验报告-4-}5、测试数据与实验结果（可以抓图粘贴）（1）菜单显示：（2）入队：（3）队满（已入队9个元素）：（4）出队：（5）队空（已出队9个元素）：（6）显示队中的元素：《算法设计与分析》实验报告-5-（7）求队长：6、结果分析与实验体会本次实验是参考了范例程序，经过自己的改写，从而实现要求。先做简单的输出，一步步的再做其它格式的设置。在实验的过程中，我加深了对队列各种操作的理解，因为队列是“先进先出”的操作受限制的线性表，一般队列只允许在队尾进行插入操作，在队头进行删除操作，元素之间存在一对一的关系，本程序的设计过程也是对前面线性表知识的巩固。再者，用链式存储结构实现这个程序，实际上是设计一个带有头指针（front）和尾指针（rear）的单向链表，此单向链表没有头结点，头尾指针指的是同一个单向链表中的首尾结点，所以，从链队列的整体结构考虑，一般讲这两个指针封装在一个结构体中。队列是一种应用广泛的数据结构，凡具有其特点的需要排队处理的问题，都可以使用它来处理。