自主實验四循环队列的实现和运算.doc

电子信息学院 实验报告书 课程名： 数据结构 题 目： 循环队列的实现和运算 实验类别 设计 班 级： BX1206 学 号： 23 姓 名： 张善干 2013年 11 月 4 日 实验题目 复习C（或C++）语言的基本描述方法； 掌握结构体及数组的用法； 提高运用C（C++）语言解决问题的能力； 通过实验程序，分析它们的时间复杂度。 实验内容 在顺序存储结构上实现输出受限制的双端循环队列的入队和出队。（只允许对头输出）的算法。 设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业原则，若一个新提交的作业的预计时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。 循环队列数据类型： #define MAXLEN 10 typedef struct { int data[MAXLEN]; int front,rear; }csequeue; 入队作业处理的预计执行时间可以用随机函数rand()产生，也可以从键盘输入。 实验要求 利用C（C++）语言完成程序设计。 上机调试通过实验程序。 输入数据，检验程序运行结果。 给出具体的算法分析，包括时间复杂度和空间复杂度。 撰写实验报告。 实验步骤与源程序 ⑴ 实验步骤 首先是在自己的本子上，编写自己设计的程序。 之后将它输入到电脑上，并调试。 发现问题后，改写程序，使之达到要求。 录入数据，进行检验。 撰写实验报告。 ⑵ 源代码 #includestdio.h #define MAXLEN 10 typedef struct { int data[MAXLEN]; int front,rear; }csequeue; void InitQueue(csequeue q) { q.front=MAXLEN-1; q.rear=MAXLEN-1; } int IsEmpty(csequeue q) { if(q.rear==q.front) return 1; else return 0; } int IsFull(csequeue q) { if((q.rear+1)%MAXLEN==q.front) return 1; else return 0; } int InrQueue(csequeue q,int x) { if(IsFull(q)) { printf(队满!); return 0; } else { q.rear=(q.rear+1)%MAXLEN; q.data[q.rear]=x; return 1; } } void InfQueue(csequeue q,int x) { int i; if (q.front==(q.rear+1) % MAXLEN ) { printf(\n\t\t 队满，不能入队! \n); return; } q.data[q.front--]=x; printf(元素成功插入队首 %d\n,q.data[q.front+1]); } int OutQueue(csequeue q,int x) { if(IsEmpty(q)) { printf(对空!); return 0; } else { q.front=(q.front+1)%MAXLEN; x=q.data[q.front]; return 1; } } void ShowQueue(csequeue q) { int k=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); printf(\n); } void main() { csequeue q; InitQueue(q); int a[8]; int i,k,ave; for(i=0;i8;i++) { scanf(%d,a[i]); InrQueue(q,a[i]); } printf(当前队列为: \n); ShowQueue(q);