HUNAN UNIVERSITY 课程实验报告题目：停车场管理学生姓名：学生学号：专业班级：指导老师：完成日期：一．需求分析1.输入形式第一次输入一个正整数，代表停车场容量大小。
然后输入三个值，分别为字符、正整数、正整数，中间用空格隔开，分别代表车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。
其中字符必须为“A,D,E”三者之一。
输入格式为：“A 1 5”、“D 1 15”和“E 0 0“。
当用户输入的字符不是ADE或者输入的不是正整数时，提示用户输入错误并重新输入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 Car{public: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() const{return size};//栈的实际长度使用队列模拟场外通道，其ADT设计如下：ADT Queue数据对象：Car类数据关系：线性关系基本操作：void clear();//队列的初始化bool enqueue(const Car& it);//入队bool dequeue(Car& it);//出队int length() const{return size;};//队列的长度2.算法基本思想①在该程序中，对停车场和场外通中每辆车停车的编号而言，他们有唯一的第一个元素和最后一个元素，而且除第一个元素以外的每个元素都有唯一的后继，除最后一个元素以外的每个元素都有唯一的前驱。
因此这些元素具有线性关系。
而且，对于停车场里面的汽车，他们逻辑次序是“先进后出，后进先出“的，且只在表头作插入和删除，所以可以使用栈来模拟停车场。
而在场外通道中的汽车，他们是”先进先出”的，在一端插入另一端删除操作，所以可以用队列来模拟场外通道。
当汽车离开时，在它之后进入的车辆必须先退出再按原次序进入停车场，所以需要定义另外一个临时栈存储这些元素。
(本算法按用户输入的顺序进行车辆的停放，不是按车牌号码依次停放)②（1）当有汽车需要进停车场停车时，进行入栈操作，若停车场已满，即栈已满，则将车停在场外通道里，进行入队操作，并记下此时的时间ArriveTime；（2）当有汽车需要离开停车场时，对该车对应的元素进行出栈操作，并将后面进来的车辆所对应的元素进行出栈操作，将这些元素（除了需要离开的车对应的元素）存入另外一个栈，即为需要离开停车场的车让道，并记下此时的时间LeaveTime；（3）在需要离开停车场的车成功离开停车场时，将存储在临时栈的那些元素按照原来的顺序依次插入原来的栈；（4）如果队列不为空（即停车场场外通道上有车，这些车需要进入停车场停车），进行入栈操作,即进行（1）操作；（5）通过LeaveTime 与ArriveTime的差计算停车时间和停车费用（本程序默认停车每小时10元）；3.程序基本流程程序由个基本模块组成：输入模块：输入停车场的容量和车辆的相关信息；停车模块：根据车的信息，将该车对应的元素进行入栈操作；离开模块：根据车的信息，将该车对应的元素进行出栈操作，并将后面的元素存入一个临时栈中；输出模块：输出该车停车位置或停车费用；三．详细设计1.物理数据类型①停车场容量为正整数，使用整型数据存储n；②对于剩下的输入使用字符型、整型、整型存储，并将相应数据存入Car类class Car{public:int CarNumber;//车牌号码int ArriveTime;//到达时间int LeaveTime;//离开时间}③定义一个Link类用来存储元素值element及下一个存储表中下一个节点指针的next域，其ADT设计如下：template <class Car>class Link{public:Car element;Link *next;Link(const Car & elemval, Link* nextval = NULL){element = elemval;next = nextval;}Link(Link *nextval = NULL){next = nextval;}};④由于停车场容量一定，即栈空间大小不变，所以可以选用顺序表实现栈class AStck:public Stack<Car>//{private:int size;//栈的长度int top;//栈顶元素Car *listArray;//顺序表保存栈元素public:AStack(int sz){size=sz;top=0;listArray=new Car[sz];} //构造函数~AStack(){delete []listArray;} //析构函数void clear(){top=0;}//栈的清空bool push(const Car&item){if(top==size) return false;else{listArray[top++]=item; return true; }} //栈的插入bool pop(Car& item){if(top==0) return false;else{item=listArray[-top];return true;}} //栈的删除bool topValue(Car & it) const{if(top==0) return false;else{ it=listArray[top-1]; return true;}} //获取栈顶元素int length()const {return top;} //栈的长度};⑤由于该队列中元素添加操作和删除操作比较多，所以使用链式队列实现队列：template <class Car> class Queue :public Link<Car>{private:int size;Link<Car>* front;Link<Car>* rear;public:LQueue(int sz){front=NULL; rear=NULL;size=0}~Lqueue(){delete[]front; delete[]rear;};void clear(){while(front!=NULL){rear=front;front=front->next;delete rear;}rear=NULL;size=0;}//队列的清空bool enqueue(const Car& it){if(rear=NULL)front=rear=new Link<Car>(it NULL);else{rear->next=new Link<Car>(it ,NULL);rear=rear->next;}size++;return true;}//入队bool dequeue( Car& it){if(size==0) return false;it=front->element;Link<Car>* ltemp=front;front=front->nextdelete ltemp;if(front==NULL) rear=NULL;siz--;return true;}//出队int length() const { return size;} //队列的长度}2.算法具体步骤(park为停车场对应的栈，out指临时栈，line指队列)char c;input(c);//输入汽车停车或者离开或者结束；input(num);//输入汽车编号input(time);//输入汽车进入或离开时间Car C[100];//Car的对象数组while(1) //停车{switch(c){case('A')//进入停车场{if(park is FULL) //停车场已满{ enqueue(C[num-1]);output(line.length())}//输出停车位置else {park.push(C[a - 1]);C[a - 1].ArriveTime = b;C[a - 1].carNumber = a;output（park.length()）//输出停车位置}} break;case(’D’)//离开{C[a - 1].LeaveTime = b;C[a - 1].carNumber = a; //进来与离开时间for (int i = 0; i < a - 1; i++)//为要离开的车开道{park.pop(C[i]);// 先删除前面的元素out.push(C[i]);//将前面的元素存至临时栈中park.topValue(C[i]);//}while(out.length()!=0)//将车复原{for (int i = 0; i < a - 1; i++){out.pop(C[i]);park.push(C[i]);}}if(line.length()!=0)//将在通道内的车停进停车场{for (int j = a; j < a + line.length() - 1; j++){line.dequeue(C[j]);park.push(C[j]);}output（C[a - 1].LeaveTime - C[a - 1].ArriveTime）；//输出停留时间output（10*（C[a - 1].LeaveTime - C[a - 1].ArriveTime））；//输出停车费用}break;case ‘E’:return 0;//输入‘E’时结束}3.算法时空分析在该程序中，栈的插入的时间复杂度为Ɵ（1），而对栈中元素进行删除时，需要对该元素后面的所有元素都进行删除，并将他们存入另外一个临时栈中，到该元素顺利删除完毕时又重新存入原栈中，所以栈的删除的时间复杂度为Ɵ（n2）；4.输入输出格式（停车费用每小时10元）输入：5A 1 1A 6 6D 1 4E 0 0输出：车停在停车场第 1个位置车停在场外通道第 2 个位置停车时间：3 缴纳费用：￥30四．调试分析在使用类模板时，第一次没有使用模板参数列表，导致程序运行出错，后来将Car改成class Car后纠正了这个错误五．测试结果程序测试时界面截图如下：六．用户使用说明1.本程序用来处理停车场的问题；2.运行程序后，需要要求进行输入，如若输入错误，系统提示输入错误请重新输入，第一次输入停车场容量，接下来请输入车辆相关信息；3.车辆相关信息中用空格隔开，第一个输入‘A’或‘D’或‘E’，分别表示停车，车离开停车场和结束程序，第二个输入车牌号码，第三个输入到达停车场时间或离开停车场时间。