搜索
数据结构实验报告实验名称：实验五队列的基本操作一、实验目的：1、掌握链接存储队列的进队和出队等基本操作2、掌握环行队列的进队和出队等基本操作3、加深对队列结构的理解，逐步培养解决实际问题的编程能力二、实验环境：计算机，同学，vc++三、实验内容和要求：（一）基础题1、编写链接队列的基本操作函数(１)EnQueue(QUEUE**head,QUEUE**tail,intx)进队操作(２)DeQueue(QUEUE**head,QUEUE**tail,int*cp)出队操作(３)OutputQueue(QUEUE*head)输出队列中元素2、调用上述函数实现下列操作，操作步骤如下：（1）调用进队函数建立一个队列；（2）读取队列的第一个元素；（3）从队列中删除元素；（4）输出队列中所有元素。。注：每完成一个步骤，必须及时输出队列中元素，便于观察操作结果。3、编写环型队列的基本操作函数(１)EnQueue(int*queue,intmaxn,int*head,int*tail,intx)进队操作,返回1:队满(２)DeQueue(int*queue,intmaxn,int*head,int*tail,int*cp)出队操作返回1:队空(３)OutputQueue(int*queue,intmaxn,inth,intt)输出队列中元素4、调用上述函数实现下列操作，操作步骤如下：（1）调用进队函数建立一个队列；（2）读取队列的第一个元素；（3）从队列中删除元素；（4）输出队列中所有元素。四、实验步骤：从网上把word下载下来，认真的看题目，思考和同学讨论在老师的帮助下，完成了题目。五、实验结果与分析（含程序、数据记录及分析和实验总结等）：基础题一#includestdio.h#includealloc.htypedefstructqueue{/*定义队列结构*/intdata;/*队列元素类型为int*/structqueue*link;}QUEUE;voidEnQueue(QUEUE**head,QUEUE**tail,intx)/*进队操作*/{QUEUE*p;p=(QUEUE*)malloc(sizeof(QUEUE));p-data=x;p-link=NULL;/*队尾指向空*/if(*head==NULL)/*队首为空，即为空队列*/*head=*tail=p;else{(*tail)-link=p;/*新单元进队列尾*/*tail=p;/*队尾指向新入队单元*/}}intDeQueue(QUEUE**head,QUEUE**tail,int*cp)/*出队操作1:对空*/{QUEUE*p;p=*head;if(*head==NULL)/*队空*/return1;*cp=(*head)-data;*head=(*head)-link;if(*head==NULL)/*队首为空，队尾也为空*/*tail=NULL;free(p);/*释放单元*/return0;}voidOutputQueue(QUEUE*head)/*输出队列中元素*/{while(head!=NULL){printf(%d,head-data);head=head-link;}printf(\n);}voidmain(){QUEUE*head,*tail;intop,i;head=tail=NULL;/*将队列头和尾置为空*/while(1){printf(请选择操作，1：进队2：出队0：退出);fflush(stdin);/*清空标准输入缓冲区*/scanf(%d,&op);switch(op){case0:/*退出*/return0;case1:/*进队*/printf(请输入进队元素：);scanf(%d,&i);EnQueue(&head,&tail,i);printf(队内元素为:\n);OutputQueue(head);break;case2:/*出队*/if(DeQueue(&head,&tail,&i)==0){/*出队成功*/printf(出队元素为:[%d],队内元素为:\n,i);OutputQueue(head);}elseprintf(队空\n);break;}}}基础题二#includestdio.h#includealloc.h#defineMAXN11/*定义环行顺序队列的存储长度*/intEnQueue(int*queue,intmaxn,int*head,int*tail,intx)/*进队操作,返回1:队满*/{if((*tail+1)%maxn==*head)/*队尾指针赶上队首指针,队满*/return1;*tail=(*tail+1)%maxn;/*队尾指针+1*/queue[*tail]=x;/*元素入对尾*/return0;}intDeQueue(int*queue,intmaxn,int*head,int*tail,int*cp)/*出队操作返回1:队空*/{if(*head==*tail)/*队首=队尾,表明队列为空*/return1;*head=(*head+1)%maxn;/*队首指针+1*/*cp=queue[*head];/*取出队首元素*/return0;}voidOutputQueue(int*queue,intmaxn,inth,intt)/*输出队列中元素*/{while(h!=t){/**/h=(h+1)%maxn;printf(%d,queue[h]);}printf(\n);}voidmain(){intq[MAXN];/*假设环行队列的元素类型为int*/intq_h=0,q_t=0;/*初始化队首,队尾指针为0*/intop,i;while(1){printf(请选择操作，1：进队2：出队0：退出);fflush(stdin);/*清空标准输入缓冲区*/scanf(%d,&op);switch(op){case0:/*退出*/return0;case1:/*进队*/printf(请输入进队元素：);scanf(%d,&i);if(EnQueue(q,MAXN,&q_h,&q_t,i)!=0)printf(队列满\n);else{printf(入队成功,队内元素为:\n);OutputQueue(q,MAXN,q_h,q_t);}break;case2:/*出队*/if(DeQueue(q,MAXN,&q_h,&q_t,&i)==0){/*出队成功*/printf(出队元素为:[%d],队内元素为:\n,i);OutputQueue(q,MAXN,q_h,q_t);}elseprintf(队空\n);break;}}}提高题一#includestdio.h#includestdlib.h#includealloc.htypedefstruct{intarrive;/*病人到达时间*/inttreat;/*病人处理时间*/}PATIENT;typedefstructqueue{/*定义队列结构*/PATIENTdata;/*队列元素类型为int*/structqueue*link;}QUEUE;voidEnQueue(QUEUE**head,QUEUE**tail,PATIENTx)/*进队操作*/{QUEUE*p;p=(QUEUE*)malloc(sizeof(QUEUE));p-data=x;p-link=NULL;/*队尾指向空*/if(*head==NULL)/*队首为空，即为空队列*/*head=*tail=p;else{(*tail)-link=p;/*新单元进队列尾*/*tail=p;/*队尾指向新入队单元*/}}intDeQueue(QUEUE**head,QUEUE**tail,PATIENT*cp)/*出队操作1:对空*/{QUEUE*p;p=*head;if(*head==NULL)/*队空*/return1;*cp=(*head)-data;*head=(*head)-link;if(*head==NULL)/*队首为空，队尾也为空*/*tail=NULL;free(p);/*释放单元*/return0;}voidOutputQueue(QUEUE*head)/*输出队列中元素*/{while(head!=NULL){printf(到达时间:[%d]处理时间:[%d]\n,head-data.arrive,head-data.treat);head=head-link;}}voidInitData(PATIENT*pa,intn)/*生成病人到达及处理时间的随机数列*/{intparr=0;/*前一个病人到达的时间*/inti;for(i=0;in;i++){pa[i].arrive=parr+rand(15);/*假设病人到达的时间间隔为0~14*/pa[i].treat=rand(9)+1;/*假设医生处理时间为1~9*/parr=pa[i].arrive;printf(第[%d]个病人到达时间为[%d]处理时间为[%d]\n,i+1,parr,pa[i].treat);}}voidmain(){QUEUE*head,*tail;PATIENT*p,curr;/*病人到达及处理时间信息,当前出队病人信息*/intn,i,finish;intnowtime;/*时钟*/intdwait,pwait;/*医生累计等待时间,病人累计等待时间*/head=tail=NULL;/*将队列头和尾置为空*/while(1){n=0;nowtime=dwait=pwait=0;printf(请输入病人总数(1~20),=0：退出);scanf(%d,&n);if(n==0)/*退出*/return0;if(n20||n0)continue;if((p=(PATIENT*)malloc(n*sizeof(PATIENT)))==NULL){printf(内存申请错误\n);return1;}InitData(p,n);/*生成病人到达及处理时间的随机数列*/for(i=0;in||head!=NULL;){/*病人到达未结束或还有等待,处理*/if(head==NULL){/*等待队列为空*/if(p[i].arrive-nowtime0)/*病人到达时间与上次处理时间迟*/dwait+=p[i].arrive-nowtime;/*累计医生等待时间*/nowtime=p[i].arrive;/*时钟推进*/EnQueue(&head,&tail,p[i++]);/*病人入队*/}DeQueue(&head,&tail,&curr);/*出队一位病人*/pwait+=nowtime-curr.arrive;/*累计病人等待时间*/finish=nowtime+curr.treat;/*当前病人处理结束时间*/while(in&&p[i].arrive=finish)/*下一位病人到达时间在当前病人等待时间结束之前,入队*/EnQueue(&head,&tail,p[i++]);nowtime=finish;/*时钟推进到当前病人处理结束时间*/}free(p);/*释放空间*/printf(医生等待时间[%d],病人平均等待时间[%.2f]\n,dwait,(float)pwait/n);}}六：思考题：七、教师评语：实验成绩：教师：（签名要全称）年月日注：1。此模板为专业实验报告的基本要求，若有特殊要求的实验，可在此模板基础上增加，但不可减少。２．实验报告必须在学生提交报告后一星期内批改。说明：①上下页边距改成2厘米，左边距为2.0厘米，右边距为1.5厘米。②表格位置为居中