《数据结构课程设计--模拟停车场管理问题》由会员分享,可在线阅读,更多相关《数据结构课程设计--模拟停车场管理问题(20页珍藏版)》请在金锄头文库上搜索。
1、目 录1、设计目的22、设计内容21.题目 22.问题描述23.基本要求24.实现提示23、算法思想分析34、算法描述与实现41.数据结构类型定义 42.主要算法的流程图及系统模块划分63.功能描述 74.程序代码 85、测试结果 176、总结体会 2011、设计目的数据结构是计算机专业的核心课程,是一门实践性很强的课程。为了学好这门课程,必须在掌握理论知识的同时,加强上机实践。课程设计是加强学生实践能力的一个强有力手段,要求学生掌握数据结构的应用、算法的编写、将算法转换成程序并上机调试的基本方法,还要求学生在完成程序设计的同时能够写出比较规范的设计报告。本课程设计的目的就是要达到理论与实际应
2、用相结合,使同学们能够根据数据对象的特性,学会数据组织的方法,能把现实世界中的实际问题在计算机内部表示出来,并培养学生的基本程序设计素养和软件工作者工作作风。2、设计内容1.题目:模拟停车场管理问题2.问题描述:设停车场只有一个可停放几辆汽车的狭长通道,且只有一个大门可供汽车进出。汽车在停车场按车辆到来的先后顺序依次排列,若车场内已停满几辆汽车,则后来的汽车只能在门外的便道上等候,一旦停车场内有车开走,则排在便道上的第一辆车即可进入;当停车场内某辆车要离开时,由于停车场是狭长的通道,在它之后开入的车辆必须先退出车场为它让路,待该辆车开出大门后,为它让路的车辆在按原次序进入车场。每辆停放在车场的
3、车在它离开停车场时必须按它停留的时间长短交纳费用。3.基本要求:试为停车场编制按上述要求进行管理的模拟程序。在这里假设汽车不能从便道上开走。试设计一个停车场管理程序。4.实现提示:以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻,例如:(A,1,5)表示一号牌照车在 5 这个时刻到达,而(D,5,20)表示 5 号牌照车在 20 这个时刻离去,整个程序可以在输入信息为(E,0,0)时结束。对每一组输入数据进行操作后的输出数据为:若是车辆到达,则输出汽车在停车场内或便道上的停
4、车位置;若是车离2去;则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。栈以顺序结构实现,队列以链表实现。需另设一个栈,临时停放为给要离去的汽车让路而从停车场退出来的汽车。3、算法思想分析1.输入根据提示输入停车场容量 n。2.创建根据读入的停车场容量 n,创建长度为 n 的栈(停车场) 。3.主要操作1)插入(车辆停入)根据提示往栈中插入元素(车辆信息) ,即使车辆停在停车场中。首先检查停车场是否已满,若不满,则车辆停放在停车场中,记录车辆到达时间,并把此时间作为开始计费时间。若插入的元素个数超过停车场的容量,则此后的车辆停在便道上用队列表示,即元素储存在队列中。2)
5、删除(车辆离开)根据提示删除栈中的元素(车辆信息) ,即使车辆离开停车场,同时停在便道上的车辆停入停车场中。当车辆离开时,首先要寻找到要离开车辆的车牌号,若车是从停车场离开,则在它之后进入的车辆必须先退出(进入临时栈)为它让路,待该辆车开出大门外,其它车辆再按原次序进入停车场,并将停放在便道上第一位置的车开进停车场,离开的车辆按其在停车场内停留的时间交费,并把离开车辆的离开时间作为便道上第一位置的车进入停车场的进入时间和开始计费时间。3)显示根据提示操作,显示当前停车场和便道使用情况。4)退出释放停车场和便道(栈和队列)上的车辆信息等,退出当前运行程序。34、算法描述与实现1.数据结构类型定义
6、/停车场车辆信息(存储结构)typedef struct carinfor / 车辆信息char szRegMark64; / 车牌号char szArrTime16; / 到达时间char szEntTime16; / 进入停车场(开始计费)时间char szDepTime16; / 离开时间 TCARINFOR, *LPTCARINFOR;/栈 carstack 存储结构typedef struct carstack LPTCARINFOR lpCarInfor; / 车辆信息 int nTop; / 栈顶元素下标int nStackSize; / 栈容量 TCARSTACK, *LPTC
7、ARSTACK;szRegMark64/车牌号szArrTime16/到达时间szEntTime16/计费时间szDepTime16/离开时间carinfor停车场车辆信息存储结构栈顶元素下标nTop停车场 carstack(栈)存储结构lpcarinfornStackSize=nTop+14/便道车辆信息(存储结构)typedef struct carnode / 链队结点信息TCARINFOR carinfo; / 车辆信息struct carnode *lpNext; / 指向下一个元素的指针 TCARNODE, *LPTCARNODE;/ 链队 carqueue 存储结构typedef
8、 struct carqueue LPTCARNODE lpHead; / 头结点LPTCARNODE lpRear; / 指向当前队尾的指针int nEffSize; / 当前队中元素个数 (有效车位) TCARQUEUE, *LPTCARQUEUE;szRegMark64/车牌号szArrTime16/到达时间szEntTime16/计费时间szDepTime16/离开时间carinfor便道车辆信息存储结构LPTCARNODE lpRear便道 carsqueue(队列)存储结构LPTCARNODE lpHeadlpcarinfor next52.主要算法的流程图及功能描述(1)流程图:
9、(2)系统模块划分:程序运行界面输入停车场容量,创建栈开 始根据当前提示操作取得 key 值向栈或队列加入元素信息向栈或队列删除元素信息显示栈和队列的停车情况退出程序E、释放空间ADO车进入停车场 判断停车场是否已满 车进入停车场 记录时间开始计费车辆离开记录离开时间计算持续时间和费用否是进入便道记录进入时间但不计费判断停车场是否有空位否继续等待是6(3)算法描述:(1)void InitStack( LPTCARSTACK &lpCarStack, int nSize )初始化栈 lpCarStack,,为栈和车辆信息分配储存空间,将其容量设置为 nSize。int InitQueue( L
10、PTCARQUEUE &lpCarQueue )初始化链队 lpCarQueue,分配队列存储空间和头结点空间,有效车位初始化。(2)void Push( LPTCARSTACK &lpCarStack, TCARINFOR carinfo )向栈中加入元素信息:车辆信息 carinfo 入栈 lpCarStack,栈顶元素下标+1。int EnQueue( LPTCARQUEUE &lpCarQueue, TCARINFOR carinfo )向队列中加入元素信息:分配结点空间,车辆信息 carinfo 入队 lpCarQueue,顺序存储到队列中,有效车位加 1。(3)void Pop(
11、LPTCARSTACK &lpCarStack, TCARINFOR &carinfo )从栈中删除元素时:车辆信息从栈 lpCarStack 中弹出并存入 carinfo 中,栈顶元素下标-1。int DeQueue( LPTCARQUEUE &lpCarQueue, TCARINFOR &carinfo )从队列中删除元素时:队头元素从链队 lpCarQueue 中出队并存入 carinfo,当队列中无元素时,返回 ERROR;否则 carinfo 中信息存入临时队列中,再释放临时队列,队列长度减 1。7(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 carinfor / 车辆信息ch
13、ar szRegMark64; / 车牌号char szArrTime16; / 到达时间char szEntTime16; / 进入停车场(开始计费)时间char szDepTime16; / 离开时间 TCARINFOR, *LPTCARINFOR;/栈 carstack 存储结构typedef struct carstack LPTCARINFOR lpCarInfor; / 车辆信息 int nTop; / 栈顶元素下标int nStackSize; / 栈容量 TCARSTACK, *LPTCARSTACK;/ 初始化栈 lpCarStack, 将其容量设置为 nSizevoid I
14、nitStack( LPTCARSTACK &lpCarStack, int nSize )8lpCarStack = ( LPTCARSTACK ) malloc( sizeof ( TCARSTACK ) ); /栈储存分配lpCarStack-lpCarInfor = ( LPTCARINFOR ) malloc(nSize * sizeof ( TCARINFOR ); /栈中车辆信息储存分配lpCarStack-nTop = -1; /栈中无元素lpCarStack-nStackSize = nSize; /栈的长度为 nSize/ 车辆信息 carinfo 入栈 lpCarStac
15、kvoid Push( LPTCARSTACK &lpCarStack, TCARINFOR carinfo )lpCarStack-nTop+; /栈顶元素下标 +1lpCarStack-lpCarInfor lpCarStack-nTop = carinfo; /把 carinfo 存入栈中/ 车辆信息从栈 lpCarStack 中弹出并存入 carinfovoid Pop( LPTCARSTACK &lpCarStack, TCARINFOR &carinfo )carinfo = lpCarStack-lpCarInfor lpCarStack-nTop; /把栈中元素存入 carinfo中lpCarStack-nTop-; /栈顶元素下标减 1/ 若栈 lpCarstack 空,返回 TRUE;否则,返回 FALSEBOOL IsStackEmpty( LPTCARS