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

1、肇庆学院 计算机学院/软件学院 实 验 报 告专业 15物联网工程 班级 1班 姓名 林忠杰 学号 1 课程名称 数据结构 学年20152016 学期 1R / 2 课程类别 专业必修R 限选 任选 实践评分： 批阅老师： 2016年 12 月 6 日实验3 栈的基本操作l 实验目的（1） 熟悉栈的定义和栈的基本操作。（2） 掌握顺序存储栈和链接存储栈的基本运算。（3） 加深对栈结构的理解，逐步培养解决实际问题的编程能力。l 实验内容（1） 基础题（1） 编写栈的基本操作函数。（2） 调用栈的基本操作函数完成栈的基本操作：建立栈、读取栈顶函数、从栈中删除元素、输出栈中的所有元素。（2） 提高题

2、编写一个判定表达式中的括号是否正确匹配的函数。l 实验结果1、基础题（1）画出数据结构基本运算的流程图主函数输入操作选择op1进栈2出栈0退出调用push函数调用pop函数调用OutputStack函数输出操作结果（2） 程序运行主要结果截图测试用例：依次输入元素34，43，56，45进栈，程序运行结果如下图测试用例：让元素45,56出栈，程序运行结果如下图（3） 程序源代码#include#define max 10int push(int *stack,int maxn,int *toppt,int x)if(*toppt=maxn)return 1;stack*toppt=x;+(*to

3、ppt);return 0;int pop(int *stack,int *toppt,int *cp)if(toppt=0)return 1;-(*toppt);*cp=stack*toppt;return 0;void OutputStack(int *stack,int toppt)int i;for(i=toppt-1;i=0;i-)printf(%d ,stacki);printf(n);void main()int smax,i;int top=0;int op;while(1)printf(请选择操作，1:进栈；2:出栈；0:退出n);fflush(stdin);scanf(%d

4、,&op);switch(op)case 0: return;case 1:printf(请输入进栈元素：);scanf(%d,&i);if(push(s,max,&top,i)=0)printf(进栈成功，栈内元素为：n);OutputStack(s,top);elseprintf(栈满n);break;case 2:if(pop(s,&top,&i)=0)printf(出栈元素为：%d,栈内元素为：n,i);OutputStack(s,top);elseprintf(栈空n);break;主函数gets(exp)读取表达式Strcmp(exp,”0”)=0?退出调用correct函数输出结

5、果2、提高题（1）画出数据结构基本运算的流程图 否是（2） 程序运行主要结果截图测试用例：输入表达式 () ，程序运行结果如图测试用例：输入表达式 () ，程序运行结果如图（3） 程序源代码#include#include#include#define MAX 100int push(int *stack,int maxn,int *toppt,char x) if(*toppt=maxn) return 1; stack*toppt=x; +(*toppt); return 0;int pop(int *stack,int *toppt,char *cp) if(toppt=0) retur

6、n 1; -(*toppt); *cp=stack*toppt; return 0;int correct(char *exp,int max)int flag=0;char sMAX;int top=0;char c;int i;for(i=0;i=max&flag=0;i+)if(expi=(|expi=|exp=)push(s,MAX,&top,expi);if(expi=)|expi=|expi=)flag=pop(s,&top,&c);if(expi=)&c!=()|(expi=&c!=)|(expi=&c!=)flag=1;if(top!=0)flag=1;return flag;

7、void main()char exp1024;int top=0;while(1)printf(请输入表达式，输入0 结束程序：n);gets(exp);expMAX=0;if(strcmp(exp,0)=0)return;if(correct(exp,strlen(exp)!=0)printf(表达式括号不匹配n);elseprintf(表达式括号匹配n);实验4 队列的基本操作l 实验目的（1） 掌握链接存储队列的进队和出队等基本操作。（2） 掌握环形队列的进队和出队等基本操作。（3）加深对队列结构的理解，逐步培养解决实际问题的编程能力。l 实验内容（1） 基础题1（1） 编写链接队列的

8、基本操作函数。（2） 调用上述函数实现下列操作：建立队列、读取队列的第一个元素、从队列中删除元素、输出队列中的所有元素。（2） 基础题2（1） 编写环形队列的基本操作函数。（2）调用上述函数完成下列操作：建立队列、读取队列的第一个元素、从队列中删除元素、输出队列中的所有元素。（3） 提高题使用队列结构对医务室事件进行模拟，输出医生的总等待时间和病人的平均等待时间。l 实验结果1、基础题1（1）画出数据结构基本运算的流程图主函数Switch(op)1进队2出队0退出调用EnQueue函数调用DeQueue函数调用OutputQueue函数输出操作结果（2） 程序运行主要结果截图测试用例：依次输入

9、元素23,34,43,56,45进入队列，程序运行结果如图测试用例：让元素23,34出队，程序运行结果如图（3） 程序源代码#include#includetypedef struct queue int data; struct queue *link;Q;void EnQueue(Q *head,Q *tail,int x)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;int DeQueue(Q *head,Q *hail,in

10、t *cp)Q *p;p=*head;if(*head=NULL)return 1;*cp=(*head)-data;*head=(*head)-link;if(*head=NULL)*hail=NULL;free(p);return 0;void OutputQueue(Q *head)while(head!=NULL)printf(%d ,head-data);head=head-link;printf(n);int main()Q *head,*tail;int op,i;head=tail=NULL;while(1)printf(请选择操作，1:进队；2:出队；0:退出n);fflus

11、h(stdin);scanf(%d,&op);switch(op)case 0:return 0;case 1:printf(n请输入进队元素：);scanf(%d,&i);EnQueue(&head,&tail,i);printf(队内元素为：);OutputQueue(head);printf(n);break;case 2:if(DeQueue(&head,&tail,&i)=0)printf(n出队元素为：%dn队内元素为：,i);OutputQueue(head);printf(n);elseprintf(队空nn);break;2、基础题2（1）画出数据结构基本运算的流程图主函数S

12、witch(op)1进队2出队0退出调用EnQueue函数调用DeQueue函数调用OutputQueue函数输出操作结果（2） 程序运行主要结果截图测试用例：依次输入入队元素34,67,45,56，程序运行结果如图测试用例：让元素34,67出队，程序运行结果如图（3） 程序源代码#include#include#define MAXN 5int EnQueue(int *queue,int maxn,int *head,int *tail,int x)if(*tail+1)%maxn=*head)return 1;*tail=(*tail+1)%maxn;queue*tail=x;retur

13、n 0;int DeQueue(int *queue,int maxn,int *head,int *tail,int *cp)if(*head=*tail)return 1;*head=(*head+1)%maxn;*cp=queue*head;return 0;void OutputQueue(int *queue,int maxn,int h,int t)while(h!=t)h=(h+1)%maxn;printf(%d ,queueh);printf(n);int main()int qMAXN;int qh=0,qt=0;int op,i;while(1)printf(请选择操作，1

14、:进队 2:出队 0:退出n);fflush(stdin);scanf(%d,&op);switch(op)case 0:return 0;case 1:printf(请输入进队元素：);scanf(%d,&i);if(EnQueue(q,MAXN,&qh,&qt,i)!=0)printf(队列满n);elseprintf(入队成功，队内元素为：n);OutputQueue(q,MAXN,qh,qt);break;case 2:if(DeQueue(q,MAXN,&qh,&qt,&i)=0)printf(出队元素为：%d ,队内元素为：n,i);OutputQueue(q,MAXN,qh,qt

15、);elseprintf(队空n);break;3、 提高题 （1）画出数据结构基本运算的流程图主函数输入病人总数n n = 0 ?n20申请内存调用InitData函数生成病人到达及处理时间的随机数列i0?dwait+=pi.arrive-nowtime调用EnQueue函数 nowtime=pi.arrive调用DeQueue函数pwait+=nowtime-curr.arrviefinish=nowtime+curr.treatin&pi.arrive=finish?调用EnQueue函数nowtime=finish是否是否 否是 否是 是否 否 是（2） 程序运行主要结果截图测试用例：

16、输入病人人数为13，程序运行结果如图测试用例：输入病人人数为5，程序运行结果如图测试用例：分别输入病人人数为21，-4，0，程序运行结果如图（3） 程序源代码#include#include#includetypedef structint arrive,treat;PA;typedef struct queuePA data;struct queue *link;QE;void Enqueue(QE *head,QE *tail,PA x)QE *p;p=(QE*)malloc(sizeof(QE);p-data=x;p-link=NULL;if(*head=NULL)*head=*tail

17、=p;else(*tail)-link=p;*tail=p;int Dequeue(QE *head,QE *tail,PA *cp)QE *p;p=*head;if(*head=NULL)return 1;*cp=(*head)-data;*head=(*head)-link;if(*head=NULL)*tail=NULL;free(p);return 0;void Outputqueue(QE *head)while(head!=NULL)printf(到达时间：%d 处理时间：%dn,head-data.arrive,head-data.treat);head=head-link;vo

18、id Initdata(PA *pa,int n)int parr=0;int i;for(i=0;i20|n0)continue;if(p=(PA*)malloc(n*sizeof(PA)=NULL)printf(内存申请错误n);return 0;Initdata(p,n);for(i=0;i0)dwait+=pi.arrive-nowtime;nowtime=pi.arrive;Enqueue(&head,&tail,pi+);Dequeue(&head,&tail,&curr);pwait+=nowtime-curr.arrive;finish=nowtime+curr.treat;while(in&pi.arrive=finish)Enqueue(&head,&tail,pi+);nowtime=finish;free(p);printf(医生等待时间为 %d