实验4循环队列的实现与运算..doc

电子信息学院 实验报告书 课程名： 数据结构 题 目： 循环队列的实现和运算 实验类别 设计 班 级： BX1001 学 号： 101003020141 姓 名： 赵艳 2011年10 月 10日实验题目 掌握队列 “先进先出”的特点； 复习队列的入队、出队、插入、删除等基本运算。 掌握循环队列的特点，以及循环队列的应用。 实验内容 在顺序存储结构上实现输出受限制的双端循环队列的入队和出队（只允许队头输出）算法。 设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于对头和队尾作业的平均时间，则插入在队头，否则插入在队尾。 循环队列数据类型： #define MAXLEN 10 typedef struct { int data[MAXLEN]; int front,rear; }csequeue; (4)入队作业处理的预计执行时间可以用随机数函数rand()产生，也可以从键盘输入。 实验要求 利用C（C++）语言完成算法设计和程序设计。 上机调试通过实验程序。 输入数据，检验程序运行结果。 给出具体的算法分析，包括时间复杂度和空间复杂度等。 撰写实验报告。 实验步骤与源程序 ⑴ 实验步骤 首定义MAXLEN=10，然后初始化队列，再定义数据类型、头、尾指针。下面定义五个函数，分别是入队函数、出队函数、显示函数和长度计算函数。在入队时要判断是否队满，队满不能入队。出队要判断队是否为空，队空不能出队。判断队列长度的函数，用队尾指针与队首指针之差来计算。最后的主函数是一个队列菜单和相应的对函数的调用，菜单界面主要通过printf（）函数来实现，下面一一对应有switch（）语句来实现。 ⑵ 源代码 #includestdio.h #define MAXLEN 10 typedef struct { int data[MAXLEN]; // 定义数据的类型 int front,rear; // 定义队头、队尾指针 }csequeue; csequeue q; void IniQueue() // 初始化队列 { q.front=q.rear=MAXLEN-1; } void InQueue() // 入队函数 { int x ; 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); } void Outsequeue() // 出队函数 { 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; } } void ShowQueue() // 显示函数 { int k=q.front; if (k==q.rear) { printf(\n\t\t 此队列为空! \n); return;} printf(\n\t\t 此队列元素为：); do { k=(k+1)%