1、数据结构与算法报告Read数据结构与算法实验报告实验题目对于单跑道飞机场的模拟班级 1050310521姓名 黄林峰设计要求： 提出问题：1)程序目的：（1）模拟飞机在飞机场起飞和降落问题（2）统计跑道上飞机工作情况，包括起飞或降落飞机的数量及等待时间,以及没有起飞或降落的飞机数量、跑道的空闲时间2).程序功能： 模拟飞机在飞机场起飞和降落问题，以及统计跑道上飞机工作情况，包括起飞或降落飞机的数量及等待时间3）输入：机场运行的时间，和单位时间内起飞和降落的飞机的架数 4）输出：机场模拟的最终结果，包括用户输入的信息和模拟结束后统计得到的信息详情见Conclude函数问题分析：1）程序中的数据结
2、构：1）struct Plane： 其中有两个变量，其中一个是飞机的编号，编号与飞机为一一对应的关系，另外一个变量记录飞机进入队列的时间2）Queue *pl,*pt： 这是指向控制飞机降落和起飞的两个队列的两个指针，其中包括四个变量，队首front，队尾rear，记录队中元素个数从而知道等待起飞和等待降落的飞机的数量变量count，最后是用于储存降落和起飞飞机的两个队列，大小由事先定义的宏 MAXQUEUE指定。3）kind Action 枚举变量用于标定飞机的状态，ARRIVE为降落，DEPART为起飞。 2.)程序中的相关函数及其作用：1）NewPlane ：为一架新的飞机家里相关的数据
3、，并将nplanes加1。2）Refuse ：拒绝一架飞机提出的请求，由kind变量决定拒绝飞机的请求是降落还是起飞。3）Land ：处理一架降落的飞机，并记录相应的信息，包括现在的时间，降落飞机的架数和等待的时间。4）Fly ：处理一架起飞的飞机，并记录相应的信息，包括现在的时间，降落飞机的架数和等待的时间。5）Start：程序的初始化函数，同时包括了用户输入的必要信息，模拟的时间和单位时间内可以起飞和降落飞机的架数。6）Idle：记录机场为空，并记录下当前的时间，将机场为空的次数加一。7）Conclude：在模拟结束后，对相关信息进行统计，并打印相关的信息：包括飞机处理飞机的架数，降落飞机
4、的架数，起飞飞机的架数，拒绝请求的飞机的架数，起飞飞机等待的时间，降落飞机等待的时间，空闲的时间，结束的时间等模拟的信息8）Randomize：产生一个伪随机数。 9）PoissonRandom ：模拟Poisson分布。返回Poisson分布下，一定概率下所对应的整数值。10）UserSayYes：确定用户是否继续运行程序，继续，则返回1，不继续，返回0。队列系列函数：10） CreateQueue ：创建一个队列，并初始化为空。 11） Queuefull：用来判断队列是否为满，若队列满，返回1；否则返回0。12) Queueempty：用来判断队列是否为空，若队列空，返回1；否则返回0。
5、13) Queuesize：返回队列中存储的元素的个数。14） Add：将一架飞机加入相应的队列。15） Remove：将一架飞机移除出队列。3)程序流程： 1）初始化，给出了程序的作用，并给出了用户需要输入的相关的信息，包括单位时间内可以起飞或者降落的飞机的数量expecteddepart,expectedarrive，还有模拟机场运行的时间endtime。还有一个用于产生伪随机数的程序。 2.)令当前的时间curtime 为1，根据输入的endtime，做for循环：（1）首先根据expecteddepart,expectedarrive，调用Randomize函数和PoissonRand
6、om函数，用在（1）中产生的伪随机数返回Poisson分布下对应的数值pri（这里只取整数），分别在控制两个for循环，每次循环都是根据飞机的状态是ARRIVE还是DEPART（由枚举变量kind随机决定），分别向起飞队列和降落队列提出请求，如果队列已满，则拒绝请求（Refuse函数）,如队列未满则加入队列（Add函数）。（2）判断降落队列pl是否为空，如不空，说明有飞机等待降落，将飞机从队列pl中清除Remove函数，同时飞机降落，记录下相关的信息：包括飞机的编号，降落时的时间，等待时间（Land函数）。如没有飞机等待降落，则处理起飞队列pt。过程与处理飞机降落类似，由Remove函数和Fl
7、y函数共同完成。因为题中要求降落的飞机的优先级高于起飞的飞机，所以首先判断是否有飞机等待降落，也就是首先判断队列pl是否为空（3）如果既没有飞机降落，也没有飞机起飞，则说明跑到此时刻为空。此时调用Idletime函数记录下当前为空的时间（curtime），同时记录跑道空的次数加1（idletime+）。同时curtime+,表示本模拟单元已经过去，进入下一次模拟 3）总结相关信息，打印模拟的结果。由Conclude函数完成。计算机实现：程序代码：#define MAXQUEUE 5#include #include #include #include #include typedef enum
8、 action ARRIVE,LAND Action;typedef struct plane int id; /*identification numbeer of airplane*/ int tm; /*time of arrival in queue*/ Plane;typedef Plane QueueEntry; typedef struct queue int count; /*numberj of airplanes in the queue*/ int front; /*front of the queue*/ int rear; /*rear of the queue*/
9、QueueEntry entryMAXQUEUE; Queue;void NewPlane(Plane *p, int *nplanes, int curtime, Action kind);void Refuse(Plane P, int *nrefuse, Action kind);void Land(Plane p, int curtime, int *nland, int *landwait);void Fly (Plane p, int curtime, int *ntakeoff, int *takeoffwait);void Start (int *endtime,double
10、*expectarrive, double *expectdepart);void Idle (int curtime, int *idletime);void Conclude(int nplanes, int nland,int ntakeoff, int nrefuse, int landwait, int takeoffwait, int idletime, int endtime, Queue *pt, Queue *pl);void Randomize(void); /*Generate a pseudo-random integer*/int PoissonRandom (dou
11、ble expectedvalue); /*Simulate the distribution of Poisson */bool UserSayYes(void); /*The series functions of Queue*/void CreateQueue(Queue *q);int Queuefull (Queue *q);int Queueempty (Queue *q);int Queuesize (Queue *q);void Add(QueueEntry x, Queue *q);void Remove(QueueEntry *x, Queue *q);int main (
12、void) /*the main program*/ Queue landing, takeoff; Queue *pl=&landing; Queue *pt=&takeoff; Plane plane; int curtime; /*current time, one unit=time for take off or landing*/ int endtime; /*total number of time units to run*/ double expectarrive; /*number of planes arriving in one unit*/ double expect
13、depart; /*number of planes newly ready to take off*/ int i; /*loop control variable*/ int idletime; /*number of units when runway is idle*/ int landwait; /*total waiting time for planes landed*/ int nland; /*number of planes landed*/ int nplanes; /*number of planes processed so far*/ int nrefuse; /*
14、number of planes refused use of airport*/ int ntakeoff; /*number of planes taken off*/ int pri; /*pseudo-random integer*/ int takeoffwait; /*total waiting time for takeoff*/ CreateQueue(pl); CreateQueue(pt); nplanes=nland=ntakeoff=nrefuse=0; landwait=takeoffwait=idletime=0; Start(&endtime,&expectarr
15、ive,&expectdepart); for (curtime=1; curtime=endtime; curtime+) pri=PoissonRandom(expectarrive); for (i=1; i=pri; i+) /*Add to landing queue*/ NewPlane(&plane,&nplanes,curtime,ARRIVE); if (Queuefull(pl) Refuse(plane,&nrefuse,ARRIVE); else Add(plane,pl); pri=PoissonRandom(expectdepart); for (i=1; i=pr
16、i; i+) /*Add to takeoff queue*/ NewPlane(&plane,&nplanes,curtime,LAND); if (Queuefull(pt) Refuse(plane,&nrefuse,LAND); /If the queue of landing is full ,refuse the request. else Add(plane,pt); if (!Queueempty(pl) /*Bring planes to land*/ Remove(&plane,pl); Land(plane,curtime,&nland,&landwait); else
17、if(!Queueempty(pt) /*Allow planes to take off*/ Remove(&plane,pt); Fly(plane,curtime,&ntakeoff,&takeoffwait); else Idle(curtime,&idletime); Conclude(nplanes,nland,ntakeoff,nrefuse,landwait, takeoffwait,idletime,endtime,pt,pl); return 0;/*Start: Print messages and initialize the parameters. Pre: none
18、 Post: Ask users for responses and initializes all variables, specified as parameters. Uses: Uses say yes*/void Start (int *endtime,double *expectarrive, double *expectdepart) bool ok; printf(This program simulates an airport with only one runway.n One plane can land or take off in each unit of time
19、.n Up to %d planes can be waiting to land or take off at any timen, MAXQUEUE); printf(How many units of time will be the simulation run?n); scanf(%d,endtime); Randomize(); /*Initialize random number generaton*/ do printf(Expected number of arrivals in each unit time ?n); scanf(%lf,expectarrive); pri
20、ntf(Expected number of departures in each unit time?n); scanf(%lf,expectdepart); if(*expectarrive0.0 | *expectdepart1.0) printf(The airport will become satarated. Read new members?); ok=!UserSayYes(); /*if user say yes ,repeat loop*/ else ok=1; while(ok=0);/*NewPlane: Make a new record for a plane,a
21、nd update nplanes. Pre: None Post: Makes a new structure for a plane and updates nplanes.*/void NewPlane (Plane *p, int *nplanes, int curtime, Action kind) (*nplanes)+; p-id=*nplanes; switch (kind) /Judge the plane is ready to land or take off. case ARRIVE: printf(Plane %3d ready to land.n, *nplanes
22、); break; case LAND : printf(Plane %3d ready to take off.n, *nplanes); break; /*Refuse: Process a plane when the queue is full. Pro: None. Post: Process a plane waiting to use the runway,but the queue is full.*/void Refuse (Plane p, int *nrefuse, Action kind) switch (kind) case ARRIVE: printf(Plane
23、%3d directed to another airport.n, p.id); break; case LAND : printf(Plane %3d told to try later.n, p.id); break; (*nrefuse)+;/*Land: Process a plane that is actually landing. Pre: None. Post: Process a Plane p that is actually landing*/void Land(Plane p, int curtime, int *nland, int *landwait) int w
24、ait; wait=curtime-p.tm; printf(%3d plane %3d landed; in queue %3d units.n,curtime, p.id, wait); (*nland)+; *landwait+=wait;/*Fly: Process a plane that is actually taking off. Pre: None Post: Process a plane that is actually taking off. */void Fly (Plane p, int curtime, int *ntakeoff, int *takeoffwai
25、t) int wait; wait=curtime-p.tm; printf(%3d plane %3d took off; in queue %3d units.n,curtime, p.id, wait); (*ntakeoff)+; *takeoffwait+=wait; /Add all the takeoff time together,and get the total waiting time./*Idle: Updates variables for idle runway. Pre: None. Post: Updates variables for a time unit
26、when the runway is idle.*/void Idle (int curtime, int *idletime) printf(%2d : Runway is idle.n,curtime); (*idletime)+;/*Conclude: Write out statistics and conclude the simulation. Pre: None Post: Write out all the statistics and conclude the simulation.*/void Conclude(int nplanes, int nland,int ntak
27、eoff, int nrefuse, int landwait, int takeoffwait, int idletime, int endtime, Queue *pt, Queue *pl) printf(Simulation hsa concluded after %d units.n, endtime); printf(Total number of planes processed: %3dn, nplanes); printf(Number of planes landed: %3dn, nland); printf(Number of planes taken off: %3d
28、n, ntakeoff); printf(Number of planes refused use: %3dn, nrefuse); printf(Number of planes left ready to land: %3dn, Queuesize(pl); printf(Number of planes left ready to take off: %3dn, Queuesize(pt); if (endtime0) printf(Percentage of time runway idle: %6.2fn, (double)idletime/endtime)*100.0); if (
29、nland0) printf(Average wait time to land: %6.2fn, (double)landwait/nland); if (ntakeoff0) printf(Average wait time to take off: %6.2fn, (double)takeoffwait/ntakeoff);/*Randomize: Set starting point for preudorandom integer*/void Randomize(void) srand(unsigned int)time(NULL)%10000);/*PoissonRandom: Generate a preudorandom integer according to the Poisson distribution Pre: None. Post: Generate a preudorandom integer according to the Poisson distribution with the value given as the parameter*/int PoissonRandom (double expectedvalue) int n=0; /*for loop*/
