停车场管理实验报告.doc

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 Carpublic: 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类 数据关系：线性关系 基本操作： void clear();/队列的初始化 bool enqueue(const Car& it);/入队 bool dequeue(Car& it);/出队 int length() constreturn size;/队列的长度 2.算法基本思想 在该程序中，对停车场和场外通中每辆车停车的编号而言，他们有唯一的第一个元素和最后一个元素，而且除第一个元素以外的每个元素都有唯一的后继，除最后一个元素以外的每个元素都有唯一的前驱。因此这些元素具有线性关系。而且，对于停车场里面的汽车，他们逻辑次序是“先进后出，后进先出“的，且只在表头作插入和删除，所以可以使用栈来模拟停车场。而在场外通道中的汽车，他们是”先进先出”的，在一端插入另一端删除操作，所以可以用队列来模拟场外通道。当汽车离开时，在它之后进入的车辆必须先退出再按原次序进入停车场，所以需要定义另外一个临时栈存储这些元素。(本算法按用户输入的顺序进行车辆的停放，不是按车牌号码依次停放) （1）当有汽车需要进停车场停车时，进行入栈操作，若停车场已满，即栈已满，则将车停在场外通道里，进行入队操作，并记下此时的时间ArriveTime； （2）当有汽车需要离开停车场时，对该车对应的元素进行出栈操作，并将后面进来的车辆所对应的元素进行出栈操作，将这些元素（除了需要离开的车对应的元素）存入另外一个栈，即为需要离开停车场的车让道，并记下此时的时间LeaveTime； （3）在需要离开停车场的车成功离开停车场时，将存储在临时栈的那些元素按照原来的顺序依次插入原来的栈； （4） 如果队列不为空（即停车场场外通道上有车，这些车需要进入停车场停车），进行入栈操作,即进行（1）操作；（5）通过LeaveTime 与ArriveTime的差计算停车时间和停车费用（本程序默认停车每小时10元）；3.程序基本流程 程序由个基本模块组成： 输入模块：输入停车场的容量和车辆的相关信息； 停车模块：根据车的信息，将该车对应的元素进行入栈操作； 离开模块：根据车的信息，将该车对应的元素进行出栈操作，并将后面的元素存入一个临时栈中； 输出模块：输出该车停车位置或停车费用；三 详细设计1. 物理数据类型 停车场容量为正整数，使用整型数据存储n； 对于剩下的输入使用字符型、整型、整型存储，并将相应数据存入Car类class Carpublic: int CarNumber;/车牌号码 int ArriveTime;/到达时间 int LeaveTime;/离开时间定义一个Link类用来存储元素值element及下一个存储表中下一个节点指针的next域，其ADT设计如下： template 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/ private: int size;/栈的长度 int top;/栈顶元素Car *listArray;/ 顺序表保存栈元素 public: AStack(int sz)size=sz;top=0;listArray=new Carsz; /构造函数 AStack()delete listArray; /析构函数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) const if(top=0) return false; else it=listArraytop-1; return true; /获取栈顶元素 int length()const return top; /栈的长度 ;由于该队列中元素添加操作和删除操作比较多，所以使用链式队列实现队列：template class Queue :public Link private:int size;Link* front;Link* rear; public: LQueue(int sz)front=NULL; rear=NULL;size=0 Lqueue()deletefront; deleterear; 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(it NULL); else rear-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=NULL;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()/输出停车位置else 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)/将车复原 for (int i = 0; i a - 1; i+) out.pop(Ci); park.push(Ci); if(line.length()!=0)/将在通道内的车停进停车场 for (int j = 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. 算法时空分析在该程序中，栈的插入的时间复杂度为（1），而对栈中元素进行删除时，需要对该元素后面的所有元素都进行删除，并将他们存入另外一个临时栈中，到该元素顺利删除完毕时又重新存入原栈中，所以栈的删除的时间复杂度为（n2）；4.输入输出格式（停车费用每小时10元）输入：5A 1 1 A 6 6 D 1 4 E 0 0 输出：车停在停车场第 1个位置车停在场外通道第 2 个位置停车时间：3 缴纳费用：￥30四 调试分析在使用类模板时，第一次没有使用模板参数列表，导致程序运行出错，后来将Car改成class Car后纠正了这个错误五 测试结果程序测试时界面截图如下：六 用户使用说明1. 本程序用来处理停车场的问题；2. 运行程序后，需要要求进行输入，如若输入错误，系统提示输入错误请重新输入，第一次输入停车场容量，接下来请输入车辆相关信息；3. 车辆相关信息中用空格隔开，第一个输入A或D或E，分别表示停车，车离开停车场和结束程序，第二个输入车牌号码，第三个输入到达停车场时间或离开停车场时间。七 实验心得通过这次实验，我掌握了栈和队列的ADT设计，以及如何用它们来解决问题附录代码：#include using namespace std; int judge(); class Car public: int carNumber; int ArriveTime; int LeaveTime; ; class Stack private: 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=listArray-top; void topValue(Car&it)const if (top = 0) ; else it=listArraytop - 1; int length() return top; ; template class Link public: 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 Link private: 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 Link(it,NULL) ; else rear-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(); 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.length() = n + 1) line.enqueue(Ca -