数据结构课程设计停车场管理问题未完

1、停车场管理实验报告 专 业 数学与应用数学 班 级 121092 学 生 贺钰植 学 号 20091001979 实验题目：停车场管理系统一、需求分析1.问题描述停车场是一条可以停放n辆车的狭窄通道，且只有一个大门汽车停放安到达时间的先后依次由北向南排列（大门在最南端，最先到达的第一辆车停在最北端）若停车场已经停满n辆车，后来的汽车在便道上等候，一旦有车开走，排在便道上的第一辆车可以开入；当停车场的某辆车要离开时，停在他后面的车要先后退为他让路，等它开出后其他车在按照原次序开入车场，每两停在车场的车要安时间长短缴费。 要求：以栈模拟停车场，以队列车场外的便道，按照从终端输入的数据序列进行模拟管

2、理。每一组数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码、以及到达或离去的时刻。对每一组数据进行操作后的信息为：若是车辆到达，则输出汽车在停车场的内或便道上的位置：若是车辆离去则输出汽车在停车场内的停留时间和应缴纳的费用（在便道上的停留时间不收费）。栈以顺序结构实现，队列以链表结构实现2.基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项；汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽

3、车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。测试数据： 设n=2,输入数据为：（A，1，5），（A，2，10），（D，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。3.拓展内容（1）汽车可有不同种类，则它们的占地面积不同，收费标准也不同。 （2）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （3）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。二、设 计 1.设计思想由于停车场是一个狭窄

4、通道，而且只有一个大门可供汽车进出，问题要求汽车停车场内按车辆到达时间的先后顺序，依次由北向南排列。由此很容易联想到数据结构中的堆栈模型，因此可首先设计一个堆栈，以堆栈来模拟停车场，我设计用顺序存储结构来存储停车场内的车辆信息，并给车辆按进栈顺序编号，当停车场内某辆车要离开时，在他之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入停车场。这是个一退一进的过程，而且让道的汽车必须保持原有的先后顺序，因此可再设计一个堆栈，以之来暂时存放为出站汽车暂时让道的汽车。当停车场满后，继续进来的汽车需要停放在停车场旁边的便道上等候，若停车场有汽车开走，则按排队的先后顺序依次进站

5、，最先进入便道的汽车将会最先进入停车场，这完全是一个先进先出模型，因此可设计一个队列来模拟便道，队列中的数据元素设计成汽车的车牌号，并以链表的形式存储。另外，停车场根据汽车在停车场内停放的总时长来收费的，在便道上的时间不计费，因此必须记录车辆进入停车场时的时间和车辆离开停车场时的时间，然后计算、显示费用情况。2.概要设计（1）Status InitStack(SqStack &s)构造一个空栈，用以表示车辆信息。（2）Status Push(SqStack &s,SElemType e)向栈中插入元素，表示车辆进入信息（3）Status Pop(SqStack &s,S

6、ElemType &e)若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK，否则返回ERROR,用以表示车辆开出的信息。 （4）Status InitQueue(LinkQueue &Q)构造一个空队列表示便道车辆信息。（5）Status EnQueue(LinkQueue &Q,SElemType e)队列的插入表示车辆进入便道等候的信息。（6）Status DeQueue(LinkQueue &Q,SElemType &e)若队列不空，则删除Q的对头元素，用e返回其值，并返回OK，否则返回ERROR，表示车辆开出便道进入停车场。（7）void C

7、arArrival(SqStack &s,LinkQueue &Q)对汽车到达时处理，记下车号到达时刻，车号等等的信息。（8）void CarDeparture(SqStack &s,LinkQueue &Q)车辆在停车场整个过程的信息，其中包括收费信息。3详细设计下面是整个程序的算法的设计框架。开始初始化两个栈和及一个队列。进入主菜单车到达车离开退出停车场前车辆进临时栈对对车辆计费便道车信息车场内信息判便道是否有车车场是否为空列表显示栈元素出栈队列中元素进栈队列中元素出队元素进栈便道车进车场元素进队列判断栈是否为满结束退出列表显示是否否是否是三、源程序清单#i

8、nclude<stdio.h>#include<stdlib.h>#include<iostream.h>typedef int Status; /元素类型int flag=0;typedef structint carnumber; /车号int time; /汽车“到”或“离”的时刻SElemType;/以下是对栈数据类型的定义#define STACK_INIT_SIZE 2#define STACKINCREMENT 1typedef structSElemType *base; SElemType *top; int stacksize; SqSt

9、ack;Status InitStack(SqStack &s) /构造一个空栈Ss.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType);if(!s.base) exit(0);s.top=s.base;s.stacksize=STACK_INIT_SIZE;return 1;Status Push(SqStack &s,SElemType e)/插入元素e为新的栈顶元素if(s.top-s.base>=s.stacksize)/栈满s.base=(SElemType * ) realloc(s.ba

10、se,(s.stacksize+STACKINCREMENT) * sizeof(SElemType);if(!s.base) exit(0); /存储分配失败s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return 1;Status Pop(SqStack &s,SElemType &e)/若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK，否则返回ERRORif(s.top=s.base) return 0;e=*-s.top;return 1;typedef struct QNodeSE

11、lemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;Status InitQueue(LinkQueue &Q) /构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(0);Q.front->next=NULL;return 1;Status EnQueue(LinkQueue &Q,SElemType e) /插入元素e为新的队尾元

12、素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(0);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return 1;Status DeQueue(LinkQueue &Q,SElemType &e)/若队列不空，则删除Q的对头元素，用e返回其值，并返回OK，否则返回ERRORQueuePtr p;if(Q.front=Q.rear) return 0;p=Q.front->next;e=p->data; p->next=NULL

13、;Q.front->next=p->next;if(Q.rear=p) Q.rear=Q.front;free(p);return 1; /对汽车到达时的处理void CarArrival(SqStack &s,LinkQueue &Q)SElemType e;cout<<"请输入车号:"cin>>e.carnumber;cout<<"请输入到达时刻:"cin>>e.time;if(s.top-s.base>s.stacksize)EnQueue(Q,e);cout<

14、<"-n"cout<<"|车号| 停车位置 | 到达时刻 |n"cout<<"-n"cout<<"|"<<e.carnumber<<"| 停在便道上等待|"<<e.time<<" |"<<"n"cout<<"-n"elsePush(s,e);*s.top+=e;cout<<"-n"cout&l

15、t;<"|车号| 停车位置 | 到达时刻 |n"cout<<"-n"cout<<"|"<<e.carnumber<<"| 停在停场内"<<+flag<<"号位|"<<e.time<<" |"<<"n"cout<<"-n"void CarDeparture(SqStack &s,LinkQueue &

16、;Q)SqStack T; /临时倒车处int money;/停留时刻SElemType a,e;int carnumber,time;InitStack(T);/构造临时倒车处cout<<"请输入车号:"<<endl;cin>>carnumber;cout<<"请输入离去时刻:"<<endl;cin>>time;a=*(s.top-1);doPop(s,e);Push(T,e);*s.top-=e;a=*(s.top-1);while(e.carnumber!=carnumber)

17、;Pop(s,e); money=time-e.time;cout<<"武昌停车场收费单 n"cout<<"-n"cout<<"|车号 |到达时刻 |离去时刻 |停留时刻 |费用(元) |n"cout<<"-n"cout<<"|"<<carnumber<<"|"<<e.time<<" |"<<time<<"|&quo

18、t;<<money<<" |"<<money*2<<" |"<<"n"cout<<"-n"flag-;while(T.base!=T.top)Pop(T,e);*s.top+=e;while(Q.front!=Q.rear)if(s.top-s.base<s.stacksize)DeQueue(Q,e); Push(s,e);*s.top+=e;if(s.top-s.base> STACK_INIT_SIZE)cout<<"n便道上有车进入停车场!"<<"n此车停在"<<+flag<<"车位"<<endl; void shurujiesu()cout<<"nn输入结束（END)!nn"void main() cha