数据结构实验报告(实验3,实验4)

肇庆学院计算机学院/软件学院实验报告专业15物联网工程班级1班姓名林忠杰学号201524134151课程名称数据结构学年2015—2016学期1/2□课程类别专业必修限选□任选□实践□评分：批阅老师：2016年12月6日实验3栈的基本操作实验目的（1）熟悉栈的定义和栈的基本操作。（2）掌握顺序存储栈和链接存储栈的基本运算。（3）加深对栈结构的理解，逐步培养解决实际问题的编程能力。实验内容（一）基础题（1）编写栈的基本操作函数。（2）调用栈的基本操作函数完成栈的基本操作：建立栈、读取栈顶函数、从栈中删除元素、输出栈中的所有元素。（二）提高题编写一个判定表达式中的括号是否正确匹配的函数。实验结果1、基础题（1）画出数据结构基本运算的流程图主函数输入操作选择op1进栈2出栈0退出调用push函数调用pop函数调用OutputStack函数输出操作结果（2）程序运行主要结果截图测试用例：依次输入元素34，43，56，45进栈，程序运行结果如下图测试用例：让元素45,56出栈，程序运行结果如下图（3）程序源代码#includestdio.h#definemax10intpush(int*stack,intmaxn,int*toppt,intx){if(*toppt=maxn)return1;stack[*toppt]=x;++(*toppt);return0;}intpop(int*stack,int*toppt,int*cp){if(toppt==0)return1;--(*toppt);*cp=stack[*toppt];return0;}voidOutputStack(int*stack,inttoppt){inti;for(i=toppt-1;i=0;i--)printf(%d,stack[i]);printf(\n);}voidmain(){ints[max],i;inttop=0;intop;while(1){printf(请选择操作，1:进栈；2:出栈；0:退出\n);fflush(stdin);scanf(%d,&op);switch(op){case0:return;case1:printf(请输入进栈元素：);scanf(%d,&i);if(push(s,max,&top,i)==0){printf(进栈成功，栈内元素为：\n);OutputStack(s,top);}elseprintf(栈满\n);break;case2:if(pop(s,&top,&i)==0){printf(出栈元素为：[%d],栈内元素为：\n,i);OutputStack(s,top);}elseprintf(栈空\n);break;}}}2、提高题（1）画出数据结构基本运算的流程图否是（2）程序运行主要结果截图测试用例：输入表达式([][](()))，程序运行结果如图测试用例：输入表达式[][[]()，程序运行结果如图（3）程序源代码#includestdio.h#includestdlib.h#includestring.h#defineMAX100intpush(int*stack,intmaxn,int*toppt,charx){if(*toppt=maxn)return1;stack[*toppt]=x;++(*toppt);return0;}intpop(int*stack,int*toppt,char*cp){if(toppt==0)return1;--(*toppt);主函数gets(exp)读取表达式Strcmp(exp,”0”)=0?退出调用correct函数输出结果*cp=stack[*toppt];return0;}intcorrect(char*exp,intmax){intflag=0;chars[MAX];inttop=0;charc;inti;for(i=0;i=max&&flag==0;i++){if(exp[i]=='('||exp[i]=='['||exp=='{')push(s,MAX,&top,exp[i]);if(exp[i]==')'||exp[i]==']'||exp[i]=='}'){flag=pop(s,&top,&c);if((exp[i]==')'&&c!='(')||(exp[i]==']'&&c!='[')||(exp[i]=='}'&&c!='{'))flag=1;}}if(top!=0)flag=1;returnflag;}voidmain(){charexp[1024];inttop=0;while(1){printf(请输入表达式，输入0结束程序：\n);gets(exp);exp[MAX]='\0';if(strcmp(exp,0)==0)return;if(correct(exp,strlen(exp))!=0)printf(表达式括号不匹配\n);elseprintf(表达式括号匹配\n);}}实验4队列的基本操作实验目的（1）掌握链接存储队列的进队和出队等基本操作。（2）掌握环形队列的进队和出队等基本操作。（3）加深对队列结构的理解，逐步培养解决实际问题的编程能力。实验内容（一）基础题1（1）编写链接队列的基本操作函数。（2）调用上述函数实现下列操作：建立队列、读取队列的第一个元素、从队列中删除元素、输出队列中的所有元素。（二）基础题2（1）编写环形队列的基本操作函数。（2）调用上述函数完成下列操作：建立队列、读取队列的第一个元素、从队列中删除元素、输出队列中的所有元素。（三）提高题使用队列结构对医务室事件进行模拟，输出医生的总等待时间和病人的平均等待时间。实验结果1、基础题1（1）画出数据结构基本运算的流程图主函数Switch(op)1进队2出队0退出调用EnQueue函数调用DeQueue函数调用OutputQueue函数输出操作结果（2）程序运行主要结果截图测试用例：依次输入元素23,34,43,56,45进入队列，程序运行结果如图测试用例：让元素23,34出队，程序运行结果如图（3）程序源代码#includestdio.h#includemalloc.htypedefstructqueue{intdata;structqueue*link;}Q;voidEnQueue(Q**head,Q**tail,intx){Q*p;p=(Q*)malloc(sizeof(Q));p-data=x;p-link=NULL;if(*head==NULL)*head=*tail=p;else{(*tail)-link=p;*tail=p;}}intDeQueue(Q**head,Q**hail,int*cp){Q*p;p=*head;if(*head==NULL)return1;*cp=(*head)-data;*head=(*head)-link;if(*head==NULL)*hail=NULL;free(p);return0;}voidOutputQueue(Q*head){while(head!=NULL){printf(%d,head-data);head=head-link;}printf(\n);}intmain(){Q*head,*tail;intop,i;head=tail=NULL;while(1){printf(请选择操作，1:进队；2:出队；0:退出\n);fflush(stdin);scanf(%d,&op);switch(op){case0:return0;case1:printf(\n请输入进队元素：);scanf(%d,&i);EnQueue(&head,&tail,i);printf(队内元素为：);OutputQueue(head);printf(\n);break;case2:if(DeQueue(&head,&tail,&i)==0){printf(\n出队元素为：%d\n队内元素为：,i);OutputQueue(head);printf(\n);}elseprintf(队空\n\n);break;}}}2、基础题2（1）画出数据结构基本运算的流程图（2）程序运行主要结果截图测试用例：依次输入入队元素34,67,45,56，程序运行结果如图主函数Switch(op)1进队2出队0退出调用EnQueue函数调用DeQueue函数调用OutputQueue函数输出操作结果测试用例：让元素34,67出队，程序运行结果如图（3）程序源代码#includestdio.h#includemalloc.h#defineMAXN5intEnQueue(int*queue,intmaxn,int*head,int*tail,intx){if((*tail+1)%maxn==*head)return1;*tail=(*tail+1)%maxn;queue[*tail]=x;return0;}intDeQueue(int*queue,intmaxn,int*head,int*tail,int*cp){if(*head==*tail)return1;*head=(*head+1)%maxn;*cp=queue[*head];return0;}voidOutputQueue(int*queue,intmaxn,inth,intt){while(h!=t){h=(h+1)%maxn;printf(%d,queue[h]);}printf(\n);}intmain(){intq[MAXN];intqh=0,qt=0;intop,i;while(1){printf(请选择操作，1:进队2:出队0:退出\n);fflush(stdin);scanf(%d,&op);switch(op){case0:return0;case1:printf(请输入进队元素：);scanf(%d,&i);if(EnQueue(q,MAXN,&qh,&qt,i)!=0)printf(队列满\n);else{printf(入队成功，队内元素为：\n);OutputQueue(q,MAXN,qh,qt);}break;case2:if(DeQueue(q,MAXN,&qh,&qt,&i)==0){printf(出队元素为：%d,队内元素为：\n,i);OutputQueue(q,MAXN,qh,qt);}elseprintf(队空\n);break;}}}3、提高题（1）画出数据结构基本运算的流程图是否是否否是否是是否否是主函数输入病人总数nn=0?n0或n20申请内存调用InitData函数生成病人到达及处理时间的随机数列in||head!=NULL退出输出结果，医生等待时间和病人平均等待时间head==NULL?p[i].arrive-nowtime0?dwait+=p[i].arrive-nowtime调用EnQueue函数nowtime=p[i].arrive调用DeQueue函数pwait+=nowtime-curr.arrviefinish=nowtime+curr.treatin&&p[i].arrive=finish?调用EnQueue函数nowtime=finish（2）程序运行主要结果截图测试用例：输入病人人数为13，程序运行结果如图测试用例：输入病人人数为5，程序运行结果如图测试用例：分别输入病人人数为21，-4，0，程序运行结果如图（3）程序源代码#includestdio.h#includestdlib.h#includemalloc.htypedefstruct{intarrive,treat;}PA;typedefstructqueue{PAdata;structqueue*link;}QE;voidEnqueue(QE**head,QE**tail,PAx){QE*p;p=(QE*)malloc(sizeof(QE));p-data=x;p-li