数据结构课程设计大课.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,数据结构课程设计,数据结构课程设计,1,教学安排,2,设计题目,3,成绩评定,4,课程设计报告,5,研究性学习与创新性实验,1,1,教学安排,1-1,教学目的,1-2,计划学时,1-3,学习方式,1-4,教学过程,2,1,教学安排,教学目的,（,1,）全面落实课程教学大纲,（,2,）提升学生软件设计实践技能,（,3,）鼓励学生研究性学习,（,4,）鼓励学生创新性实验,3,1,教学安排,计划学时：,32,学时,课外自主学习：,32,学时,自主学习与计划学时比例：,1:1,4,1,教学安排,学习方式,（,1,）组建课程设计活动小组,（,2,）双向自愿选题,（,3,）课程实践（自主学习,+,调研）,（,4,）上机实践（技术讨论,+,调试）,（,5,）成果交流,5,1,教学安排,教学过程,总体分为两个阶段：,（,1,）综合训练阶段,（,2,）研究性学习与创新性实验阶段,循序渐进（重点）,逐步深入（扩展与提高）,6,1,教学安排,具体教学过程,（,1,）选题与开题,（,2,）方案设计,（总体设计,+,数据结构设计）,（,3,）详细设计（函数原型,+,算法设计）,（,4,）编程与调试,（,5,）结题与成果交流,7,2,设计题目,分为三类,A,类,综合训练性,B,类 应用研究性,C,类 创新设计性,8,3,成绩评定,综合评定,综合训练性 占60%,应用研究性 占,20%,创新设计性 占,20%,9,4,课程设计报告,设计报告内容,（,1,）课题背景,（,2,）可行性与需求分析,（,3,）总体设计,（,4,）详细设计,（,5,）程序实现,（,6,）软件测试,（,7,）总结,10,4,课程设计报告,设计报告格式,（,1,）封面,（,2,）任务书,（,3,）目录,（,4,）正文,（,5,）附录（源代码等）,11,5,研究性学习与创新性实验,设计题目举例,排队问题仿真,基于,STL,双端队列及应用,线段树及应用,12,排队问题仿真,排队问题,用队列结构可以模拟现实生活中的很多排队现象，如车站候车、医院候诊、银行排队等都可以通过程序进行仿真模拟，并由此预测客流等多种经营指标。例如理发店排队问题。,13,问题描述,假设理发店内设有,N,把理发椅，可同时为,N,位顾客进行理发。,顾客进门，可能有两种情况。,若当时理发店内尚有空闲理发椅，则该顾客可立即入座理发，他在店内的逗,留时间即为他理发所需时间；,排队问题仿真,14,否则需要排队候理，则他在店内的逗留时间应为他理发所需时间和排队等候的时间之和。,一旦有顾客理完发离去时，排在对头的顾客便开始理发。顾客的到达时间和理发所需时间均可随机生成，并约定，过了营业时间顾客不再进门，但仍需继续为已进入店内的顾客理发，直至最后一名顾客离开为止。,排队问题仿真,15,题目要求,编制一个事件驱动仿真程序以模拟理发店内一天的活动，要求输出在一天的营业时间内，到达的顾客人数、顾客在店内的平均逗留时间和排队等候理发的平均人数以及在营业时间内空椅子的平均数。,通过队列模拟理发店的排队现象，通过仿真办法评估理发店的营业状况。,排队问题仿真,16,排队问题仿真,需求分析,“事件驱动模拟”,为计算出每个顾客自进门到出门之间在理发馆内逗留的时间，只需要在顾客“进门”和“出门”这两个时刻进行模拟处理。,定义在这两个时刻内发生的事情为“事件”，整个仿真程序可以按事件发生的先后次序逐个处理事件，这种模拟的工作方式称为“事件驱动模拟”。,17,建立数据模型,-,数据结构设计,本题目需要两种数据结构：,链队列登录排队等候理发的顾客情,况，队列中的每个元素应包括顾客进门的时刻和理发所需的时间。,链表：登录顾客进门和出门的事件。表中的元素应包括事件类型，还应按事件发生的先后次序有序。,排队问题仿真,18,排队问题仿真,事件表数据类型定义,typedef,struct,/,数据域,int occurTime,;,/,事件发生时刻,char,NType,;,/,事件类型,ElemType,Event,;,typedef struct,Lnode /,链表结点,ElemType data;,struct,Lnode *next;,*Link,*Position;,19,排队问题仿真,事件链表结构定义,typedef,struct,Link head,tail;,/,头、尾指针,int length;,/,链表长度,Link,current;/,当前指针,Link List;,typedef LinkList EventList;,/,事件链表类型，定义为有序链表,20,等待队列定义,typedef struct,/,数据域,int arrivalTime,;,/,顾客到达时间,int duration;,/,顾客理发所需时间,QElemType;,typedef struct,Qnode /,链表结点,QElemType data;,struct,Qnode *next;,Qnode,*QueuePtr;,排队问题仿真,21,链队列结构,定义,typedef struct,QueuePtr front;/,头指针,QueuePtr rear;,/,尾指针,LinkQueue;,排队问题仿真,22,主算法设计,假设,进门事件类型,为,A,，出门事件类型,为,D,。,为便于按事件发生的先后次序顺序进行处理，事件表应按发生的“时刻”有序。,实际问题中，顾客进门的时刻和理发所需要的时间都是随机的。假设第一个顾客进门的时刻为,0,。之后每个顾客进门的时刻在前一个顾客进门时设定，即以两个顾客之间的时间间隔来确定下一个顾客的到达时间。,排队问题仿真,23,生成“顾客,理发所需时间,durtime和,“,下一顾客到达的时间间隔,intertime”,两,个,随机数,可从,C,语言的随机数函数得到。,假设当前事件发生的时刻为,occurtime,，则下一顾客进门事件发生的时刻则,为,occurtime,+intertime,。,该顾客在当前时刻开始理发，经过,durtime,时间之后便可离开理发馆，则应发生时刻为,occurtime+durtime,。,排队问题仿真,24,排队问题主算法描述,主算法是以处理,顾客进门事件,和,顾客离,开事件,为线索进行的。,void BarberShop_Simulation(int chairNum,int closeTime),/,理发店馆业务模拟,/,chatrNum,为假设的理发馆的,/,规模,closeTime,为营业时间,OpenForDay;,/,初始化,排队问题仿真,25,while MoreEvent do,EventDrived(OccurTime,EventType);,/,事件驱动,switch(EventType),case A:CustomerArrived;,break;,/,处理顾客到达事件,case D:CustomerDeparture;,break;,/,处理顾客离开事件,排队问题仿真,26,default:Invalid;,/switch,/while,CloseForDay;,/,计算平均逗留时间和排队的平均长度,/BarberShop_Simulation,排队问题仿真,27,主,算法详细,描述,BarberShop_Simulation,设定,事件表中的第一个元素；,置空队列；,while,（当事件表不空）,删除,事件表中发生时刻最早的元素；,if,（事件类型,=0,）,/,处理顾客进门,事件,累计顾客进门人数；,if,（下一个到达时刻,关门时刻）,进门事件插入事件表；,排队问题仿真,28,if,（有空闲理发椅）,新,出门事件插入事件表；,累计,顾客逗留时间；,else,当前顾客插入队尾；,累计队列长度；,/if,排队问题仿真,29,else,/,事件类型,=1,，处理顾客离开事件if,（队列不空）,删除队头元素；,记录顾客离开的最晚时间；,新出门事件插入事件表；,累计顾客逗留时间；,/if,/else,/while,排队问题仿真,30,计算平均队列长度；,计算平均逗留时间；,/BarberShop_Simulation,排队问题仿真,31,void,CustomerArrived(eventList evL,Queue Q,Event en),/,处理顾客进门事件,Random(durtime,intertime);,nextAT=en.occurTime+intertime;,/,下一顾客到达时刻，,evL,为事件表，表,/,中的第,1,个事件为,(0,A),。,durtime,为当,/,前进门的顾客理发所需时间，,intertime,/,为下一个顾客即将进门的间隔时间。,排队问题仿真,32,if(nextATcloseTime),newAEvent=(nextAT,A);,/,新的进门事件,MakeNode(newp,newAEvent);,LocateElem(evL,newAEvent,compare);,Insafter(evL,newp);,/,插入事件表,排队问题仿真,33,if(freeChair),/,顾客即刻开始理发，,freeChair,的初,/,值即为,chairNum,。,dT=en.occurTime+durtime;,newDEvent=(dT,D);,/,新的出门事件,MakeNode(newp,newDEvent);LocateElem(evL,newDEvent,compare);,排队问题仿真,34,Insafter(evL,newp);,/,插入事件表,totalTime+=durtime;,/,累计逗留时间，,TotalTime,、,/customerNum,和,totalQLength,的,/,初值均为,0,。,-freeChair;,排队问题仿真,35,else,/,顾客排队等候,newCustomer=(en.occuTime,durtime);,EnQueue(Q,newCustomer);,customerNum;,/,统计顾客总人数,totalQLength+=QueueLength(Q);,/,累计排队的长度,/CustomerArrived,排队问题仿真,36,void,CustomerDeparture(eventList evL,Queue Q,Event en),/,处理顾客出门事件,if(!DeQueue(Q,cm)+FreeChair;,/,无人等候理发,else /,排头顾客出列开始理发,dT=en.occurTime+cm.duration;,newDEvent=(dT,D);/,新的出门事件,排队问题仿真,37,MakeNode(newp,newDEvent);,LocateElem(evL,newDEvent,compare);,Insafter(evL,newp);,/,插入事件表,totalTime+=(dT-cm.arrivalTime);,/,累计逗留时间,排队问题仿真,38,totalFreeChair+=freeChair;,/,累计空椅数,/CustomerDeparture,排队问题仿真,39,主程序模块间调用关系,主程序模块,事件模块,队列模块,链表模块,排队问题仿真,40,主程序算法,void main(),/,全局变量定义,EventList ev;/,事件表,Event en;/,事件,LinkQueue Q;/,等候理发的顾客队列,QElemType customer;/,顾客记录,int,t2,t1,Totaltime,CustomerNum;,int,CloseTime,k,CurrentChair;,/,累计顾客逗留时间，顾客数,排队问题仿真,41,float Totallength;,int t=0;,OpenForDay();/,初始化,while(!ListEmpty(ev),DelFirst(ev,en);,if(en.NType=0),CustomerArrived();/,处理进门事件,else CustomerDeparture();/,处理离开事件,/while,排队问题仿真,42,cout“Number of customer,CustomerNumendl;,coutAverage time,Totaltime/CustomerNumendl;,/,求平均逗留时间,coutAverage queuelength“,Totallength/CustomerNumendl;,/,求平均的队列长度,/main,排队问题仿真,43,模拟运行,理发店有四个工作室，,Ntype=0,表示客户到达，,Ntype=1,2,3,4,表示在,1,号、,2,号、,3,号和,4,号理发室等待或理发。一对随机数（,a,b,），,a,表示理发需要的时间，,b,表示下一个客户到达的时间。,假设每个客户理发时间不超过,30,分钟；两个相邻到达理发店的客户的时间间隔不超过,5,分钟。模拟程序从第一个客户到达时间为“,o”,开始起运行。,排队问题仿真,44,初始状态,ev.first,为链表头指针。,删除事件表上第一个结点，得到,en.OccurTime=0,，,en.Ntype=0,；,排队问题仿真,45,状态,1,因为,en.Ntype=0,，则随即得到,两个随机效,(23,，,4),，生成一个下一客户到达的事件,(OccurTime=4,，,NTyPe=o),插入事件表；,排队问题仿真,46,状态,2,刚到的第一位客户排在第一个理发室等待的队列中,(ArrivalTime=0,，,Duration=23),，由于他是排头，故生成一个客户将离开的事件,(OccurTime=23,，,NType,1),插入事件表。,排队问题仿真,47,状态,3,删除事件表上第一个结点，因为,en.Ntype=0,仍是新客户到达事件，,en.OccurTime=4,，得到随机数为,(3,，,1),，则下一客户到达的时间为,OccurTime=4+1=5,；,排队问题仿真,48,状态,4,由于此时第二间理发室是空的，则刚到的第二位客户为第二个队列的队头,(ArrivalTime=4,，,Duration=3),，因而生成一个客户离开的事件,(OccurTime=7,，,Ntype=2),插入事件表排队问题仿真,49,状态,5,删除事件表上第一个结点，仍是新客户到达事件，,en.OccurTime=5,，得到随机数,(11,，,3),，则插入事件表的新事件为,(OccurTime=8,，,Ntype=0),；,排队问题仿真,50,状态,6,刚到的第三位客户成为第三个理发室队列的队头,(ArrivalTime=5,，,Duration=11),，因而插入事件表的新事件为,(OccurTime=16,，,Ntype=3),。,排队问题仿真,51,状态,7,删除事件表的第一个结点，因为,Ntype=2,，说明是第二个理发室的客户离开,en.OccurTime=7,，删去第二个理发室队列的队头，,ArrivalTime=4,，则他在理发店逗留的时间为,3,分钟。,排队问题仿真,52,状态,8,排队问题仿真,53,状态,9,排队问题仿真,54,状态,10,依次类推。,排队问题仿真,55,数据结构课程设计,学习、学习、,再学习！,56,