数据结构实验报告―停车场问题

《计算机软件技术基础》实验报告I—数据结构实验二：停车场管理问题一、问题描述1.实验题目：设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若停车场内已经停满n辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。2．基本要求：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项：汽车的“到达”（‘A’表示）或“离去”（‘D’表示）信息、汽车标识（牌照号）以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。3．测试数据：设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。其中：（‘A’，1，5）表示1号牌照车在5这个时刻到达，而（‘D’，1，15）表示1号牌照车在15这个时刻离去。二、需求分析1.程序所能达到的基本可能：本程序用来模拟一个可停放n辆车的停车场的停车管理问题。用栈和队列模拟停车场及场外通道，输入车辆状态（到达或者离开），车牌号和时间，就可显示停车位置或者该车在停车场停留时间及应缴费用。2.输入的形式及输入值范围：程序接受5个命令，分别是：到达（‘A’,车牌号,时间)；离去(‘D’,车牌号,时间)；停车场（‘P’,0,0）显示停车场的车数；候车场（‘W’,0,0）显示候车场的车数；退出（‘E’,0,0）退出程序。3.输出的形式：对于车辆到达，要输出汽车在停车场内或者便道上的停车位置；对于车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上不收费）。用户输入完毕后，程序自动运行输出运行结果。4.测试数据要求：设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。其中：（‘A’，1，5）表示1号牌照车在5这个时刻到达，而（‘D’，1，15）表示1号牌照车在15这个时刻离去。三、概要设计为了实现上述功能，该程序以栈模拟停车场以及临时停放为给要离去的汽车让路而从停车场退出来的汽车的场地，以队列模拟车场外的便道，因此需要栈和队列这两个抽象数据类型。1.栈抽象数据类型定义：ADTSqStack{数据对象：D={ai,bi,ci,di|ai∈int,bi∈int,ci∈int,di∈char),i=1,2...,n,n≥0}:数据关系：R={(ai,bi,di,)|ai,bi,di∈D,ai,bi,di∈structcar};基本操作：Car_enter(carnum,cartime)//将到达车辆a的信息入栈s或者入队qCar_Leave(carnum,cartime)；//将待离开车辆d出栈s，并将q中相应车辆入栈并进行相关的操作Result(charcarmove,intcarnum,intcartime)//根据输入信息完成车辆的离开或者到达}ADTSqStackADT的C语言形式说明：typedefstruct//构造一个顺序栈{structNode1home[MaxSize];intstacktop;//栈顶的指针}Stack;2.队列抽象数据类型定义ADTLinkQueue{数据对象：D={ai,bi,ci|ai∈Qnode*,bi∈Qnode*,ci∈int),i=1,2...,n,n≥0};数据关系：R=∅基本操作：Car_enter(carnum,cartime)//将到达车辆a的信息入栈s或者入队qCar_Leave(carnum,cartime)；//将待离开车辆d出栈s，并将q中相应车辆入栈并进行相关的操作Result(charcarmove,intcarnum,intcartime)//根据输入信息完成车辆的离开或者到达}ADTLinkQueueADT的C语言形式说明：typedefstruct//构建一个链式队列{QNode*front,*rear;}Queue;voidCar_enter(intcarnum,intcartime)//到达车辆的信息入栈或者入队voidCar_Leave(intcarnum,intcartime)//车离开intResult(charcarmove,intcarnum,intcartime)//根据输入信息完成车辆的离开或者达到3.主程序流程及其模块调用关系:1）主程序流程：主函数提示用户输入指令：到达（‘A’,车牌号,时间)；离去(‘D’,车牌号,时间)；停车场‘P’显示停车场的车数；候车场‘W’显示候车场的车数；退出‘E’退出程序。调用intResult(charcarmove,intcarnum,intcartime)根据输入信息完成车辆的离开或者达到。若输入A则调用Car_enter(intcarnum,intcartime)，创建顺序栈CarS和链式队列CarQ，根据栈是否满决定输入的信息入栈还是入队列。若栈未满，输入的车辆信息入栈，若已满，入队列。若输入D则调用Car_Leave(intcarnum,intcartime)：创建一个临时栈存放退出让路的车，若在车库中找到对应的车，车库中该车后面的车辆信息进入临时栈CarS2，该车出栈，显示车牌号，此时时间，停留时间，应缴费用。临时栈中的车的信息再回到CarS中。此时若队列CarQ不为空则将队列中车辆信息放入栈CarS中。若在车库中找不到对应的车的车牌号信息，则在表示候车场的队列中找该车信息，如果它在队列的最后，直接出列并输出车牌号，此时时间，停留时间，应缴费用。如果它不在队尾，先把对应信息保存在一个指向队列的指针中，输出车牌号，此时时间，停留时间，应缴费用。删除队列中此结点表示此车离开候车场。若输入P，则输出车库车辆数PCar；若输入W，则输出候车场车辆数WCar；若输入E，则退出程序。2）调用关系四、详细设计1.元素类型、结点类型和结点指针类型：typedefstructNode1//构建一个结构体{intcarnum;inttime;}Node1;typedefstructNode2{intcarnum;inttime;structNode2*next;}Node2;2、创建顺序栈typedefstruct//构造一个顺序栈{structNode1home[MaxSize];intstacktop;//栈顶的指针}Stack;3、创建链式队列typedefstruct//构建一个链式队列{Node2*front,*rear;}Queue;4.车辆到达：voidCar_enter(intcarnum,intcartime)//到达车辆的信息入栈或者入队{if(CarS.stacktopMaxSize)//如果栈没有满的时候{CarS.home[CarS.stacktop].carnum=carnum;//到达车辆信息放入顺序栈CarS.home[CarS.stacktop].time=cartime;PCar++;//车库里的车数量+1printf(%d号车进入停车场!进入时刻:%d位置:%d\n,CarS.home[CarS.stacktop].carnum,CarS.home[CarS.stacktop].time,PCar);CarS.stacktop++;//栈顶指针加一}else//若栈满{CarQ.front-carnum=carnum;CarQ.front-time=cartime;//到达车辆信息加入到队列中WCar++;//候车场车辆数+1printf(%d号车进入候车场!到达时刻:%d位置:%d\n,CarQ.front-carnum=carnum,CarQ.front-time=cartime,WCar);CarQ.front-next=(Node2*)malloc(sizeof(Node2));//分配空间CarQ.front=CarQ.front-next;//更改队列指针}}5.车辆离开voidCar_Leave(intcarnum,intcartime)//车离开{StackCarS2;//构造一个栈临时存放为了让位退出来的车inti;intfindcar=-1;Node2*p,*f;CarS2.stacktop=0;//设临时栈CarS2为空for(i=0;iCarS.stacktop;i++)//通过循环对比查找要离开的车{if(carnum==CarS.home[i].carnum){findcar=i;//如果要寻找的车在车库里则让findcar等于车的号码break;}}if(findcar!=-1)//如果在车库里找到这辆车{for(;--CarS.stacktopfindcar;CarS2.stacktop++)//将车库里面在i车外面的车移动到临时栈CarS2中{CarS2.home[CarS2.stacktop].carnum=CarS.home[CarS.stacktop].carnum;CarS2.home[CarS2.stacktop].time=CarS.home[CarS.stacktop].time;}printf(%d号车离开停车场!离开时刻:%d,停留时长(%d)\n,CarS.home[CarS.stacktop].carnum,cartime,cartime-CarS.home[CarS.stacktop].time);PCar--;//车库内车辆-1printf(应付停车费%d\n,(cartime-CarS.home[CarS.stacktop].time)*5);for(i=CarS2.stacktop-1;i=0;i--)//把临时栈里面的车移回去{CarS.home[CarS.stacktop].carnum=CarS2.home[i].carnum;CarS.home[CarS.stacktop].time=CarS2.home[i].time;CarS.stacktop++;CarS2.stacktop--;}if(CarQ.front!=CarQ.rear)//如果候车场有车，将它移进车库{CarS.home[CarS.stacktop].carnum=CarQ.rear-carnum;//将队列中的车牌号信息放入栈CarS.home[CarS.stacktop].time=cartime;//将此时的时刻记录入栈CarS，确保计算费用是从车辆从候车场进入车库后才开始算CarS.stacktop++;PCar++;//车库车辆数+1WCar--;//候车场车辆数-1p=CarQ.rear;CarQ.rear=CarQ.rear-next;free(p);}}else//如果车库中找不到此车，再在候车场找{p=CarQ.rear;if(p!=C