数据结构课程设计
学 院 信息科学与工程学院 专 业 计算机科学与技术 班 级 计1005 姓 名 ***
学 号 2010******* 指导教师 ***
2012 年 3 月 11 日
一、需求分析
1、【问题描述】
设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北门向南排列（大门在最南端，最先到达的第一辆车放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
2、【基本要求】
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或里去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在听车场内停留的时间和应缴纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。
3、【实现提示】
需另设一个栈，临时停放为给要离去的汽车让路二从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
二、概要设计
1、设计思想
此停车场管理系统是在一个狭长的通道上的，而且只有一个大门可以供车辆进出，并且要实现停车场内某辆车要离开时，在它之后进入停车场的车
都必须先退出停车场为它让路，待其开出停车场后，这些车再依原来的次序进场的功能，就可以设计两个顺序栈，其中一个栈用来模拟停车场，另一个栈用来模拟临时停车场，该临时停车场用来存放当有车辆离开时，原来停车场内为其让路的车辆。至于当停车场已满时，需要停放车辆的便道可以用一个链队列来实现。当停车场内开走一辆车时，便道上便有一辆车进入停车场，此时只需要改变便道上车辆结点的连接方式就可以了，使便道上第一辆车进入停车场这个栈，并且使便道上原来的第二辆车成为便道上的第一辆车，此时只需将模拟便道的链队列的头结点连到原来的第二辆车上就可以了。
2、实现方法
对于此停车场管理系统的实现，就是用两个顺序栈来分别模拟停车场以及停车场内车辆为其它车辆让路时退出停车的临时停放地点。至于便道上车辆的停放则用一个链队列来实现，此时，便道上车辆的离开或者进入停车场只需改变此链队列上的结点而已。对于要对停车场内的车辆根据其停放时间收取相应的停车费用，可以记录下车辆进入以及离开停车场的时间，再用时间差乘以相应的单价并且打印出最后的费用就可以实现了。
三、详细设计
函数功能：
1、Status InitStack(Park &P){//初始化停车场
P.base=(CarNode*)malloc(SIZE*sizeof(Car1)); if(!P.base) exit(OVERFLOW); P.top=P.base; P.stacksize=0; return OK; }
功能：构造一个栈，并置为空栈。
2、Status Push(Park &P,CarNode e){//车进入停车场 *P.top++=e; ++P.stacksize;
return OK; }
功能：定义入栈函数Push
3、Status Pop(Park &P,CarNode &e){//车离开停车场 if(P.top==P.base)
printf(\停车场为空。\ else {
e=*--P.top; --P.stacksize; }
return OK;
}
功能：定义出栈函数Pop。
4、Status InitQueue(Shortcut &S){//初始化便道 S.front=S.rear=(CarPtr)malloc(sizeof(Car2)); if(!S.front||!S.rear) exit(OVERFLOW); S.front->next=NULL; S.length=0; return OK; }
功能：构造一个队列，并置为空队列。
5、Status EnQueue(Shortcut &S,int number,int ar_time){//车进入便道 CarPtr p;
p=(CarPtr)malloc(sizeof(Car2)); if(!p) exit(OVERFLOW); p->number=number; p->ar_time=ar_time; p->next=NULL; S.rear->next=p; S.rear=p; ++S.length; return OK; }
功能：定义入队函数EnQueue。
6、Status DeQueue(Shortcut &S,CarPtr &w){//车离开便道
if(S.length == 0)
printf(\通道为空。\ else {
w = S.front->next;
S.front->next=S.front->next->next; --S.length; }
return OK; }
功能：定义出队函数DeQueue。
7、Status Arrival(Park &P,Shortcut &S){//对进站车辆的处理 int number,ar_time;
printf(\请输入车牌号：\ scanf(\ printf(\进场的时刻:\ scanf(\ if(P.stacksize CarNode c; c.number=number; c.ar_time=ar_time; Push(P,c); printf(\该车应停在第%d号车道。\\n\ } else { EnQueue(S,number,ar_time); printf(\停车场已满，请暂时停在便道的第%d个位置。\\n\ } return OK; } 功能：对进站车辆的处理，在P.stacksize 入停车场，并记录车的车牌号及车进停车场的时刻。另外，当P.stacksize>=SIZE，即停车场已满时，将车停在便道上，并打印“停车场已满，请暂时停在便道的第S.length个位置。 8、Status Leave(Park &P,Park &P1,Shortcut &S){//对离站车辆的处理 int number,le_time,flag=1,money,ar_time; printf(\请输入车牌号：\ scanf(\