停车场管理实验报告.doc

1、页眉内容HUNAN UNIVERSITY课程实验报告题目：停车场管理学生姓名：学生学号：专业班级：指导老师：完成日期：一需求分析1. 输入形式第一次输入一个正整数，代表停车场容量大小。然后输入三个值，分别为字符、正整数、正整数，中间用空格隔开，分别代表车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。其中字符必须为“A,D,E”三者之一。 输入格式为：“ A 1 5 ”、“ D 1 15 ”和“ E 0 0 “。当用户输入的字符不是 ADE或者输入的不是正整数时，提示用户输入错误并重新输入2. 输出形式若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停

2、车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。（注：本程序中默认停车一小时收费10 元）3. 程序功能本程序可通过用户输入的车辆信息，输出该车的停车位置或者停车时间及应缴费用4. 测试数据请输入停车场容量： 5A 1 1车停在停车场第1个位置A 2 2车停在停车场第2个位置A 6 6车停在停车场第3个位置页眉内容D 1 4停车时间： 3缴纳费用：￥ 30D 2 6停车时间： 3缴纳费用：￥ 30F C 19.5输入有误，请重新输入E 0 0二概要设计1. 抽象数据类型将每辆车模拟成一个对象，每个对象具有车牌号时间等属性，所以定义一个 Car 类存储这些信息 class Carpu

3、blic:int CarNumber;/int ArriveTime;/int LeaveTime;/车牌号码到达时间离开时间使用栈模拟停车场，其ADT设计：ADT stack数据对象：Car 类数据关系：线性关系基本操作：void clear();/栈的初始化bool push(const Car& item);/栈的插入操作bool pop(Car& it);/栈的删除操作bool topValue(Car& it)/栈的顶层元素int length() constreturn size;/栈的实际长度使用队列模拟场外通道，其ADT设计如下：ADT Queue数据对象：Car 类数据关系：

4、线性关系基本操作：void clear();/队列的初始化页眉内容bool enqueue(const Car& it);/入队bool dequeue(Car& it);/出队int length() constreturn size;/队列的长度2. 算法基本思想 在该程序中，对停车场和场外通中每辆车停车的编号而言，他们有唯一的第一个元素和最后一个元素，而且除第一个元素以外的每个元素都有唯一的后继，除最后一个元素以外的每个元素都有唯一的前驱。因此这些元素具有线性关系。而且，对于停车场里面的汽车，他们逻辑次序是“先进后出，后进先出“的，且只在表头作插入和删除，所以可以使用栈来模拟停车场。而在

5、场外通道中的汽车，他们是”先进先出”的，在一端插入另一端删除操作，所以可以用队列来模拟场外通道。当汽车离开时，在它之后进入的车辆必须先退出再按原次序进入停车场，所以需要定义另外一个临时栈存储这些元素。 ( 本算法按用户输入的顺序进行车辆的停放，不是按车牌号码依次停放 ) （ 1）当有汽车需要进停车场停车时，进行入栈操作，若停车场已满，即栈已满，则将车停在场外通道里，进行入队操作，并记下此时的时间 ArriveTime ；（ 2）当有汽车需要离开停车场时，对该车对应的元素进行出栈操作，并将后面进来的车辆所对应的元素进行出栈操作，将这些元素（除了需要离开的车对应的元素）存入另外一个栈，即为需要离开

6、停车场的车让道，并记下此时的时间 LeaveTime；（ 3）在需要离开停车场的车成功离开停车场时，将存储在临时栈的那些元素按照原来的顺序依次插入原来的栈；（4） 如果队列不为空（即停车场场外通道上有车，这些车需要进入停车场停车），进行入栈操作 , 即进行（ 1）操作；（5）通过 LeaveTime 与 ArriveTime的差计算停车时间和停车费用（本程序默认停车每小时10 元）；3. 程序基本流程程序由个基本模块组成：输入模块：输入停车场的容量和车辆的相关信息；停车模块：根据车的信息，将该车对应的元素进行入栈操作；离开模块：根据车的信息，将该车对应的元素进行出栈操作，并将后面的元素存入一个

7、临时栈中；输出模块：输出该车停车位置或停车费用；三详细设计1. 物理数据类型页眉内容 停车场容量为正整数，使用整型数据存储n； 对于剩下的输入使用字符型、整型、整型存储，并将相应数据存入Car 类class Carpublic:int CarNumber;/int ArriveTime;/int LeaveTime;/车牌号码到达时间离开时间定义一个 Link 类用来存储元素值 element 及下一个存储表中下一个节点指针的 next 域，其 ADT设计如下：template class Linkpublic:Car element;Link *next;Link(const Car & e

8、lemval, Link* nextval = NULL)element = elemval;next = nextval;Link(Link *nextval = NULL)next = nextval;由于停车场容量一定，即栈空间大小不变，所以可以选用顺序表实现栈class AStck:public Stack/private:int size;/栈的长度int top;/栈顶元素Car *listArray;/顺序表保存栈元素public:AStack(int sz)size=sz;top=0;listArray=new Carsz; /构造函数页眉内容AStack()delete li

9、stArray; /void clear()top=0;/栈的清空析构函数bool push(const Car&item)if(top=size) return false;elselistArraytop+=item; return true; / 栈的插入bool pop(Car& item)if(top=0) return false;elseitem=listArray-top;return true;/栈的删除bool topValue(Car & it) constif(top=0) return false;else it=listArraytop-1; return true

10、;/获取栈顶元素int length()const return top; /;栈的长度由于该队列中元素添加操作和删除操作比较多，所以使用链式队列实现队列：template class Queue :public Linkprivate:int size;Link* front;Link* rear;页眉内容public:LQueue(int sz)front=NULL; rear=NULL;size=0Lqueue()deletefront; deleterear;void clear()while(front!=NULL)rear=front;front=front-next;delete

11、 rear;rear=NULL;size=0;/队列的清空bool enqueue(const Car& it)if(rear=NULL)front=rear=new Link(it NULL);elserear-next=new Link(it ,NULL);rear=rear-next;size+;return true;/ 入队bool dequeue(Car& it)if(size=0) return false;it=front-element;Link* ltemp=front;front=front-nextdelete ltemp;if(front=NULL) rear=NUL

12、L;siz-;页眉内容return true;/ 出队int length() const return size; /队列的长度2. 算法具体步骤(park为停车场对应的栈，out指临时栈，line指队列 )char c;input(c);/输入汽车停车或者离开或者结束；input(num);/输入汽车编号input(time);/输入汽车进入或离开时间Car C100;/Car的对象数组while(1)/停车switch(c)case(A)/进入停车场if(park is FULL) /停车场已满 enqueue(Cnum-1);output(line.length()/ 输出停车位置el

13、se park.push(Ca - 1);Ca - 1.ArriveTime = b;Ca - 1.carNumber = a;output （park.length()）/输出停车位置 break;case(D )/ 离开Ca - 1.LeaveTime = b;Ca - 1.carNumber = a; /进来与离开时间for (int i = 0; i a - 1; i+)/ 为要离开的车开道park.pop(Ci);/先删除前面的元素out.push(Ci);/将前面的元素存至临时栈中页眉内容park.topValue(Ci);/while(out.length()!=0)/将车复原f

14、or ( inti = 0; i a - 1; i+)out.pop(Ci);park.push(Ci);if(line.length()!=0)/将在通道内的车停进停车场for ( intj = a; j a + line.length() - 1; j+)line.dequeue(Cj);park.push(Cj);output（Ca - 1.LeaveTime - Ca - 1.ArriveTime）；/输出停留时间output（10*（Ca-1.LeaveTime-Ca-1.ArriveTime）；/输出停车费用break;case E :return 0;/输入 E时结束3. 算法时

15、空分析在该程序中，栈的插入的时间复杂度为 ? （1），而对栈中元素进行删除时，需要对该元素后面的所有元素都进行删除，并将他们存入另外一个临时栈中，到该元素顺利删除完毕时又重新存入原栈中，所以栈的删除的时间复杂度为 ? （n2）；4. 输入输出格式（停车费用每小时10 元）输入：5A 1 1A 6 6D 1 4页眉内容E 0 0输出：车停在停车场第1 个位置车停在场外通道第2个位置停车时间： 3缴纳费用：￥ 30四调试分析在使用类模板时，第一次没有使用模板参数列表，导致程序运行出错，后来将 Car 改成 class Car 后纠正了这个错 误五测试结果程序测试时界面截图如下：六用户使用说明1.

16、本程序用来处理停车场的问题；2. 运行程序后，需要要求进行输入，如若输入错误，系统提示输入错误请重新输入，第一次输入停车场容量，接下来请输入车辆相关信息；3. 车辆相关信息中用空格隔开，第一个输入 A或 D或 E，分别表示停车，车离开停车场和结束程序，第二个输入车牌号码，第三个输入到达停车场时间或离开停车场时间。七实验心得通过这次实验，我掌握了栈和队列的 ADT设计，以及如何用它们来解决问题附录代码：页眉内容#includ eusing namespace std;int judge();class Carpublic:int carNumber;int ArriveTime;int Leav

17、eTime;class Stackprivate:int size;int top;Car*listArray;public:int maxsize() return size; ;Stack(int sz)size = sz;top = 0;listArray = new Carsz;Stack()delete listArray;void clear()页眉内容top = 0;void push(const Car&it)if (top = size) ;else listArraytop+ = it;void pop(Car&it)if (top = 0);else it=listArr

18、ay-top;void topValue(Car&it)constif (top = 0);else it=listArraytop - 1;int length() return top; ;template class Linkpublic:Car element;Link *next;Link(const Car & elemval, Link* nextval = NULL)element = elemval;next = nextval;页眉内容Link(Link *nextval = NULL)next = nextval;template class Queue :public

19、Linkprivate:int size;Link* front;Link* rear;public:Queue() front = NULL; rear = NULL; size = 0; Queue()deletefront;deleterear;void clear()while (front != NULL)rear = front;front = front -next;delete rear;rear = NULL; size = 0;/ 队列的清空void enqueue(const Car& it)页眉内容if (rear =NULL)front = rear =new Lin

20、k(it,NULL) ;elserear-next = new Link(it, NULL);rear = rear-next;size+;/ 入队void dequeue(Car& it)if (size = 0);it = front-element;Link* ltemp = front;front = front -next;delete ltemp;if (front = NULL) rear = NULL;size-;/ 出队int length() const return size; ;/ 队列的长度int main()int n;cout 请输入停车场容量：;n=judge(

21、);while (n = 0)cout 输入有误，请重新输入。n 请输入停车场容量：;页眉内容n = judge();Car C100; Stack park = Stack(n); Stack out = Stack(n); Queue line; Car topCar;while (1)/ 停车char c;/ 停车 or 离开int a;/ 汽车车牌号码int b;/ 到达时间 or 离开时间cout cab;switch (c)case A:if (park.length()n + 1)park.push(Ca - 1);Ca - 1.ArriveTime = b;Ca - 1.carNumber = a;cout 该车停在第停车场第 park.length() 个位置 n;else if (park