自主设计实验.docVIP

电子信息学院 实验报告书 课程名： 数据结构 题 目： 循环队列的实现和运算 实验类别 设计 班 级： BX1008 学 号： 35 姓 名： 张哲栋 2011年 9 月 20 日 1、 实验题目 （1) 复习C（或C++）语言的基本描述方法； （2) 掌握结构体及数组的用法； （3) 提高运用C（C++）语言解决问题的能力； （4) 通过实验程序，分析它们的时间复杂度。 2、 实验内容 （1） 在顺序存储结构上实现输出受限制的双端循环队列的入队和出队。（只允许对头输出）的算法。 （2） 设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业原则，若一个新提交的作业的预计时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。 （3） 循环队列数据类型： #define MAXLEN 10 typedef struct { int data[MAXLEN]; int front,rear; }csequeue; （4） 入队作业处理的预计执行时间可以用随机函数rand()产生，也可以从键盘输入。 3、 实验要求 （1） 利用C（C++）语言完成程序设计。 （2） 上机调试通过实验程序。 （3） 输入数据，检验程序运行结果。 （4） 给出具体的算法分析，包括时间复杂度和空间复杂度。 （5） 撰写实验报告。 4、 实验步骤与源程序 ⑴ 实验步骤 首先是在自己的本子上，编写自己设计的程序。 之后将它输入到电脑上，并调试。 发现问题后，改写程序，使之达到要求。 录入数据，进行检验。 撰写实验报告。 ⑵ 源代码 #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]); InrQ