循环队列的实现与运算 数据结构.doc

电子信息学院实验报告书课程名： 数据结构 题 目： 循环队列的实现和运算 实验类别 设计 班 级： 学 号： 姓 名： 2011年10 月 17 日 算法设计与分析 实验报告 - 5 -1、 实验题目（1) 掌握队列 “先进先出”的特点；（2) 复习队列的入队、出队、插入、删除等基本运算。（3) 掌握循环队列的特点，以及循环队列的应用。2、 实验内容（1） 在顺序存储结构上实现输出受限制的双端循环队列的入队和出队（只允许队头输出）算法。（2） 设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于对头和队尾作业的平均时间，则插入在队头，否则插入在队尾。（3） 循环队列数据类型：#define MAXLEN 10typedef struct int dataMAXLEN; int front,rear;csequeue; (4)入队作业处理的预计执行时间可以用随机数函数rand()产生，也可以从键盘输入。3、 实验要求（1） 利用C（C+）语言完成算法设计和程序设计。（2） 上机调试通过实验程序。（3） 输入数据，检验程序运行结果。（4） 给出具体的算法分析，包括时间复杂度和空间复杂度等。（5） 撰写实验报告。4、 实验步骤与源程序 实验步骤 首定义MAXLEN=10，然后初始化队列，再定义数据类型、头、尾指针。下面定义五个函数，分别是入队函数、出队函数、显示函数和长度计算函数。在入队时要判断是否队满，队满不能入队。出队要判断队是否为空，队空不能出队。判断队列长度的函数，用队尾指针与队首指针之差来计算。最后的主函数是一个队列菜单和相应的对函数的调用，菜单界面主要通过printf（）函数来实现，下面一一对应有switch（）语句来实现。 源代码#include#define MAXLEN 10typedef struct int dataMAXLEN; / 定义数据的类型 int front,rear; / 定义队头、队尾指针csequeue;csequeue q; void IniQueue() / 初始化队列 q.front=q.rear=MAXLEN-1; void InQueue() / 入队函数 int x ; 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); void Outsequeue() / 出队函数 if (q.front=q.rear) printf (ntt 此队列为空! ); return ; / 队空不能出队 else q.front=(q.front+1) % MAXLEN; printf(ntt 出队元素为：%dn,q.dataq.front); / 输出队头元素 return; void ShowQueue() / 显示函数 int k=q.front; if (k=q.rear) printf(ntt 此队列为空! n); return; printf(ntt 此队列元素为：); do k=(k+1)%MAXLEN; printf(%4d,q.datak); while(k!=q.rear); printf(n);int length() int k; k=(q.rear-q.front+MAXLEN)% MAXLEN; return k;void main() / 主函数 int i=1; int choice; IniQueue(); while (i) printf(ntt 循 环 队 列n);printf(ntt*);printf(ntt* 1-显 示 *);printf(ntt* 2-进 队 *);printf(ntt* 3-出 队 *); printf(ntt* 4-求 队 列 长 度 *);printf(ntt* 0-返 回 *);printf(ntt*);printf(nntt 请选择菜单号: );scanf(%d,&choice);switch(choice) case 1: ShowQueue(); break; case 2: InQueue(); break; case 3: Outsequeue(); break; case 4: printf(ntt 队列长度为: %d n,length();break; case 0: i=0; break; 5、 测试数据与实验结果（可以抓图粘贴） 6、 结果分析与实验体会程序可以运行，结果正确，在实验中是对五个函数的调用，我在实验中更清楚的认识到队列跟栈的不同，队列是先进先出，栈是后进先出。但这个程序只有对一个元素的处理，入队、出队、显示、求长度，出栈后队列长度为0。进队是通过把新元素插入队尾，出队是输出队头元素。我再次加深了入队要判断栈满，用语句q.front=(q.rear+1) % MAXLEN判断，入队有两种输入方法，队首和队尾。出队要判断队是否为空，用语句q.front=q.rear判断。如果不判断，会影响程序运行，也会