数据结构实验报告
实验二 停车厂模拟管理程序的设计与实现
本实验的目的是进一步理解线性表的逻辑结构和存储结构，进一步提高使 用理论知识指导解决实际问题的能力。
一、【问题描述】 设停车厂只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车 进出。汽车在停车场内按车辆到达的先后顺序依次排列，若车场内已停满几辆 汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排 在便道上的第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭 长的通道，在它之后开入的车辆必须先退出车场为它让路， 待该车辆开出大门， 为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走，试 设计这样一个停车厂模拟管理程序。为了以下描述的方便，停车厂的停车场用 “停车位”进行叙述，停车厂的便道用“便道”进行叙述。
二、【数据结构设计】
1、为了便于区分每辆汽车并了解每辆车当前所处的位置， 需要记录汽车的 牌照号码和汽车的当前状态，所以为汽车定义一个新的类型 CAR具体定义如
下：
typedef struct
{
char *license_plate; // 汽车牌照号码，定义为一个字符指针类型 char state; // 汽车当前状态，字符 s 表示停放在停车位上， // 字符 p 表示停放在便道上，每辆车的初始状态用字符 i 来进行表示 }
2、由于车位是一个狭长的通道， 所以不允许两辆车同时出入停车位， 当有 车到来要进入停车位的时候也要顺次停放，当某辆车要离开时，比它后到的车 要先暂时离开停车位，而且越后到的车就越先离开停车位，显然这和栈的“后 进先出”特点相吻合，所以可以使用一个栈来描述停车位。
由于停车位只能停放有限的几辆车，而且为了便于停车厂的管理，为每个 车位要分配一个固定的编号，不妨设为 1、2、3、4、5（可利用数组的下标）， 分别表示停车位的 1 车位、2车位、3 车位、4车位。5车位，针对这种情况使 用一个顺序栈比较方便，具体定义如下：
#define MAX_STOP 5
typedef struct
{
CAR STOP[MAX_STOP]; /各/ 汽车信息的存储空间
int top; // 用来指示栈顶位置的静态指针
}STOPPING;
3、当停车场的停车位上都已经停满了汽车， 又有新的汽车到来时要把它调 度到便道上，便道上的车辆要按照进入便道的先后顺序顺次存放在便道上，为 便道上的每个位置也分配一个固定的编号，当有车从停车位上离开后，便道上 的第一辆汽车就立即进入停车位上的某个车位，由于问题描述中限制了便道上 的汽车不能从便道上开走，即便道上的汽车只有在停车位上停放过之后才能离 开停车厂，这样越早进入便道的汽车就越早进入停车位，而且每次进入停车位 的汽车都是处于便道“最前面”的汽车，显然，这和队列的先进先出特点相吻 合，所以，这里使用一个顺序队来描述便道，可以利用数组的下标表示便道的 位置，具体定义如下：
#define MAX_PAVE 100 /* 便道不限制停放车辆的数目，设为足够大 */ typedef struct
{
CAR PAVE[MAX_PAVE]; /各/ 汽车信息的存储空间
int front,rear; // 用来指示队头和队尾位置的静态指针
}PAVEMENT;
4、当某辆车要离开停车厂的时候， 比它后进停车位的车要为它让路， 而且 当它开走之后让路的车还要按照原来的停放次序再次进入停车位的某个车位 上，为了完成这项功能，再定义一个辅助栈，停车位中让路的车依次“压入” 辅助栈，待提出开走请求的车开走后再从辅助栈的栈顶依次“弹出”到停车位 中。对辅助栈也采用顺序栈，具体定义与停车位栈类似，如下：
typedef struct
{
CAR BUFFER[MAX_STOP]; /各/ 汽车信息的存储空间
int top; // 用来指示栈顶位置的静态指针
}BUFFER;
当然，辅助栈直接利用在2中定义的类型STOPPIN也是可以的。
由于程序的各函数要对这些数据结构中的数据进行操作，而且每次操作的 结果都要动态反应到以上数据结构中，所以在程序设计的时候使用以上新类型 定义的变量都采用全局变量的形式。
三、【功能（函数）设计】
1、本程序从总体上分为四个大的功能模块： 分别为：程序功能介绍和操作 提示模块、汽车进入停车厂车位的管理模块、 汽车离开停车厂车位的管理模块、 查看停车厂停车状态的查询模块，具体功能描述如下：
1）程序功能介绍和操作提示模块： 此模块给出程序欢迎信息， 介绍本程序
的功能，并给出程序功能所对应的键盘操作的提示，具体屏幕显示如下所示:
H-E?
H-E? * S 那犍键?犍作 爭01咤厢q掛
<序要 便到旻#出择 车T退选 友有有显要请
函数原型为void welcome()；
汽车进入停车厂车位的管理模块：此模块用来登记停车厂的汽车的车牌 号和对该车的调度过程并修改该车的状态，其中调度过程要以屏幕信息的形式 反馈给用户来指导用户对车辆的调度。例如，当前停车位上 1、2、3车位分别
停放着牌照为JFOO1、JF002、JF003的汽车，便道上无汽车，当牌照为 JF004 的汽车到来后屏幕应给出如下提示信息：
请输入新到车辆的车牌号
JFQB3
理鎌铁按牧作 管
理鎌铁按牧作 管c q劇 场
使刃要-停十ti 迎车车示退选 欢有有显要请
停车位的情况
L 李位 JF0O1
车位 JF092
痔位 JF093
函数原型为void come();
此函数还要调用其他对于栈和队列的基本操作
汽车离开停车厂停车位的管理模块：此模块用来为提出离开停车厂的车 辆做调度处理，并修改相关车辆的状态，其中调度过程要以屏幕信息的形式反 馈给用户来指导用户对车辆的调度，当有车离开停车厂后应该立刻检查便道上 是否有车，如果有车的话立即让便道上的第一辆汽车停入停车位。例如，当前 停车位上1, 2, 3, 4, 5车位分别停放着牌照为 JF001、JF002、JF003、JF004、 JF005的汽车，便道上的1，2位置分别停放着牌照为JF006 JF007、JF008的 汽车，
停车位的情况
［车位一一JF脑］
车位 JF002
车位 jFaaj
车位 JFB04
车位 JF005
便道的情况
ml JF096
2 位茸 iTFfigi? d 位晝 Jf0OS
当接收到JF003要离开的信息时，屏幕应给出如下提示信息:
助助场场场
助助场场场 1车丰车 了了场亠IZeJIly' 入入车了了了 进进贡入入 场场进 车车了助北道 由由离由由由 5 4 3 4 5 &
一
^0
F F p F F F
函数原型为void leave();
此函数还要调用其他对于栈和队列的基本操作
查看停车厂停车状态的查询模块：此模块用来在屏幕上显示停车位和便 道上各位置的状态，例如，当前停车位上1, 2, 3, 4, 5车位分别停放着牌照 为JF001、JF002、JF003 JF004 JF005的汽车，便道上的1, 2位置分别停放 着牌照为JF006 JF007的汽车，当接受到查看指令后，屏幕上应显示：
卷售的情抚
车位 JF0S1
二车检 JF0S2
车位 JF0O4
车位 JF065
车位
JF00?更道的惰呪
JF00?
位
函数原型为void display();
此函数还要调用其他对于栈和队列的基本操作
2、以上四个总体功能模块要用到的栈和队列的基本操作所对应的主要函数
如下表所示:
函数原型
函数功能
STOPPING *ini t stopp in g()
初始化“停车位栈”
BUFFER *in it buff()
初始化“辅助栈”
PAVEMENT *ini t paveme nt()
初始化“便道队列”
Int car_come(i nt pos)
将pos指定的汽车信息插入“停车位栈”，并修改 该车状态。
Int car_leave(i nt pos)
将pos指定的汽车信息从“停车位栈”删除，并 修改该车状态。
Int stop_to_buff(int pos)
将pos指定的汽车信息从“停车位栈”移动到“辅 助栈”。
Int buff_to_stop(int pos)
将pos指定的汽车信息从“辅助栈”移动到“停 车位栈”。
Int pave_to_stop(int pos)
将pos指定的汽车信息从“便道队列”移动到“停 车位栈”
Int car disp(i nt pos)
将pos指定的汽车信息显示在屏幕上。
其他函数的定义和说明请参照源代码
3、由于程序应该能够随时处理用户所提出的各种操作请求， 所以在主函数中用 一个DO_WHIL循环结构随时监控键盘的按键操作，遇到相应的按键就转到对应 函数继续运行，运行完该函数继续监控键盘按键，如此往复，直到接到“退出” 指令程序才能结束。部分编码如下：
do
{
welcome。；
cin> >key;
if(key=='C'||key=='c')
{
come();
}
else if(key=='L'||key==T)
{
leave();
check();
}
else if(key=='S'||key=='s')
display(); else welcome();
}
while((key!='Q')&&(key!='q'));
四、【界面设计】 本程序的界面力求简洁、友好，每一步需要用户操作的提示以及每一次用 户操作产生的调度结果都以中文的形式显示在屏幕上，使用户对要做什么和已 经做了什么一目了然。文字表述精练，准确。具体设计可参阅功能设计中的相 关部分，这里就不再赘述。
五、【编码实现】
略。详见具体源代码。
六、【运行与测试】 对于测试用例的设计注重所定义的数据结构的边界以及各种数据结构共存 的可能性。例如：
1、连续有 7 辆车到来，牌照号分别为 JF001、JF002、JF003、JF004、、JF005、 JF006、JF007,前5辆车应该进入停车位1—5车位，第6、7辆车应停入便道 的 1 、 2 位置上。
2、 1 中的情况发生后，让牌照号为 JF003 的汽车从停车厂开走，应显示 JF005、JF004的让路动作和JF006从便道到停车位上的动作。
3、 随时检查停车位和便道的状态， 不应该出现停车位有空位而便道上还有 车的情况。
4、 其他正常操作的一般情况。
5、 程序容错性的测试， 当按键输入错误的时候是否有错误提示给用户指导 用户正确操作，并作出相应处理保证程序健康的运行。
经过反复的运行和测试，程序的容错性能良好，界面简洁友好，运行稳定 可靠，符合实际操作规范，基本达到了模拟停车厂管理的要求。
七、【实验完成后的思考】
1、 通过本程序熟练掌握了栈和队列的定义和使用方法， 对使用C语言编码 来验证数据结构的理论知识有了更深层次的理解，达到了实验目的。
2、 通过在设计过程中的讨论和思考， 对使用现有知识利用计算机来解决现 实生活中的实际问题确立了信心，对软件工程思想和模块化程序思想有了比较 清晰的理解，为今后的程序设计奠定了一定的心理和技术上的准备。
3、 由于时间仓促和个人能力有限， 程序中还有一些需要完善的地方， 例如： 对停放到停车厂的汽车按时间的收费管理，程序界面可以使用图形方式使之更 美观，使用鼠标或菜单方式使之能够适应更多人的使用习惯。在今后的实验中 要多多练习这方面的能力。
实验人：'、'
实验完成日期： 2011年 10月 20 日 实验报告提交日期： 2011年10月 26日
附 程序代码：
// test.cpp :
定义控制台应用程序的入口点。
//
#include
"stdafx.h"
#include
<string>
#include
<iostream>
#define
MAX_STOP 5
#define
MAX_PAVE 100
using namespacestd;
typedef struct
{
string license_plate; char state;
// 汽车牌照号码，定义为一个字符指针类型
//汽车当前状态，字符s表示停放在停车位上,
//字符p表示停放在便道上，每辆车的初始状态用字符 i来进行表示
}CAR;
typedef struct
{
CAR STOP[MAX_STOP]/;/ 各汽车信息的存储空间
int top; // 用来指示栈顶位置的静态指针
}STOPPING;
typedef struct
{
CAR PAVE[MAX_PAVE]/;/ 各汽车信息的存储空间
int front,rear; // 用来指示队头和队尾位置的静态指针
}PAVEMENT;
typedef struct
{
CAR BUFFER[MAX_STOP];// 各汽车信息的存储空间
int top; // 用来指示栈顶位置的静态指针
// 初始化“停车位栈”
// 初始化“停车位栈”
STOPPING *s;
BUFFER *b;
PAVEMENT *p;
void welcome( )
{
cout
<<"
欢迎使用停车场管理系统 " <<endl
<<"
有车到来时请按 c 键" <<endl
<<"
有车要走时请按 l 键" <<endl
<<"
显示停车场状态请按 s 键 " <<endl
<<"
要退出程序请按 q 键" <<endl
<<"
请选择您要做的操作 " <<endl;
}
STOPPING *init_stopping( ) {
s=newSTOPPING;
if (!s)
return NULL;
else {
s->top=-1;
return s;
}
} int push_stopping(CAR car) {
if (s->top==MAX_STOP-1) return 0;
else {
s->top++;
s->STOP[s->top]=car; return 1;
}
}
int pop_stopping(CAR *car)
{
if (s->top==-1)
return 0;
else {
*car=s->STOP[s->top];
s->top--;
return 1;
}
}
BUFFER *init_buff( ) // 初始化“辅助栈” {
b=newBUFFER;
b->top=-1;
return b;
}
int push_buff(CAR car)
{
if (b->top==MAX_STOP-1) return 0;
else {
b->top++; b->BUFFER[b->top]=car; return 1;
}
}
int pop_buff(CAR *car)
{
if (b->top==-1)
return 0;
else {
*car=b->BUFFER[b->top];
b->top--;
return 1;
}
PAVEMENT *init_pavement( ) // 初始化“便道队列 { p=newPAVEMENT;
p->front=p->rear=MAX_PAVE-1; return p;
}
int In_pavement(CAR car)
{
if ((p->rear+1)%MAX_PAVE==p->front) return 0;
else { p->rear=(p->rear+1)%MAX_PAVE; p->PAVE[p->rear]=car; return 1;
}
}
int Out_pavement(CAR *car)
{
if (p->rear%MAX_PAVE==p->front) return 0;
else { p->front=(p->front+1)%MAX_PAVE; *car=p->PAVE[p->front];
return 1;
}
}
int car_come(CAR car) II将pos指定的汽车信息插入"停车位栈"，并修改该车状态 {
car.state= 's' ;
return push_stopping(car);
}
int car_leave() // 将 pos 指定的汽车信息从“停车位栈”删除，并修改该车状态 {
CAR *car= new CAR();
int a=pop_stopping(car); cout<<car->license_plate<< "离开了了停车场 " <<endl;
car->state= 'i' ;
return a;
}
int stop_to_buff() //将pos指定的汽车信息从"停车位栈”移动到“辅助栈”
{
CAR *car= new CAR();
if (pop_stopping(car))
{
if (push_buff(*car))
{
cout<<car->license_plate<< " 由停车场进入了辅助 " <<endl; return 1;
} else
return 0;
}else
return 0;
}
int buff_to_stop() //将pos指定的汽车信息从"辅助栈”移动到“停车位栈”
{
CAR *car= new CAR();
if (pop_buff(car))
{
if (push_stopping(*car))
{
cout<<car->license_plate<< " 由辅助进入了停车场 " <<endl; return 1;
} else
return 0;
} else
return 0; int pave_to_stop() //将pos指定的汽车信息从“便道队列”移动到“停车位栈” {
CAR *car=new CAR();
if (Out_pavement(car))
{
if (push_stopping(*car))
{
cout<<car->license_plate<< " 由便道进入了停车场 " <<endl; return 1;
}
else
return 0;
}
else
return 0;
}
int come()
{
CAR car;
car.state= 'i' ;
coutvv"请输入新到车辆的车牌号"vvendl;
cin>>car.license_plate;
if (s->top==MAX_STOP-1)
return In_pavement(car);
else
return car_come(car);
}
void leave()
{
string license;
int i=0;
CAR car;
coutvv "请输入将离开车的车牌号 "vvendl;
cin>>license;
for (i=0;i<=s->top;i++)
if (s->STOP[i].license_plate==license) break ;
if (i>s->top)
{
cout<< " 没有该车辆 "<<endl;
}else if (i==s->top){
car_leave();
}
else {
int m=s->top;
for (int j=i+1;j<=m;j++) stop_to_buff();
car_leave();
m=b->top;
for (int k=0;k<=m;k++) buff_to_stop();
}
}
void check()
{
while ((s->top<MAX_STOP-1)&&(p->rear%MAX_PAVE!=p->front))
pave_to_stop();
void display()
{
cout<< " 停车位的情况 " <<endl;
int max=s->top;
int i=0;
for (i=0;i<=max;i++)
cout<<i+1<< "车位" <<" —— " <<s->STOP[i].license_plate<<endl; cout<< " 便道的情况 " <<endl;
for (i = (p->front+1)%MAX_PAVE; (p->rear +1)%MAX_PAVE!= i%MAX_PAVE; i=(i+1)%MAX_PAVE) cout<<i+1<< "位置" <<" —— " <<p->PAVE[i].license_plate<<endl;
}
}
int main()
{ init_buff(); init_pavement(); init_stopping(); char key; do { welcome(); cin>>key; if (key== 'C' ||key== 'c' ) {
come();
}
else if (key== 'L' ||key== 'l' ) {
leave();
check();
}
else if (key== 'S' ||key== 's' ) display();
else welcome();
}
while ((key!= 'Q' )&&(key!= 'q' ));