实验2停车场管理
1． 需求分析
（1） 输入的形式和输入值的范围：
第一次输入一个正整数，代表停车场容量大小。
以后每一次输入三个值，分别为字符、整形、整形，中间用逗号隔开。分别代表车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。其中字符必须为“A,D,E”三者之一。
输入格式为：“（‘A’，1，5）”、“（‘D’，1，15）”。.
不对非法输入做处理，即假设输入都是合法的。
（2） 输出的形式：
若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。
（3） 程序所能达到的功能：
对于用户输入的车辆信息，可以输出该车的停车位置或者停车时间及应缴费用。
（4） 测试数据：
请输入停车场容量2
A,1,1
车停在停车场第 1 个位置
A,2,2
车停在停车场第 2 个位置
A,3,3
车停在便道第 1 个位置
D,1,4
停车时间：3 缴纳费用：￥6
D,2,5
停车时间：3 缴纳费用：￥6
A,5,5
车停在停车场第 2 个位置
E,0,0
2． 概要设计
（1）抽象数据类型的定义：
由于每一辆车包含多种信息。所以定义一个Data类来存储汽车的“来去、车牌号，时间”信息。
class Data //每辆车的信息类
{
public:
int license;//车牌号码
int arrive;//到达时间
};
用栈模拟停车场，其ADT如下：
ADT stack
数据对象：Data类型
数据关系：线性关系
基本操作：
bool push(const Data&item)//入栈
bool pop(Data& item)//出栈
bool topValue(Data & it)//顶层元素值
int length()const {return top;}//栈实际长度
用队列模拟便道，其ADT如下：
ADT quene
数据对象：Data类型
数据关系：线性关系
基本操作：
bool enquene(const Data &it)//入队
bool dequene(Data &it)//出队
virtual int length()const{return ((rear+size)-front+1)%size;}//队列的实际长度
（2）算法的基本思想：
1、
对于指定大小的停车场，其只有一端出口，先进后出，用栈存储；
超过停车场容量的车停在便道上，先进先出，用队列存储；
当汽车离开时，在它之后进入的车辆必须先退出再按原次序进入车场，需要一个临时栈存储。
2、
每进入一辆车，进行入栈操作，即停车场；如果入栈不成功则入队列，即便道。
每离开一辆车：
1）要对在该车之后进入的车辆进行弾栈操作，出栈的元素依次存入另一个临时堆栈，即为离开车辆开道。
2）在对该车进行出栈操作后，再将临时堆栈的元素弹回原栈。
3）通过离开时间与该车储存在Data中的到达时间差获得停车时间以及费用（费用的计算根据2元/小时）。
4）此时如果队列不为空，表明便道上有车待入，修改此待入车辆的到达时间为离开车的离开时间，并进行入栈操作。
当输入不为‘E’时，循环进行上述操作。
3． 详细设计
（1） 实现概要设计中定义的所有数据类型：
1、分别用字符型、整形、整形存储用户的输入，并将相应数据存入Data类。
class Data //每辆车的信息类
{
public:
int license;//车牌号码
int arrive;//到达时间
};
2、用顺序栈表实现栈：
class Stack//堆栈，模拟停车场以及有车辆离开时的临时停车处
{ private:
int size;
int top;
Data *listArray;
public:
Stack(int sz){size=sz;top=0;listArray=new Data[sz];}
~Stack(){delete []listArray;}
bool push(const Data&item)//入栈
{
if(top==size)return false;
else
{
listArray[top++]=item;
return true;
}
}
bool pop(Data& item)//出栈
{
if(top==0)return false;
else
{
item=listArray[--top];
return true;
}
}
bool topValue(Data & it)//顶层元素值
{
if(top==0)return false;
it=listArray[top-1];
return true;
}
int length()const {return top;}//栈实际长度
};
3、用循环队列实现队列：
class Quene//队列，模拟便道
{
private:
int size;
int front;
int rear;
Data *listArray;
public:
Quene(int sz){size=sz+1;rear=0;front=1;listArray=new Data[size];}
~Quene(){delete []listArray;}
bool enquene(const Data &it)//入队
{
if((rear+2)%size==front)return false;
rear=(rear+1)%size;
listArray[rear]=it;
return true;
}
bool dequene(Data &it)//出队
{
if(length()==0)return false;
it=listArray[front];
front=(front+1)%size;
return true;
}
virtual int length()const{return ((rear+size)-front+1)%size;}//队列的实际长度
};
（2） 实现程序的具体步骤：
while(c!='E')//不退出程序
{
Data top;
if(c=='A')//进入停车场
{ if(park.push(d))//入栈成功
{
//输出提示语句 }
Else//入栈失败
{
line.enquene(d);
//输出提示语句 }
}
else if(c=='D')//离开停车场
{
park.topValue(top);
while(top.license!=d.license)//为车开道
{
park.pop(top);
temp.push(top);
park.topValue(top);
}
park.pop(top);
//输出提示语句
while(temp.length()!=0)//回到车位
{
temp.pop(top);
park.push(top);
}
if(line.length()!=0)//由便道到车库
{
line.dequene(top);
top.arrive=d.arrive;//进入的时间刚好是那辆车出去的时间
park.push(top);
}
}
（3） 算法的时空分析和改进设想：
对于入栈处理，时间复杂度为Θ(1)，对于出栈处理，最坏情况下的时间复杂度是Θ(n)的。输入N次，出栈处理最多只有N/2次，所以时间复杂度最坏情况是Θ(n2)的，最好情况是Θ(n)的。
（4）
画出函数的调用关系图：
主程序
（5） 输入和输出的格式：
输入：
A,1,1
A,2,2
A,3,3
D,1,4
输出：
车停在停车场第 1 个位置
车停在停车场第 2 个位置
车停在便道第 1 个位置
停车时间：3 缴纳费用：￥6
4、测试结果
根据实际演算与输出结果比对，证明结果正确无误，即测试结果正确。
5、用户使用说明
运行程序时
1）显示提示“请输入停车场容量”，此时输入的整形代表停车场最多可以容纳的车辆数量。
2）在接下来的使用中，每次处理车辆信息，都输入“字母，整数，整数”，中间用逗号隔开。具体解释如下：
字母：其中字母‘A’代表车辆进入信息，字母‘D’代表车辆离开信息，字母‘E’代表停止使用软件信息。
整数：代表车辆的车牌号。
整数：代表时间。当字母为‘A’时表示车辆进入停车场的时间，当字母为‘D’时表示车辆离开停车场的时间。
3）当字母输入为‘E’时，无论接下来输入什么数字，程序都将结束。尽管程序结束与这两个整数无关，但是这两个整形必须输入，否则程序无法正常结束。
6、实验心得
这次实验思路很清晰，整体用了1个小时，完成速度较好，以后应该在完成实验的基础上继续提高效率。
第二篇：数据结构实验报告二-停车场管理
实验2停车场管理
1． 需求分析
（1） 输入的形式和输入值的范围：
第一次输入一个正整数，代表停车场容量大小。
以后每一次输入三个值，分别为字符、整形、整形，中间用逗号隔开。分别代表车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。其中字符必须为“A,D,E”三者之一。
输入格式为：“（‘A’，1，5）”、“（‘D’，1，15）”。
不对非法输入做处理，即假设输入都是合法的。
（2） 输出的形式：
若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。
（3） 程序所能达到的功能：
对于用户输入的车辆信息，可以输出该车的停车位置或者停车时间及应缴费用。
（4） 测试数据：
请输入停车场容量2
A,1,1
车停在停车场第 1 个位置
A,2,2
车停在停车场第 2 个位置
A,3,3
车停在便道第 1 个位置
D,1,4
停车时间：3 缴纳费用：￥6
D,2,5
停车时间：3 缴纳费用：￥6
A,5,5
车停在停车场第 2 个位置
E,0,0
2． 概要设计
（1）抽象数据类型的定义：
由于每一辆车包含多种信息。所以定义一个Data类来存储汽车的“来去、车牌号，时间”信息。
class Data //每辆车的信息类
{
public:
int license;//车牌号码
int arrive;//到达时间
};
用栈模拟停车场，其ADT如下：
ADT stack
数据对象：Data类型
数据关系：线性关系
基本操作：
bool push(const Data&item)//入栈
bool pop(Data& item)//出栈
bool topValue(Data & it)//顶层元素值
int length()const {return top;}//栈实际长度
用队列模拟便道，其ADT如下：
ADT quene
数据对象：Data类型
数据关系：线性关系
基本操作：
bool enquene(const Data &it)//入队
bool dequene(Data &it)//出队
virtual int length()const{return ((rear+size)-front+1)%size;}//队列的实际长度
（2）算法的基本思想：
1、
对于指定大小的停车场，其只有一端出口，先进后出，用栈存储；
超过停车场容量的车停在便道上，先进先出，用队列存储；
当汽车离开时，在它之后进入的车辆必须先退出再按原次序进入车场，需要一个临时栈存储。
2、
每进入一辆车，进行入栈操作，即停车场；如果入栈不成功则入队列，即便道。
每离开一辆车：
1）要对在该车之后进入的车辆进行弾栈操作，出栈的元素依次存入另一个临时堆栈，即为离开车辆开道。
2）在对该车进行出栈操作后，再将临时堆栈的元素弹回原栈。
3）通过离开时间与该车储存在Data中的到达时间差获得停车时间以及费用（费用的计算根据2元/小时）。
4）此时如果队列不为空，表明便道上有车待入，修改此待入车辆的到达时间为离开车的离开时间，并进行入栈操作。
当输入不为‘E’时，循环进行上述操作。
3． 详细设计
（1） 实现概要设计中定义的所有数据类型：
1、分别用字符型、整形、整形存储用户的输入，并将相应数据存入Data类。
class Data //每辆车的信息类
{
public:
int license;//车牌号码
int arrive;//到达时间
};
2、用顺序栈表实现栈：
class Stack//堆栈，模拟停车场以及有车辆离开时的临时停车处
{ private:
int size;
int top;
Data *listArray;
public:
Stack(int sz){size=sz;top=0;listArray=new Data[sz];}
~Stack(){delete []listArray;}
bool push(const Data&item)//入栈
{
if(top==size)return false;
else
{
listArray[top++]=item;
return true;
}
}
bool pop(Data& item)//出栈
{
if(top==0)return false;
else
{
item=listArray[--top];
return true;
}
}
bool topValue(Data & it)//顶层元素值
{
if(top==0)return false;
it=listArray[top-1];
return true;
}
int length()const {return top;}//栈实际长度
};
3、用循环队列实现队列：
class Quene//队列，模拟便道
{
private:
int size;
int front;
int rear;
Data *listArray;
public:
Quene(int sz){size=sz+1;rear=0;front=1;listArray=new Data[size];}
~Quene(){delete []listArray;}
bool enquene(const Data &it)//入队
{
if((rear+2)%size==front)return false;
rear=(rear+1)%size;
listArray[rear]=it;
return true;
}
bool dequene(Data &it)//出队
{
if(length()==0)return false;
it=listArray[front];
front=(front+1)%size;
return true;
}
virtual int length()const{return ((rear+size)-front+1)%size;}//队列的实际长度
};
（2） 实现程序的具体步骤：
while(c!='E')//不退出程序
{
Data top;
if(c=='A')//进入停车场
{ if(park.push(d))//入栈成功
{
//输出提示语句 }
Else//入栈失败
{
line.enquene(d);
//输出提示语句 }
}
else if(c=='D')//离开停车场
{
park.topValue(top);
while(top.license!=d.license)//为车开道
{
park.pop(top);
temp.push(top);
park.topValue(top);
}
park.pop(top);
//输出提示语句
while(temp.length()!=0)//回到车位
{
temp.pop(top);
park.push(top);
}
if(line.length()!=0)//由便道到车库
{
line.dequene(top);
top.arrive=d.arrive;//进入的时间刚好是那辆车出去的时间
park.push(top);
}
}
（3） 算法的时空分析和改进设想：
对于入栈处理，时间复杂度为Θ(1)，对于出栈处理，最坏情况下的时间复杂度是Θ(n)的。输入N次，出栈处理最多只有N/2次，所以时间复杂度最坏情况是Θ(n2)的，最好情况是Θ(n)的。
（4）
画出函数的调用关系图：
主程序
（5） 输入和输出的格式：
输入：
A,1,1
A,2,2
A,3,3
D,1,4
输出：
车停在停车场第 1 个位置
车停在停车场第 2 个位置
车停在便道第 1 个位置
停车时间：3 缴纳费用：￥6
4、测试结果
根据实际演算与输出结果比对，证明结果正确无误，即测试结果正确。
5、用户使用说明
运行程序时
1）显示提示“请输入停车场容量”，此时输入的整形代表停车场最多可以容纳的车辆数量。
2）在接下来的使用中，每次处理车辆信息，都输入“字母，整数，整数”，中间用逗号隔开。具体解释如下：
字母：其中字母‘A’代表车辆进入信息，字母‘D’代表车辆离开信息，字母‘E’代表停止使用软件信息。
整数：代表车辆的车牌号。
整数：代表时间。当字母为‘A’时表示车辆进入停车场的时间，当字母为‘D’时表示车辆离开停车场的时间。
3）当字母输入为‘E’时，无论接下来输入什么数字，程序都将结束。尽管程序结束与这两个整数无关，但是这两个整形必须输入，否则程序无法正常结束。
6、实验心得
这次实验思路很清晰，整体用了1个小时，完成速度较好，以后应该在完成实验的基础上继续提高效率。