数据结构上机实验报告.doc

数据结构上机实验报告 实习题目 【问题描述】 假设某银行有四个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正空闲，则可上前办理业务，反之，若四个窗口均有客户所占，他便会排在人数最少的队伍后面。现在需要编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。 【实现要求】 假设模拟数据已按客户到达的先后顺序依次存入到数据文件中，对应每位客户有两个数据，即到达时间和需要办理业务的时间。 需求分析 为了计算这个平均时间，我们自然需要掌握每个客户到达银行和离开银行这两个时刻，后者减去前者即为每个客户在银行的逗留时间。所有客户逗留时间的总和被一天内进入银行的客户数除便是所求的平均时间。 概要设计 分析需求可得，我们有两类事件处理：一类是客户到达事件，另一类是客户离开时间，因为前一类事件是自然发生的，而后以类事件是由客户处理事务所需时间和等待时间而决定，因为是有先后之分，所以事件表应是有序表，其主要操作是插入和删除事件。 而客户排队需要用队列来处理（QNode），因为有四个窗口，因此需要四个队列（LinkQueue q[5];）,队列中有关客户的主要信息是客户到达时刻和办理业务所需要的时间typedef struct QNode{ int ArrivaTime，Duration; struct QNode *next; }QNode; 由以上可见，我们只需要两种数据类型：有序表和队列。 然后先处理客户到达事件，因为客户到达银行是随机的，因此我们需要在客户到达事件发生时需先产生两个随即数，其一为此时到达的客户办理业务所需时间durtime，其二为下一个客户将到达的时间间隔intertime(durtime=rand()%25)，假设当前事件发生时刻occurtime(intertime=rand()%24)，则下一个客户到达的时刻为occurtime+intertime,由此应产生新的客户到达事件表，刚到达的客户则应插入当前所含元素最少的队列中，在此时则需要得到每只队列的长度（Status QueueLength()）然后判断并且得到最短队列（int MinQueue（）），则还应产生一个客户离开事件的插入表。 接着再处理客户离开事件，首先计算该用户在银行逗留的时间，然后从队列中删除该客户（（Status DelFirst()））后查看队列是否空（Status ListEmpty()），若不空则设定一个新的队头客户离开事件。 因为还需设定结束的条件，由此我们定义CloseTime； 详细设计 EventList ev; //事件表 Event en; //事件 LinkQueue q[5]; //四个客户队列 QNode customer; //客户记录 int TotalTime,CustomerNum; //累计客户逗留时间，客户数 int durtime,intertime,CloseTime=100;LinkQueue q[5]; void OpenForDay() { //初始化操作 TotalTime=0; //初始化累计时间 CustomerNum=0; //初始化客户数为0 InitList(); //初始化事件链表为空表 en.OccurTime=0, en.NType=0; //设定第一个客户到达事件 OrderInsert(ev); //插入事件表 int i; //置空队列 for(i=1;i=4;i++) InitQueue(q[i]); } void CustomerArrived() { //处理客户到达事件 int t,i; static int c=1; ++CustomerNum; //记录客户数 durtime=rand()%25; //生成随机时间 intertime=rand()%24; t=en.OccurTime+intertime; //下个客户到达时刻 if(tCloseTime) { en.NType=0; en.OccurTime=t; OrderInsert(ev); } i=MinQueue(q); //求长度最短队列 EnQueue(q[i],en.OccurTime,durtime); printf(\n%2d%12d%19d\n,c++,en.OccurTime,durtime); if(QueueLength(q[i])==1) { en.NType=i;