1、 数据结构课程设计说明书题目: 停车场问题 院 系： 计算机科学与工程学院 专业班级： 计算机08-4班 学 号： 2008302886 学生姓名： 指导教师： 2010年 02 月 24 日 课程设计（论文）任务书 计算机科学与工程 学院 计算机软件教研室学 号 学生姓名 专业（班级）计算计08-4设计题目 停车场问题设计技术参数系统平台：Windows XP开发工具：Microsoft Visual C+ 6.0设计要求(1) 利用栈和队列实现车的停放，等候以及结算；(2) 每一组输入数据包括三个数据项：汽车“到达”或“离去”的信息，汽车牌照号码以及到达或离去的时刻；（3）对每一组输入数据
2、进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）；工作量课程设计报告要求不少于3000字。源程序要求不少于300行工作计划2009年12月17日-2009年12月20日 查找相关资料2009年12月2日-2009年12月31日 代码编写2010年2月19日-2010年2月23日 查错及调整程序 2010年2月24日-2010年2月27日 撰写实验报告参考资料1秦锋.数据结构（C语言版）.合肥:中国科大出版社,20072温秀梅,丁学均.Visual C+面向对象程序设计.北京:清华大
3、学出版社,20053何钦铭,颜晖.C语言程序设计.北京:高等教育出版社,2008指导教师签字教研室主任签字 2009年 12月 29 日 学生姓名： 高芹 学号： 2008302886 专业班级： 计08-4 课程设计题目： 停车场问题 指导教师评语： 成绩： 指导教师： 年 月 日安徽理工大学课程设计（论文）成绩评定表目录1 问题描述12 需求分析13 总体设计23.1 栈和队列在使用前的数据类型定义及各自的结点类型24 总结12参考文献121 问题描述利用栈和队列实现车的停放，等候以及结算；在执行时使用菜单方式实现，选择需要的停车服务，执行后可以显示打印结果。设停车场内只有一个可停放N辆汽
4、车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满N辆汽车，则后的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入的数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”的信息，汽车牌照号码以及到
5、达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。2 需求分析 根据问题要求，我认为，虽然本程序对于现实生活中的用处不是很现实，但是可以丰富我们对栈和队列的理解，也可以让我们学会用栈和队列来模拟现实中的问题，本程序要实现的功能有：（1） 用顺序结构栈和链表结构队列来模拟停车场和过道：为了能用栈模拟停车场和用队列队列模拟过道，首先得为栈和链式队列定义结点，然后为栈和队列中各函数的实现包括初始化栈和队列还有栈的判断栈
6、空判断栈满来提示不能出车和什么时候过道上的车进入停车场，以入栈出栈来模拟车辆的出入停车场，以判断队列是否为空来提示过道是否有车来进入停车场和入队来模拟车等候在过道上出队来让过道上的车进入停车场，还有取队列首个元素来模拟排在队首的车进入停车场。（2） 停车函数：当选择是停放车辆时，则先检查停车场有没有满，如果没满就会调用停车函数，把车的信息输入到栈内，表示该车已进入停车场，并输出本车在停车场内的具体位置。（3） 等候函数：在选择停放车辆时，但停车场已满，则只能调用等候函数。将车辆的输入信息存入队列中，表示该车需要在过道内等候，并输出本车在过道内的具体位置。（4） 车辆出站函数：当选择车辆出站时，
7、则要输出汽车在停车场内停留的时间和应交纳的费用，其中不包括车在过道内等候所用的时间。3 总体设计3.1栈和队列在使用前的数据类型定义及各自的结点类型在设计程序时，为了能更简单地得到用户输入的准确的时间，我定义了一个时间数据类型，其中包括小时信息和分钟信息。typedef struct /定义时间类型用来存储车辆进出站时间int hour;int minute;time;typedef struct /定义汽车数据类型用来存储栈和队列中元素值 char name8;char Carnum6;time ti;Car;typedef struct /定义栈结点类型模拟停车场 Car dataMAXS
8、IZE; int top;SeqStack,*pSeqStack;typedef struct node /定义结点Car data; struct node *next;Qnode,*PQnode;typedef struct /定义链式队列结点类型模拟通道 PQnode front,rear; LinkQueue,*PLinkQueue;程序在执行时，用到的主要函数有：pSeqStack InitStack() /初始化栈int StackEmpty(pSeqStack S) /判栈空int StackFull(pSeqStack S) /判栈满int Push(pSeqStack S,c
9、har name,char num,time arriveti) /入栈 /Car x;if(S-top = MAXSIZE-1)/cout栈已满!top+; strcpy(S-dataS-top.name,name);strcpy(S-dataS-top.Carnum,num);S-dataS-top.ti.hour=arriveti.hour;S-dataS-top.ti.minute=arriveti.minute;return 1;int Pop(pSeqStack S) /出栈 if(StackEmpty(S)return 0;else S-top-; /*此出栈只是将top指针下移
10、了位置，而原本的top所指结点不考虑了return 1;PLinkQueue InitQueue() /初始化队列int QueueEmpty(PLinkQueue Q) /判队空int InQueue(PLinkQueue Q,char num,char name) /入队列 PQnode p;p=(PQnode)malloc(sizeof(Qnode);if( !p)cout内存溢出!data.Carnum,num);strcpy(p-data.name,name);p-next=NULL;if(QueueEmpty(Q)Q-front=Q-rear=p;else Q-rear-next=
11、p;Q-rear=p;return 1;int OutQueue(PLinkQueue Q) /出队PQnode p;p=(PQnode)malloc(sizeof(Qnode);if(!p)cout内存溢出！front;Q-front =Q-front-next;free(p);if(!Q-front)Q-rear=NULL;return 1;int CountQueue(PLinkQueue Q) /计算队列中车辆个数，显示通道中车辆停放位置int count=0;PQnode p;p=Q-front;while(p!=NULL)count+;p=p-next; return count;
12、int DeleteQueue(PLinkQueue Q,char num,char name) /取队头元素，为后来的进栈找元素int count=0;PQnode p;p=Q-front;while(p!=NULL)count+;p=p-next; return count;int InsertCar(pSeqStack S,char name,char num,time arriveti) /单个车辆入站 Push(S,name,num,arriveti);cout当前车辆停放在停车场第top+1位endl;return 1; 图1 单个车辆进站double ExitCar(pSeqSt
13、ack S,PLinkQueue Q,char name,char num,time leaveti) /车辆出站/int i,position,flag=0;/char num6; /要出站的车的车牌号for(i=0;itop+1;i+)if(strcmp(S-datai.Carnum,num)=0) /*strcmp()结果0为true,1为false,而在while()条件判断时1为true,0为false, 即：将车牌号不匹配的车入栈n，出栈s，取车牌号匹配的计算费用 position=i;flag=1;if(! flag)cout没有此辆车endl;pSeqStack S1;S1=I
14、nitStack(); /临时栈，存放在要出站车辆之后进入车场的车辆if(!S1)cout车辆出站失败！top;iposition;i-)Pop(S);/*车场出车*/Push(S1,S-dataS-top.name,S-dataS-top.Carnum,S-dataS-top.ti);/*临时栈入车*/double account=0;account=(leaveti.hour-S-dataS-top.ti.hour)*60+(leaveti.minute-S-dataS-top.ti.minute)*price;Pop(S);/*所指定的车辆出站*/while(S1-top!=-1) Pu
15、sh(S,S1-dataS1-top.name,S1-dataS-top.Carnum,S1-dataS1-top.ti);/*车场入车*/Pop(S1);/*临时栈出车*/if(Q-rear!=NULL&Q-front!=NULL)/*通道内有车*/DeleteQueue(Q,num,name);Push(S,name,num,leaveti);/cout通道车辆进站成功！endl; return account; 图2 车辆结算int Waiting(PLinkQueue Q,char name,char num) /等候停放InQueue(Q,name,num);cout当前车辆停放在通
16、道第CountQueue(Q)位top=-1)cout车场为空！endl;cout当前车场内车辆信息是：endl;cout车牌号：ends车主姓名：ends到达时间：endl;for(i=0;itop+1;i+)coutdatai.Carnumendsdatai.nameendsdatai.ti.hour : datai.ti.minuterear!=NULL&Q-front!=NULL)/Q-front=Q-front-next;/Q-rear=Q-rear;cout通道内车辆信息：endl;cout车主姓名：ends车牌号：endl;coutfront-data.nameendsfront
17、-data.Carnumfront=Q-front-next; 图4 车站内信息显示void main()char name8,num6; time arriveti,leaveti; /定义两个时间变量int select; pSeqStack S; /定义栈作为停车场S=InitStack(); PLinkQueue Q; /定义链队列作为通道Q=InitQueue();cout=快乐家园停车场=endl;coutendl;while (1)cout1、停放车辆：endl;cout2、输出车场内车辆信息：endl;cout3、车辆结算：endl;cout0、退出程序。endl;couten
18、dl;cout请选择要执行的操作：select;switch(select)case 0:exit(0); break;case 1: cout请输入到达车辆的信息：endl; cout请输入车主姓名：name; cout请输入车牌号：num; cout请输入车的到达时间的小时信息(0-23)：arriveti.hour; cout请输入车的到达时间的分钟信息(0-59)：arriveti.minute;if(StackFull(S)Waiting(Q,name,num);else InsertCar(S,name,num,arriveti);coutendl;break;case 2:cou
19、t当前车场信息：endl;Show(S,Q);coutendl;break;case 3:double money; if(StackEmpty(S)cout对不起，停车场还没车停放endl;money=0; elsecout请输入车主姓名：name;coutnum;coutleaveti.hour;coutleaveti.minute; money=ExitCar(S,Q,name,num,leaveti);cout你停车的总时间为money/price分钟endl;cout你所需交纳的停车费用为money元endl;break;default:cout输入错误，请重新选择！endl;bre
20、ak;/end switch/end while /end main()4 总结 通过这次课程设计，我对于编写程序有了更新的认识，更多的感触。首先是要把C语言这门课学好，作为编程的基础，应用是很广泛的。就像在处理停车场问题时，因为大概有半年时间没有学C了，好多函数都不怎么会用了，于是只好又花时间把能用到的知识点好好地看了一遍，while循环的循环条件，字符串string相关函数的使用方法。其实，在处理停车场问题时，更重要的还是在数据结构书上的栈和队列的应用。为了更顺利的应用这两个知识点，我又把书上栈和队列的相关代码理解了一遍。还有就是在设计中处理时间记录上，我定义了一个时间time数据类型，来
21、记录时和分钟信息。在设计程序时，要考虑到好多问题，当车场停放已满时，需要将下一辆要停放的车放在通道内，等候停放；而先进入停车场内的车，在出站时需要将在它之后进入的车退出来，等车辆出站后，再按原顺序进入站，此时就需要定义一个临时的栈，来存放之后进入的车，等原来停放在车场的车都进入后，通道上的第一辆车要进入车场，并把出站的车的离开时间作为由通道进入停车场的到达时间。而在处理结算算法时，牵涉到元素在各存储位置的转移，需要考虑到程序的健壮性，技术要求更高了。然后，认识到程序需要经常编写，经常练。在调程序时可能会出现不少的错误提示，这时就需要你静下心来慢慢分析，一个错误一个错误的过，还有在不懂的地方，需要研究或询问别人，千万不能就模糊地过去了！有跟自己的想法不同的，可用自己的方法试着调一下。分析数据结构这门课，它是培养我们编程思维的一种很好的方法，我们要想把编程学好，需要把思维培养到能很自然的把问题转换为学过的知识的水平。参考文献1秦锋.数据结构（C语言版）.合肥:中国科大出版社,20072温秀梅,丁学均.Visual C+面向对象程序设计.北京:清华大学出版社,20053 何钦铭,颜晖.C语言程序设计.北京:高等教育出版社,2008
