数据结构课程设计模拟停车场管理问题

1、目 录1、 设计目的22、 设计内容21. 题目 22. 问题描述23. 基本要求24. 实现提示23、 算法思想分析34、 算法描述与实现41.数据结构类型定义 42.主要算法的流程图及系统模块划分63.功能描述 74.程序代码 85、 测试结果 176、 总结体会 201、 设计目的数据结构是计算机专业的核心课程，是一门实践性很强的课程。为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、将算法转换成程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。本课程设计的目的就

2、是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养学生的基本程序设计素养和软件工作者工作作风。2、 设计内容1.题目：模拟停车场管理问题2.问题描述：设停车场只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场按车辆到来的先后顺序依次排列，若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门后，为它让路的车辆在按原次序进入

3、车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。3.基本要求：试为停车场编制按上述要求进行管理的模拟程序。在这里假设汽车不能从便道上开走。试设计一个停车场管理程序。4.实现提示：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，例如：(a,1,5)表示一号牌照车在5这个时刻到达，而(d,5,20)表示5号牌照车在20这个时刻离去，整个程序可以在输入信息为(e,0,0)时结束。对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或

4、便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车。3、 算法思想分析1. 输入 根据提示输入停车场容量n。2. 创建 根据读入的停车场容量n，创建长度为n的栈（停车场）。3. 主要操作1）插入（车辆停入） 根据提示往栈中插入元素（车辆信息），即使车辆停在停车场中。首先检查停车场是否已满，若不满，则车辆停放在停车场中，记录车辆到达时间，并把此时间作为开始计费时间。若插入的元素个数超过停车场的容量，则此后的车辆停在便道上用队列表示，即元素储存在队

5、列中。2）删除（车辆离开） 根据提示删除栈中的元素（车辆信息），即使车辆离开停车场，同时停在便道上的车辆停入停车场中。当车辆离开时，首先要寻找到要离开车辆的车牌号，若车是从停车场离开，则在它之后进入的车辆必须先退出(进入临时栈)为它让路，待该辆车开出大门外，其它车辆再按原次序进入停车场，并将停放在便道上第一位置的车开进停车场，离开的车辆按其在停车场内停留的时间交费，并把离开车辆的离开时间作为便道上第一位置的车进入停车场的进入时间和开始计费时间。3） 显示 根据提示操作，显示当前停车场和便道使用情况。4） 退出 释放停车场和便道（栈和队列）上的车辆信息等，退出当前运行程序。4、 算法描述与实现1

6、.数据结构类型定义/停车场车辆信息(存储结构)typedef struct carinfor / 车辆信息 char szregmark64; / 车牌号 char szarrtime16; / 到达时间 char szenttime16; / 进入停车场(开始计费)时间 char szdeptime16; / 离开时间 tcarinfor, *lptcarinfor;szregmark64/车牌号szarrtime16/到达时间szenttime16/计费时间szdeptime16/离开时间carinfor停车场车辆信息存储结构/栈carstack存储结构typedef struct car

7、stack lptcarinfor lpcarinfor; / 车辆信息 int ntop; / 栈顶元素下标 int nstacksize; / 栈容量 tcarstack, *lptcarstack;栈顶元素下标 ntop停车场carstack(栈)存储结构lpcarinfornstacksize=ntop+1/便道车辆信息(存储结构)typedef struct carnode / 链队结点信息 tcarinfor carinfo; / 车辆信息 struct carnode *lpnext; / 指向下一个元素的指针 tcarnode, *lptcarnode;szregmark64/

8、车牌号szarrtime16/到达时间szenttime16/计费时间szdeptime16/离开时间carinfor便道车辆信息存储结构/ 链队carqueue存储结构typedef struct carqueue lptcarnode lphead; / 头结点 lptcarnode lprear; / 指向当前队尾的指针 int neffsize; / 当前队中元素个数(有效车位) tcarqueue, *lptcarqueue;lptcarnode lprear便道carsqueue(队列)存储结构lptcarnode lpheadlpcarinfornext 程序运行界面 输入停车场

9、容量，创建栈开 始根据当前提示操作取得key值向栈或队列加入元素信息向栈或队列删除元素信息显示栈和队列的停车情况退出程序e、释放空间ado2. 主要算法的流程图及功能描述（1）流程图：（2）系统模块划分：车进入停车场判断停车场是否已满车进入停车场记录时间开始计费车辆离开记录离开时间计算持续时间和费用否是进入便道记录进入时间但不计费判断停车场是否有空位否继续等待是（3）算法描述：（1） void initstack( lptcarstack &lpcarstack, int nsize ) 初始化栈 lpcarstack,，为栈和车辆信息分配储存空间，将其容量设置为 nsize。 int ini

10、tqueue( lptcarqueue &lpcarqueue ) 初始化链队 lpcarqueue，分配队列存储空间和头结点空间，有效车位初始化。（2） void push( lptcarstack &lpcarstack, tcarinfor carinfo ) 向栈中加入元素信息：车辆信息 carinfo 入栈 lpcarstack，栈顶元素下标+1。 int enqueue( lptcarqueue &lpcarqueue, tcarinfor carinfo ) 向队列中加入元素信息：分配结点空间，车辆信息 carinfo 入队 lpcarqueue，顺序存储到队列中，有效车位加1。

11、（3） void pop( lptcarstack &lpcarstack, tcarinfor &carinfo ) 从栈中删除元素时：车辆信息从栈 lpcarstack 中弹出并存入 carinfo中，栈顶元素下标-1。 int dequeue( lptcarqueue &lpcarqueue, tcarinfor &carinfo ) 从队列中删除元素时：队头元素从链队 lpcarqueue 中出队并存入 carinfo，当队列中无元素时，返回error；否则carinfo中信息存入临时队列中，再释放临时队列，队列长度减1。（4） int main( void ) 主函数：主要设计一个分

12、支语句，让用户根据提示选择要执行的操作，实现所需要的功能。3. 程序代码#include /getch(void)#include /内存分配 #include #include #include #define ok 1#define error 0#define overflow -1#define clearscreen() system( cls ) / 清空当前屏幕/ 显示字符串 szprompt 并等待用户按下任意键#define pause(szprompt) printf( %s,szprompt),getch()/停车场车辆信息(存储结构)typedef struct car

13、infor / 车辆信息 char szregmark64; / 车牌号 char szarrtime16; / 到达时间 char szenttime16; / 进入停车场(开始计费)时间 char szdeptime16; / 离开时间 tcarinfor, *lptcarinfor;/栈carstack存储结构typedef struct carstack lptcarinfor lpcarinfor; / 车辆信息 int ntop; / 栈顶元素下标 int nstacksize; / 栈容量 tcarstack, *lptcarstack;/ 初始化栈 lpcarstack, 将其

14、容量设置为 nsizevoid initstack( lptcarstack &lpcarstack, int nsize ) lpcarstack = ( lptcarstack ) malloc( sizeof ( tcarstack ) ); /栈储存分配 lpcarstack-lpcarinfor = ( lptcarinfor ) malloc( nsize * sizeof ( tcarinfor ); /栈中车辆信息储存分配 lpcarstack-ntop = -1; /栈中无元素 lpcarstack-nstacksize = nsize; /栈的长度为nsize/ 车辆信息

15、carinfo 入栈 lpcarstackvoid push( lptcarstack &lpcarstack, tcarinfor carinfo ) lpcarstack-ntop+; /栈顶元素下标+1 lpcarstack-lpcarinfor lpcarstack-ntop = carinfo; /把carinfo存入栈中/ 车辆信息从栈 lpcarstack 中弹出并存入 carinfovoid pop( lptcarstack &lpcarstack, tcarinfor &carinfo ) carinfo = lpcarstack-lpcarinfor lpcarstack-

16、ntop; /把栈中元素存入carinfo中 lpcarstack-ntop-; /栈顶元素下标减1/ 若栈 lpcarstack 空,返回 true;否则,返回 falsebool isstackempty( lptcarstack lpcarstack ) return lpcarstack-ntop = -1;/栈空时返回栈顶下标ntop值为-1/ 若栈 lpstackfull 满,返回 true;否则,返回 falsebool isstackfull( lptcarstack lpcarstack )/栈满返回ntop值为栈长度减1 return lpcarstack-ntop = (

17、 lpcarstack-nstacksize - 1 ); / 销毁栈 lpcarstack,将指针 lpcarstack 置为 nullvoid destroystack( lptcarstack &lpcarstack ) free( lpcarstack-lpcarinfor ); /释放车辆信息存储空间 free( lpcarstack ); /释放栈的存储空间 lpcarstack = null; /把栈lpcarstack置空/便道车辆信息(存储结构)typedef struct carnode / 链队结点信息 tcarinfor carinfo; / 车辆信息 struct c

18、arnode *lpnext; / 指向下一个元素的指针 tcarnode, *lptcarnode;/ 链队carqueue存储结构typedef struct carqueue lptcarnode lphead; / 头结点 lptcarnode lprear; / 指向当前队尾的指针 int neffsize; / 当前队中元素个数(有效车位) tcarqueue, *lptcarqueue;/ 初始化链队 lpcarqueueint initqueue( lptcarqueue &lpcarqueue ) lpcarqueue = ( lptcarqueue ) malloc( si

19、zeof( tcarqueue ) ); /分配对列存储空间 lpcarqueue-lphead =lpcarqueue-lprear=( lptcarnode) malloc( sizeof( tcarnode ) ); /分配头结点空间 if(!lpcarqueue-lphead) exit(overflow); /分配储存失败 lpcarqueue-lphead-lpnext = null; lpcarqueue-neffsize = 0; return ok;/ 车辆信息 carinfo 入队 lpcarqueueint enqueue( lptcarqueue &lpcarqueue

20、, tcarinfor carinfo )/插入元素carinfo为队lpcarqueue的新的队尾元素 lptcarnode lpcarnode = ( lptcarnode ) malloc( sizeof( carnode ) ); /分配结点空间 if(!lpcarnode) exit(overflow); /分配储存失败 lpcarnode-carinfo = carinfo; lpcarnode-lpnext = null; lpcarqueue-lprear-lpnext = lpcarnode; lpcarqueue-lprear = lpcarnode; lpcarqueue

21、-neffsize+; return ok;/ 队头元素从链队 lpcarqueue 中出队并存入 carinfoint dequeue( lptcarqueue &lpcarqueue, tcarinfor &carinfo ) if(lpcarqueue-lphead=lpcarqueue-lprear) return error; /队列里没有元素，返回error lptcarnode lptemp = lpcarqueue-lphead-lpnext; carinfo = lptemp-carinfo; lpcarqueue-lphead-lpnext = lptemp-lpnext;

22、 /指向下一结点 if(lpcarqueue-lprear=lptemp) lpcarqueue-lphead=lpcarqueue-lprear; /如果队列尾指针指向临时结点时，队列中没有元素 free( lptemp ); /释放临时队列 lpcarqueue-neffsize-; /容量-1 return ok;/ 若链队 lpcarqueue 为空,返回 true;否则,返回 falsebool isqueueempty( lptcarqueue lpcarqueue ) return lpcarqueue-neffsize = 0; /链队为空时返回长度为0/ 销毁链队 lpcar

23、queuevoid destroyqueue( lptcarqueue &lpcarqueue ) lptcarnode lpnextcarnode = null; for ( lptcarnode lpcarnode = lpcarqueue-lphead; lpcarnode != null; lpcarnode = lpnextcarnode ) lpnextcarnode = lpcarnode-lpnext; free( lpcarnode );/释放结点 lpcarnode信息 free( lpcarqueue );/释放队列 lpcarqueue lpcarqueue = nul

24、l;/ 将字符串时间格式转换为数字(分钟)格式,例如 12:36 将被转换为 756 =( 12 * 60 + 36 )int converttime ( char *lptime ) int nhour = 0; int nminu = 0; sscanf( lptime, %d:%d, &nhour, &nminu ); return nhour * 60 + nminu; / 根据在停车场内的停留时间 ncontiminu (分钟)计算费用double calcuexp ( int ncontiminu ) return ncontiminu * ( 5.0 / 60 );int mai

25、n( void ) int nparkcap = 0; / 停车场容量 putchar( n ); printf(tt*n); printf(tt=* *=n); printf(tt=*欢迎进入停车场管理系统*=n); printf(tt=* *=n); printf(tt*n); putchar( n ); printf( 请输入停车场容量: ); scanf( %d, &nparkcap ); lptcarstack lpcarstack = null; / 停车场,用栈模拟 initstack( lpcarstack, nparkcap );/创建停车场 lptcarqueue lpca

26、rqueue = null; / 便道,用链队模拟 initqueue( lpcarqueue ); /创建队列 char comtype = null; / 命令类型 char szuserinput128 = null ; / 用户输入 do clearscreen(); putchar( n ); puts( - ); puts( 命令类型 ); puts( a - 车辆到达 ); puts( d - 车辆离开 ); puts( o - 显示当前停车场和便道使用情况 ); puts( e - 退出程序 ); putchar( n ); puts( 例: ); puts( a,t45,14

27、:26 ); puts( d,e32,16:51 ); puts( e ); puts( o ); putchar( n ); printf( 请输入命令: ); scanf( %s, szuserinput ); puts( - ); char szcarinfor 128 = null ; sscanf( szuserinput, / 将命令类型与车辆信息分开存放 %c,%s, &comtype, / 用户输入的前半部分,即命令类型 szcarinfor / 用户输入的后半部分,即车辆信息 );/sscanf()从一个字符串中读进与指定格式相符的数据. char *lpcomloc = n

28、ull; / 车辆信息字符串中的逗号位置 for ( lpcomloc = szcarinfor; *lpcomloc != 0; lpcomloc+ ) if ( *lpcomloc = , ) break;/跳出整个for循环 *lpcomloc = 0; tcarinfor carinfo = null ; / 存储本次用户输入的车辆信息 strcpy( carinfo.szregmark, szcarinfor );/把szcarinfor复制到carinfo.szregmark(车牌号)里 if (comtype = a )/车辆到达 strcpy( carinfo.szarrtim

29、e, lpcomloc + 1 );/把lpcomloc + 1复制到carinfo.szarrtime里 if ( false = isstackfull( lpcarstack ) )/判断栈lpcarstack不满时 strcpy( carinfo.szenttime, carinfo.szarrtime );/车辆到达时间szarrtime复制给开始收费时间szenttime push( lpcarstack, carinfo ); printf( 已进入停车场第 %d 个车位n,lpcarstack-ntop + 1); printf( 车牌号:tt%sn, carinfo.szre

30、gmark ); printf( 进入时间:t%sn, carinfo.szenttime ); puts( 是否收费:t是 ); else enqueue( lpcarqueue, carinfo );printf( 停车场已满,已停放在便道的第 %d 个车位n,lpcarqueue-neffsize); printf( 车牌号:tt%sn, carinfo.szregmark ); printf( 停放时间:t%sn, carinfo.szarrtime ); puts( 是否收费:t否 ); else if (comtype = d ) strcpy( carinfo.szdeptime

31、, lpcomloc + 1 ); lptcarstack lptempcarstack = null; initstack( lptempcarstack, nparkcap );/ 创建临时lptempcarstack，nparkcap（停车辆） tcarinfor carinfoout = null ; bool biscarfound = false; /初始化biscarfound while ( false = isstackempty( lpcarstack ) )/判断栈lpcarstack不为空时 pop( lpcarstack, carinfoout ); /车辆出栈lpc

32、arstack if ( 0 != strcmp( carinfoout.szregmark, carinfo.szregmark ) )/比较 push( lptempcarstack, carinfoout );/车辆进栈lptempcarstack else biscarfound = true; break; while ( false = isstackempty( lptempcarstack ) )/判断临时栈不为空时 tcarinfor tempcarinfo = null ; pop( lptempcarstack, tempcarinfo ); push( lpcarsta

33、ck, tempcarinfo ); if ( false = biscarfound ) printf( 车牌号为 %s 的车未进入停车场.n, carinfo.szregmark ); pause( -n按任意键输入下一条信息.n ); continue; strcpy( carinfoout.szdeptime, carinfo.szdeptime ); int nenttime = converttime ( carinfoout.szenttime ); int ndeptime = converttime ( carinfoout.szdeptime ); int ncontimi

34、nu = ndeptime - nenttime; printf( 计费时段:t%s - %s (共 %d 分钟)n, carinfoout.szenttime, /开始计费时间 carinfoout.szdeptime, /车辆离开时间 ncontiminu /持续时间 ); double rexpense = calcuexp ( ncontiminu ); /计算停车费 printf( 应交纳的费用:t%.1lf 元n, rexpense ); if ( false = isqueueempty( lpcarqueue ) ) /如果队列lpcarqueue不空时 tcarinfor t

35、empcarinfo = null ; dequeue( lpcarqueue, tempcarinfo ); strcpy( tempcarinfo.szenttime, carinfoout.szdeptime ); push( lpcarstack, tempcarinfo ); puts( - ); printf( 停放在便道的第 1 个车位,车牌号为 %s 的车已进入停车场n, tempcarinfo.szregmark); else if (comtype = o ) clearscreen(); putchar( n ); puts( 停车场使用情况n ); puts( 车位t车牌号t到达时间t进入(开始计费)时间n); for ( int i = 0; i ntop; i+ ) printf( %dt%stt%stt%sn, i + 1, /车位 lpcarstack-lpcarinfor i.szregmark, /车牌号 lpcarstack-lpcarinfor i.szarrtime, /车辆到达时间 lpcarstack-lpcarinfor i.szenttime /车辆进停车场时间 ); /显示停车场车辆信息 putchar( n ); putchar( n ); putchar( n ); puts( 便道使用情况n