1、计算机软件技术基础 实验报告 I数据结构实验二：停车场管理问题一、问题描述1.实验题目：设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端） 。若停车场内已经停满 n 辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理
2、的模拟程序。2基本要求：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项：汽车的“到达” （A表示）或“离去” （D表示）信息、汽车标识（牌照号）以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费） 。栈以顺序结构实现，队列以链表结构实现。3测试数据：设 n=2,输入数据为：（A ，1，5 ） ， （A ，2， 10） ， （D ，1 ，15 ） ， （A ，3， 20） ， （A ，4，2
3、5） ， （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 辆车的停车场的停车管理问题。用栈和队列模拟停车场及场外通道，输入车辆状态（到达或者离开） ，车牌号和时间，就可显示停车位置或者该车在停车场停留时间及应缴费用
4、。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、 ，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. 栈抽象数据类型定义 ：ADT SqStack 数据对象：D
6、=ai,bi,ci,di|aiint, biint,ciint,dichar),i =1,2.,n,n0: 数据关系：R=(ai,bi,di,)|ai,bi,diD,ai,bi,distruct car; 基本操作： Car_enter(carnum,cartime)/将到达车辆 a 的信息入栈 s 或者入队 q Car_Leave(carnum,cartime)；/ 将待离开车辆 d 出栈 s，并将 q 中相应车辆入栈并进行相关的操作 Result(char carmove,int carnum,int cartime)/根据输入信息完成车辆的离开或者到达 ADT SqStack ADT 的
7、 C 语言形式说明：typedef struct /构造一个顺序栈struct Node1 homeMaxSize;int stacktop; /栈顶的指针Stack;2. 队 列 抽 象 数 据 类 型 定 义ADT LinkQueue数据对象：D=ai,bi,ci|aiQnode*, biQnode*,ciint), i =1,2.,n,n0; 数据关系：R= 基本操作：Car_enter(carnum,cartime)/将到达车辆 a 的信息入栈 s 或者入队 q Car_Leave(carnum,cartime)；/ 将待离开车辆 d 出栈 s，并将 q 中相应车辆入栈并进行相关的操作
8、 Result(char carmove,int carnum,int cartime)/根据输入信息完成车辆的离开或者到达 ADT LinkQueueADT 的 C 语言形式说明：typedef struct /构建一个链式队列QNode *front,*rear;Queue; void Car_enter(int carnum,int cartime) /到达车辆的信息入栈或者入队void Car_Leave(int carnum,int cartime)/车离开int Result(char carmove,int carnum,int cartime)/根据输入信息完成车辆的离开或者达
9、到3. 主程序流程及其模块调用关系:1）主程序流程：主函数提示用户输入指令：到达（A, 车牌号,时间)；离去( D,车牌号,时间)；停车场P 显示停车场的车数；候车场W显示候车场的车数；退出E 退出程序。调用 int Result(char carmove,int carnum,int cartime)根据输入信息完成车辆的离开或者达到。若输入 A 则调用 Car_enter(int carnum,int cartime) ，创建顺序栈 CarS 和链式队列CarQ，根据栈是否满决定输入的信息入栈还是入队列。若栈未满，输入的车辆信息入栈，若已满，入队列。若输入 D 则调用 Car_Leave(
10、int carnum,int cartime)：创建一个临时栈存放退出让路的车，若在车库中找到对应的车，车库中该车后面的车辆信息进入临时栈 CarS2，该车出栈，显示车牌号，此时时间，停留时间，应缴费用。临时栈中的车的信息再回到 CarS 中。此时若队列 CarQ 不为空则将队列中车辆信息放入栈 CarS 中。若在车库中找不到对应的车的车牌号信息，则在表示候车场的队列中找该车信息，如果它在队列的最后，直接出列并输出车牌号，此时时间，停留时间，应缴费用。如果它不在队尾，先把对应信息保存在一个指向队列的指针中，输出车牌号，此时时间，停留时间，应缴费用。删除队列中此结点表示此车离开候车场。若输入 P
11、，则输出车库车辆数 PCar；若输入 W，则输出候车场车辆数 WCar；若输入 E，则退出程序。2） 调用关系 四、详细设计 1.元素类型、结点类型和结点指针类型：typedef struct Node1 /构建一个结构体int carnum;int time;Node1;typedef struct Node2 int carnum;int time;struct Node2 *next;Node2; 2、 创建顺序栈typedef struct /构造一个顺序栈struct Node1 homeMaxSize;int stacktop; /栈顶的指针Stack;3、 创建链式队列typed
12、ef struct /构建一个链式队列Node2 *front,*rear;Queue; 4.车辆到达：void Car_enter(int carnum,int cartime) /到达车辆的信息入栈或者入队 if(CarS.stacktopcarnum=carnum;CarQ.front-time=cartime;/到达车辆信息加入到队列中WCar+; /候车场车辆数 +1printf(“%d 号车进入候车场! 到达时刻:%d 位置:%dn“,CarQ.front-carnum=carnum,CarQ.front-time=cartime,WCar);CarQ.front-next=(No
13、de2 *)malloc(sizeof(Node2);/分配空间CarQ.front=CarQ.front-next;/更改队列指针5.车辆离开void Car_Leave(int carnum,int cartime)/车离开Stack CarS2;/构造一个栈临时存放为了让位退出来的车int i;int findcar=-1;Node2 *p,*f;CarS2.stacktop=0;/设临时栈 CarS2 为空for(i=0;ifindcar;CarS2.stacktop+)/将车库里面在 i 车外面的车移动到临时栈 CarS2 中CarS2.homeCarS2.stacktop.carn
14、um=CarS.homeCarS.stacktop.carnum;CarS2.homeCarS2.stacktop.time=CarS.homeCarS.stacktop.time;printf(“%d 号车离开停车场 ! 离开时刻 : %d,停留时长(%d)n“,CarS.homeCarS.stacktop.carnum,cartime,cartime-CarS.homeCarS.stacktop.time);PCar-;/车库内车辆-1printf(“应付停车费 %dn“,(cartime-CarS.homeCarS.stacktop.time)*5);for(i=CarS2.stackt
15、op-1;i=0;i-)/把临时栈里面的车移回去CarS.homeCarS.stacktop.carnum=CarS2.homei.carnum;CarS.homeCarS.stacktop.time=CarS2.homei.time;CarS.stacktop+;CarS2.stacktop-;if(CarQ.front!=CarQ.rear)/如果候车场有车，将它移进车库CarS.homeCarS.stacktop.carnum=CarQ.rear-carnum;/将队列中的车牌号信息放入栈CarS.homeCarS.stacktop.time=cartime;/将此时的时刻记录入栈 Ca
16、rS，确保计算费用是从车辆从候车场进入车库后才开始算CarS.stacktop+;PCar+;/车库车辆数+1WCar-;/候车场车辆数 -1p=CarQ.rear;CarQ.rear=CarQ.rear-next;free(p);else/如果车库中找不到此车，再在候车场找p=CarQ.rear;if(p!=CarQ.frontwhile(f!=CarQ.frontf=f-next;if(f-carnum=carnum)/如果寻找的车在便道上，出队列findcar=1;p-next=f-next;printf(“%d 号车离开候车场 ! 离开时间: %d,停留时长(%d)n“,f-carnum,cartime,cartime-f-time);WCar-;printf(“应付停车费: %dn“,(cartime-f-time)*0);free(f);if(p-carnum=carnum)/要离开的车在队尾，直接出队findcar=1;CarQ.rear=CarQ.rear-next;printf(“%d 号车离开候车场 !离开时间: %d,停留时长(%d)!n“,p-carnum,cartime,cartime-p-time);
