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

1、计算机软件技术基础 实验报告 I 数据结构实验二：停车场管理问题一、问题描述1. 实验题目：设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在 停车场内按车辆到达时间的先后顺序， 依次由北向南排列 （大门在最南端， 最先到达的第一 辆车停放在车场的最北端） 。若停车场内已经停满 n 辆车， 那么后来的车只能在门外的便道 上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时， 在它之后进入的车辆必须先退出车场为它让路， 待该辆车开出大门外， 其他车辆再按原次序 进入车场。 每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。 试

2、为 停车场编制按上述要求进行管理的模拟程序。2基本要求：以栈模拟停车场， 以队列模拟车场外的便道， 按照从终端读入数据的序列进行模拟管理。 每一组输入数据包括三个数据项：汽车的“到达”（A 表示）或“离去” （D表示）信息、汽车标识（牌照号）以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息 为：若是车辆到达， 则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出 汽车在停车场停留的时间和应缴纳的费用 （便道上停留的时间不收费） 。栈以顺序结构实现， 队列以链表结构实现。3测试数据：设 n=2,输入数据为：（A1, 5），（ A, 2，10），（ D 1，15）, （ A,

3、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 辆车的停车场的停车管理问题。 用栈和队列模拟停车场及 场外通道,输入车辆状态（到达或者离开） ,车牌号和时间,就可显示停车位置或者该车在 停

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， 2

5、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. 栈抽象数据类型定义 ：ADT SqStack

6、数据对象：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 struct car;基本操作：Car_enter(carnum,cartime)/将到达车辆a的信息入栈s或者入队qCar_Leave（carnum,cartime） ； /将待离开车辆 d出栈s，并将q中相应车辆入栈并进行相关的操作Result（char carmove,int carnum,int cartime）/ 根据输入信息完成车辆的离开或者到达ADT SqStackADT的C语

7、言形式说明：typedef struct / 构造一个顺序栈struct Node1 homeMaxSize;int stacktop; / 栈顶的指针Stack;2. 队 列抽象数据 类型定义ADT LinkQueue数据对象：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(

8、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)/ 根据输入信息完成车辆的离开或者达到3. 主程序流

9、程及其模块调用关系 :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(int carn

10、um,int cartime):创建一个临时栈存放退出让路的车， 若在车库中找到对应的车，车库中该车后面的车辆信息进入临时栈CarS2,该车出栈，显示车牌号，此时时间，停留时间，应缴费用。临时栈中的车的信息再回到CarS中。此时若队幵始；初姗七找和队列7列CarQ不为空则将队列中车辆信息放入栈Cars中。若在车库中找不到对应的车的车牌号信息，则在表示候车场的队列中找该车信息赳果它在队列的最后，直接出列并输出车牌 此时时间，停留时间，应缴费用。如果它不在队尾，先把对应信息保存在一个指向队列的指 辑中5输出车牌号，此时时间f,停留时间，应缴费用。删除队列中此结点表示此口 号,候车场车辆数程序。若输

11、入P,则输出车库车辆数 PCar;WCar;；卜士.：若 卞十若车在庫中：ffl 面的车逬入临 时钱CarS2,该 车出栈候车 场车辆进入车 库。*车在悵车 场,输出, 候车场叽 列删除该 结点4输出车牌号， 时间，位置。仪车鈕1车&卑号，时 间费用*输出车库车 辆数输i出假车场车 辆数四、详细设计1. 元素类型、结点类型和结点指针类型：typedef struct Nodel/构建一个结构体int carnum;int time;Node1;typedef struct Node2int carnum;int time;struct Node2 *next;Node2;2、创建顺序栈type

12、def struct / 构造一个顺序栈struct Node1 homeMaxSize;int stacktop; / 栈顶的指针Stack;3、创建链式队列typedef struct / 构建一个链式队列Node2 *front,*rear;Queue;4. 车辆到达：void Car_enter(int carnum,int cartime) / 到达车辆的信息入栈或者入队if(CarS.stacktopcarnum=carnum ;CarQ.front-time=cartime;/ 到达车辆信息加入到队列中WCar+; / 候车场车辆数 +1printf(%d 号 车 进 入 候 车

13、 场 ! 到 达 时 刻 :%d位置:%dn,CarQ.front -carnum=carnum,CarQ.front -time=cartime,WCar);CarQ.front-next=(Node2 *)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; 设

14、临时栈 CarS2为空for(i=0;ifindcar;CarS2.stacktop+)将车库里面在i车外面的车移动到临时 栈CarS2中CarS2.homeCarS2.stacktop.carnum=CarS.homeCarS.stacktop.carnum; CarS2.homeCarS2.stacktop.time=CarS.homeCarS.stacktop.time; printf(%d 号 车 离 开 停 车 场 ! 离 开 时 刻 :%d, 停 留 时 长(%d)n,CarS.homeCarS.stacktop.carnum,cartime,cartime -CarS.homeC

15、arS.stacktop.time);PCar-;/车库内车辆 -1printf( 应付停车费 %dn,(cartime -CarS.homeCarS.stacktop.time)*5); for(i=CarS2.stacktop-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)/ 如果候车场有车，将它

16、移进车库CarS.homeCarS.stacktop.carnum=CarQ.rear-carnum;/ 将队列中的车牌号信息放入栈CarS.homeCarS.stacktop.time=cartime; 将此时的时刻记录入栈CarS 确保计算费用是从车辆从候车场进入车库后才开始算CarS.stacktop+;PCar+;车库车辆数+1WCar-;/候车场车辆数 -1p=CarQ.rear;CarQ.rear=CarQ.rear-next;free(p);else/ 如果车库中找不到此车，再在候车场找p=CarQ.rear;if(p!=CarQ.front&p -carnum!=carnum)

17、 / 候车场队列不为空f=p-next;while(f!=CarQ.front&f -carnum!=carnum)p=f;f=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)/ 要离开的

18、车在队尾，直接出队findcar=1;CarQ.rear=CarQ.rear-next;printf(%d 号 车 离 开 候 车 场 ! 离 开 时 间 :%d, 停 留 时 长(%d)!n,p -carnum,cartime,cartime -p-time);WCar-;printf( 应付停车费 : %dn,(cartime -p-time)*0);free(p);if(findcar= -1) printf(%d 号车不在停车场中 !n,carnum);6. 主函数main()printf( 试验名称：停车场管理问题 n);printf( 学号： n);printf( 姓名： xxn)

19、;printf(=n);time_t rawtime1;struct tm * timeinfo1;time (&rawtime1);timeinfo1 = localtime (&rawtime1); / 时间函数； printf ( 程序运行开始 ,当前日期和时间 : %s, asctime(timeinfo1);int go=1,carnum,cartime,MM;char carmove;CarS.stacktop=0;CarQ.rear=CarQ.front=(Node2 *)malloc(sizeof(Node2);while(go)P;nprintf(n 车辆到达请输入 A;n

20、车辆离开请输入 D;n 显示停车场内车数请输入 显示候车场车数请输入 W;n 退出程序请输入 E:n);printf(n 请输入信息 :);carmove=getchar();printf(n); switch(carmove)case A: printf(%cn 车牌号 :t,carmove); scanf(%d,&carnum); printf( 时间 :t);scanf(%d,&cartime);MM=Result(carmove,carnum,cartime); if(!MM)go=0;break;case D:printf(%cn 车牌号 :t,carmove);scanf(%d,&

21、carnum);printf( 现在时刻 :t);scanf(%d,&cartime); MM=Result(carmove,carnum,cartime);if(!MM)go=0;break;case W:printf( 正在外通道等待的车数量是 : %dn,WCar);break;case P:printf( 车库内车的数量是 : %dn,PCar);break;case E:printf( 退出 !n);time_t rawtime2;struct tm * timeinfo2;time (&rawtime2);timeinfo2 = localtime (&rawtime2);prin

22、tf ( 程序运行结束 ,当前日期和时间 : %s, asctime(timeinfo2); return 0;getchar();五、调试分析此程序是分模块设计，根据输入的指令调用“到达”和“离开”模块，使车的信息入栈入队，或出栈出队。每次运行后又返回主菜单。程序整体结构清晰，操作方便。六、使用说明用户根据提示输入指令： 到达输入A,离开输入D,显示车库车辆数输入P,显示候车场车辆数输入 W,退出程序输入 巳输入A后，根据提示输入车牌号i和此时时间，将显示“第i号车进入车库! 时间：位置：”或“第i号车进入候车场！时间：位置：”；输入D后，根据提示输入车牌号i和此时时间，将显示“第i号车离开

23、车库!:青输X言息二呈序运4幵始当前日朗和时间：弘七Nnu 07 X3：30：22 2015专*獰匸间间y r应千缴费学号：031350103姓名；佟欣P 入帳-1 - 8?瞬 tsRS或“第i号车离开候车场！时间：停留时II输入到达车辆:-C:Uie rAdm inhtrata rD 巧 kto plDe q ugl .exe丨u回S学号：031350103桎名；佟欣三星序运行开始*当前日期和时间：Sat Hou 0? 13:33 = 29 2B15苓护到达请拋入馆车訥葛开请输人咗退出请输入信息油pr:Ae：车牌号：1吋I即5丄号车进入停车场辛进入时刻詬 位直，1圭蹬1达请逾入囱=车辆简幵遠

24、触專* .场內车憩I冃碱入P； 场车数if谕人砒E：牌号；4Tf|6:25号车进入候车场！到达时刻:毋位置囂囂帥进入时刻逸回SSI H C: U se rsAdm i nistratc rDesktoplDebugl. ex e到达车辆超过车库容量时: fP入W;输人青俞A Dsy E 车费 一输 圭冃HR场冃 输入车辆离开信息:P入U;艮请输A;D;誓:入入车費.ss达幵rD# sktoplDebu gl.exe口输入信息：DIL牌号：4见在日翅240皋车离用亭车场？离开时那他停留时长0 应吋显菱25PAW;is人 主冃输 壯誓E: AxiA 输 请请场场请 达开Um- 到禺停每 i卫艮车库

25、內车的数量是：2P认U;WA 请输 帝DiBE: 车賢 主星冃场场青 到离wea E示击 一二一二！弓*-mr-输入W:输入E:请请场场请 达 t&wb 到离+沖蒯內车输主冃主冃到离停悍程退岀！屋序运行结束当前日期和时间：Sat Nou 07 13:35:41 2815 ress any ke u Ito contioue!请输入怙息迈在外通道孝寺的车数量星：0青输人信息珂车毕穴车的效竜是：2*C:U sersAd m i nistratorXDesIrtopXlDebugXl/exe-u 回 S3 |到八、遇到的问题和解决方法i开始，程序编写完成后虽然没有报错，却不能运行，如图s fP入V;

26、输入请输A;DJlsE:入入车贸青青场场青sfi显退入W;X请输n:D;鬻E:入入车费车输 请请场场请 迖幵wHt 高丰+- -c *C;and Sett iiigshpM面D爭bu吐1. ese*-llxlKIP人W;XI A;D;数注嗚E: 入入车数人 请请场场请 达芳wt US es示一玉fliD;数住頂E: 入入车数入 请请盘请 达开车 到离羹程P入M;燹F岭,逝*退別可睑斋要壬丙-垮E此引担住T湮衣担里r肛处于逹覆当申”类干|EI.牯民R匹Ft悟冃H耐I并用叩经检查程序，将Stack *CarS; Queue *CarQ;这两个指针型变量改成Stack CarS; /用来表示车库的栈

27、Queue CarQ;/用来表示候车场的队列，再次运行发现可以成功运行。2当输入上述数据后输入P和 W后显示的车辆数不对，当车库内车辆离开时，外通道的车进入车库，但 PCar和WCar没有正确跟随变化，如图请输人信息:E底岀隅序运於吉東，当前日期和时间：Fri Nou OS 21=02=50 2015 卩严号醫令 aLny key to continue经检查程序，在if(CarQ.front!=CarQ.rear)如果候车场有车，将它移进车库CarS.homeCarS.stacktop.carnum=CarQ.rear-carnum; 将队列中的车牌号信息放入栈CarS.homeCarS.s

28、tacktop.time=cartime; 将此时的时刻记录入栈CarS 确保计算费用是从车辆从候车场进入车库后才开始算CarS.stacktop+;p=CarQ.rear;CarQ.rear=CarQ.rear-next;free(p);这段程序中少了PCar+; WCar-;，加上后再次运行，程序正确。3.计算费用时发现错误，在候车厅时间也被计入停车费。经检查程序，将CarS.homeCarS.stacktop.time=CarQ.rear-time;改成 CarS.homeCarS.stacktop.time=cartime; 使其计费时间从进入车库开始而不是从达到候 车场开始。再次运行

29、发现结果正确。九、实验收货和感想这是第一次运用栈和队列的相关知识编写程序， 开始看到这个题目感觉挑战很大， 从未尝 试过这么复杂的一个系统。 停车场问题相较与约瑟夫斯问题要复杂得多， 分了多个模块。 起 初编写时漏洞很多， 好在当框架出来后各个漏洞都可以被弥补。 比如程序刚运行成功时， 发 现不能显示位置， 车库车辆数和候车场车辆数不正确， 计费不正确等很多漏洞， 但这些细节 的小问题都比较容易排查修改， 最终终于做出了符合要求的停车场管理系统。 当完成后， 我 对栈和队列的相关算法的理解也更加清晰深刻了。这个程序中还有一些灵活可变的地方， 用宏定义定义了车库容量和费用单价， 使具体数字可以较

30、为灵活的改变， 增加了这个程序的使 用价值。 计算机实践课程给了我动手操作的机会，使我将理论和实际操作结合起来， 更好地理解算法， 更快地学会编程。每次编程都感觉收获非常多。练习的越多，对算法语句越是熟 练，越能有深刻的理解， 不仅帮助我更好的学习软件技术基础 也为以后我们专业课的道 路打好基石，对我们的逻辑能力也是很大的提升。十、源程序#include#include#include #define MaxSize 2/ 车库最大容量#define fee 10/ 在车库中停车的单价int carnum;int time;Node1;typedef struct/ 构造一个顺序栈struct

31、 Node1 homeMaxSize;int stacktop; / 栈顶的指针Stack;typedef struct Node2int carnum;int time;struct Node2 *next;Node2;typedef struct/ 构建一个链式队列Node2 *front,*rear;Queue;Stack CarS; / 用来表示车库的栈Queue CarQ; / 用来表示候车场的队列int PCar=0;/ 车库里车的数量int WCar=0;/ 候车场的车的数量void Car_enter(int carnum,int cartime) / 到达车辆的信息入栈或者入

32、队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=(Node2 *)malloc(sizeof(Node2);/ 分配空间CarQ.front=CarQ.front-next;/ 更改队列指针void Car_Leave(int carnum

33、,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.carnum=CarS.homeCarS.stacktop.carnum;CarS2.homeCarS2.stacktop.time=CarS.homeCarS.stacktop.time;pr

34、intf(%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.stacktop -1;i=0;i -)/ 把临时栈里面的车移回去 CarS.homeCarS.stacktop.carnum=CarS2.homei.carnum;

35、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; 将此时的时刻记录入栈CarS 确保计算费用是从车辆从候车场进入车库后才开始算CarS.stacktop+;PCar+;车库车辆数+1WCar-;/候车场车辆数 -1p

36、=CarQ.rear;CarQ.rear=CarQ.rear-next;free(p);else/ 如果车库中找不到此车，再在候车场找p=CarQ.rear;if(p!=CarQ.front&p -carnum!=carnum) / 候车场队列不为空f=p-next;while(f!=CarQ.front&f -carnum!=carnum)p=f;f=f-next;if(f -carnum=carnum)/ 如果寻找的车在便道上，出队列findcar=1;p-next=f-next;printf(%d 号 车 离 开 候 车 场 ! 离 开 时 间 : %d, 停 留 时 长 (%d)n,f

37、 -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);WCar-;printf( 应付停车费 : %dn,(cartime -p-time)*0);free(p);if(findcar= -1) printf(%d 号车不在