停车场管理实验报告

HUNAN UNIVERSITY

课程实验报告

题目：停车场管理

学生姓名：

学生学号：

专业班级：

指导老师：

完成日期：

一． 需求分析

1. 输入形式

第一次输入一个正整数，代表停车场容量大小。然后输入三个值，分别为字符、正整数、正整数，中间用空格隔开，分别代表车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。其中字符必须为“A,D,E”三者之一。 输入格式为：“A 1 5”、“D 1 15”和“E 0 0“。 当用户输入的字符不是ADE或者输入的不是正整数时，提示用户输入错误并重新输入

2. 输出形式

若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。

（注：本程序中默认停车一小时收费10元）

3. 程序功能

本程序可通过用户输入的车辆信息，输出该车的停车位置或者停车时间及应缴费用

4. 测试数据

请输入停车场容量：5

A 1 1 车停在停车场第 1 个位置

A 2 2 车停在停车场第 2 个位置

A 6 6 车停在停车场第 3 个位置

D 1 4 停车时间：3 缴纳费用：￥30

D 2 6 停车时间：3 缴纳费用：￥30

F 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. 物理数据类型

1 停车场容量为正整数，使用整型数据存储n；

2 对于剩下的输入使用字符型、整型、整型存储，并将相应数据存入Car类

class Car

{

public:

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 *list;// 顺序表保存栈元素

public:

AStack(int sz)

{size=sz;top=0;list=new Car[sz];} //构造函数

~AStack(){delete []list;} //析构函数

void clear(){top=0;}//栈的清空

bool push(const Car&item)

{

if(top==size) return false;

else

{list[top++]=item; return true; }

} //栈的插入

bool pop(Car& item)

{

if(top==0) return false;

else

{

item=list[-top];return true;

}

} //栈的删除

bool topValue(Car & it) const

{

if(top==0) return false;

else

{ it=list[top-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(){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(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->next

delete 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元）

输入：

5

A 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*list;

public:

int maxsize(){ return size; };

Stack(int sz)

{

size = sz;

top = 0;

list = new Car[sz];

}

~Stack()

{

delete []list;

}

void clear()

{

top = 0;

}

void push(const Car&it)

{

if (top == size) ;

else list[top++] = it;

}

void pop(Car&it)

{

if (top == 0);

else it=list[--top];

}

void topValue(Car&it)const

{

if (top == 0)

;

else it=list[top - 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()

{

delete[]front;

delete[]rear;

};

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 C[100]; Stack park = Stack(n); Stack out = Stack(n); Queue line;

Car topCar;

while (1) //停车

{

char c;//停车or离开

int a;//汽车车牌号码

int b;//到达时间or离开时间

cout << "请输入车辆相关信息：";

cin >> c>>a>>b;

switch (c)

{

case 'A':

{

if (park.length()

{

park.push(C[a - 1]);

C[a - 1].ArriveTime = b;

C[a - 1].carNumber = a;

cout << "该车停在第停车场第" << park.length() << "个位置\n";

}

else if (park.length() == n + 1)

{

line.enqueue(C[a - 1]);//停车场已满

cout << "该车停便道外第" << line.length() << "个位置\n";

}

}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]);

}

}

cout << "该车停车时间为" << C[a - 1].LeaveTime - C[a - 1].ArriveTime << endl;

cout << "需要缴纳停车费用为" << 10 * (C[a - 1].LeaveTime - C[a - 1].ArriveTime) << "元\n\n";

}break;

case 'E':

return 0;

default:

{

cout << "输入有误，请重新输入：\n";

}break;

}

}

return 0;

}

int judge()

{

//对输入的合法性进行判断并返回有效的输入

int temp;

cin.sync(); //清空输入流缓冲区

cin >> temp;

while (1)

{

if (cin.fail() || cin.bad() || cin.get() != '\n') //验证输入是否合法，其中cin.fail()和cin.bad()解决输入字符串和溢出的问题

cout << "输入有误，请重新输入。\n请输入停车场容量："; //cin.get()检查输入流中是否还有字符(如果有就表示输入的是形如123r或12.3的错误

else break; //输入合法则跳出循环

cin.clear(); //清空输入流缓冲区标志位，以免影响下次输入

cin.sync();

cin >> temp;

}

return temp;

}

本文来源：https://www.2haoxitong.net/k/doc/3bf6717e68dc5022aaea998fcc22bcd126ff428b.html