数据结构实验报告——实验三停车场模拟管理程序的设计与实现本实验的目的是进一步理解线性表的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。

一、【问题描述】设停车场只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进出。

汽车在停车场内按车辆到达的先后顺序依次排列，若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入的车辆必须先退出车场为它让路，待该车辆开出大门，为它让路的车辆再按原次序进入车场。

在这里假设汽车不能从便道上开走，试设计这样一个停车场模拟管理程序。

为了以下描述的方便，停车场的停车场用“停车位”进行叙述，停车场的便道用“便道”进行叙述。

二、【数据结构设计】1、为了便于区分每辆汽车并了解每辆车当前所处的位置，需要记录汽车的牌照号码和汽车的当前状态，所以为汽车定义一个新的类型CAR，具体定义如下：typedef struct{char *license //汽车牌照号码，定义为一个字符指针类型char state; //汽车当前状态，字符s表示停放在停车位上，//字符p表示停放在便道上，每辆车的初始状态用字符i来进行表示}2、①由于车位是一个狭长的通道，所以不允许两辆车同时出入停车位，当有车到来要进入停车位的时候也要顺次停放，当某辆车要离开时，比它后到的车要先暂时离开停车位，而且越后到的车就越先离开停车位，显然这和栈的“后进先出”特点相吻合，所以可以使用一个栈来描述停车位。

由于停车位只能停放有限的几辆车，而且为了便于停车场的管理，为每个车位要分配一个固定的编号，不妨设为1、2、3、4、5（可利用数组的下标），分别表示停车位的1车位、2车位、3车位、4车位。

5车位，针对这种情况使用一个顺序栈比较方便。

②当某辆车要离开停车场的时候，比它后进停车位的车要为它让路，而且当它开走之后让路的车还要按照原来的停放次序再次进入停车位的某个车位上，为了完成这项功能，再定义一个辅助栈，停车位中让路的车依次“压入”辅助栈，待提出开走请求的车开走后再从辅助栈的栈顶依次“弹出”到停车位中。

对辅助栈也采用顺序栈。

该栈的具体定义如下：typedef struct {CAR car[max_stopping];int top;}stack;3、当停车场的停车位上都已经停满了汽车，又有新的汽车到来时要把它调度到便道上，便道上的车辆要按照进入便道的先后顺序顺次存放在便道上，为便道上的每个位置也分配一个固定的编号，当有车从停车位上离开后，便道上的第一辆汽车就立即进入停车位上的某个车位，由于问题描述中限制了便道上的汽车不能从便道上开走，即便道上的汽车只有在停车位上停放过之后才能离开停车场，这样越早进入便道的汽车就越早进入停车位，而且每次进入停车位的汽车都是处于便道“最前面”的汽车，显然，这和队列的先进先出特点相吻合，所以，这里使用一个顺序队来描述便道，可以利用数组的下标表示便道的位置，具体定义如下：#define max_pavement 100 /*便道不限制停放车辆的数目，设为足够大*/typedef struct{CAR pavement [max_pavement]; //各汽车信息的存储空间int front,rear; //用来指示队头和队尾位置的静态指针}PAVEMENT;三、【功能（函数）设计】1、本程序从总体上分为四个大的功能模块：分别为：程序功能介绍和操作提示模块、汽车进入停车场车位的管理模块、汽车离开停车场车位的管理模块、查看停车位以及整个停车场停车状态的查询模块，具体功能描述如下：1）程序功能介绍和操作提示模块：此模块给出程序欢迎信息，介绍本程序的功能，并给出程序功能所对应的键盘操作的提示，具体屏幕显示如下所示：·欢迎使用本程序·；1有车来时；2有车走时；3显示某停车位上的汽车；4显示该停车场的停车状况；5退出系统；请输入选择函数原型void menu()；2）汽车进入停车场车位的管理模块：此模块用来登记停车场的汽车的车牌号和对该车的调度过程并修改该车的状态，其中调度过程要以屏幕信息的形式反馈给用户来指导用户对车辆的调度。

例如，当前停车位上1、2、3车位分别停放着牌照为JF001、JF002、JF003的汽车，便道上无汽车，当牌照为JF004的汽车到来后屏幕应给出如下提示信息：牌照为JF004的汽车停入停车位的4号车位！此函数原型为int push_stack(stack&s,CAR&c)；当停车位已满，再来新的车辆应提示该汽车停在了便道上，提示信息：牌照为JF006的汽车停在了便道上。

此函数原型为int push_queue(queue&q,CAR&c)；再次显示菜单让用户选择功能3）汽车离开停车场停车位的管理模块：此模块用来为提出离开停车场的车辆做调度处理，并修改相关车辆的状态，其中调度过程要以屏幕信息的形式反馈给用户来指导用户对车辆的调度，当有车离开停车场后应该立刻检查便道上是否有车，如果有车的话立即让便道上的第一辆汽车停入停车位。

例如，当前停车位上1，2，3，4，5车位分别停放着牌照为JF001、JF002、JF003、JF004、JF005的汽车，便道上的1，2位置分别停放着牌照为JF006、JF007的汽车，当接收到JF003要离开的信息时，屏幕应给出如下提示信息：车牌号为JF005的车由停车位开到了辅助栈上车牌号为JF004的车由停车位开到了辅助栈上车牌号为JF003的车开走了车牌号为JF004的车由辅助栈开到了停车位的3的车位上车牌号为JF005的车由辅助栈开到了停车位的4的车位上便道上的JF006的停在了5车位上函数原型为int car_leave(stack&s1,stack&s2,queue&q,char*c);再次显示菜单供用户选择功能。

4）①查看停车场停车状态的查询模块：此模块用来在屏幕上显示停车位和便道上各位置的状态，例如，当前停车位上1，2，3，4，5车位分别停放着牌照为JF001、JF002、JF004、JF005、JF006的汽车，便道上的1，2位置分别停放着牌照为JF006、JF007的汽车，当接受到查看指令后，屏幕上应显示：JF001----停车位的1车位JF002----停车位的2车位JF003----停车位的3车位JF004----停车位的4车位JF005----停车位的5车位JF006----便道上的1位置JF007----便道上的2位置显示菜单让用户选择功能。

此函数原型为：void show_parking(stack&s,queue&c);②查看某个停车位的停车状况：在用户选择该功能并且输入4后，应显示：4车位上停着车牌号为JF004的车此函数原型为void show_stopping(int i,stack&s);显示菜单让用户选择功能。

2、以上四个总体功能模块要用到的栈和队列的基本操作所对应的主要函数如下表所示：函数原型函数功能voidinit_stack(stack&c);通过参数c来选择初始化“停车位栈”或“辅助栈”voidinit_queue(queue&c);初始化“便道队列”intpush_stack(stack&s,CAR&c);将车辆c压入停车位栈s中intpush_queue(queue&q,CAR&c);将车辆c压入便道q中voidshow_parking(stack&s,queue&e);打印停车位s和便道q上的车辆信息void show_stopping(inti,stack&s);打印停车位上的i车位的车辆信息intcar_leave(stack&s1,stac k&s2,queue&q,char*c); 先通过c查找出要开走的车辆在停车位的位置，先将其后方的车辆开到辅助栈中，等该车辆开走后，再把辅助栈中的车辆开回停车位，如便道有车，便把1位置的车开到停车位上其他函数的定义和说明请参照源代码。

3、由于程序应该能够随时处理用户所提出的各种操作请求，所以在主函数中用一个DO_WHILE循环结构随时监控键盘的按键操作，遇到相应的按键就转到对应函数继续运行，运行完该函数继续监控键盘按键，如此往复，直到接到“退出”指令程序才能结束。

部分编码如下：do{menu();cout<<"请输入选择"<<endl;cin>>key;while(key>5||key<1){cout<<"输入有误，请重新输入："<<endl;cin>>key;}switch(key){case 1:{CAR c;cout<<"请输入该车车牌号："<<endl;c.license=new char[10];cin>>c.license;c.state='i';if(stopping.top!=max_stopping-1)push_stack(stopping,c);elsepush_queue(pavement,c);break;}case 2:{char *s;cout<<"请输入您要出站的汽车的车牌号："<<endl;s=new char[10];cin>>s;car_leave(stopping,temp,pavement,s);break;}case 3:{int location;cout<<"请输入车位："<<endl;cin>>location;show_stopping(location,stopping);break;}case 4:{show_parking(stopping,pavement);break;}case 5:{exit(0);}};}while(key!=5);return 1;}四、【界面设计】本程序的界面力求简洁、友好，每一步需要用户操作的提示以及每一次用户操作产生的调度结果都以中文的形式显示在屏幕上，使用户对要做什么和已经做了什么一目了然。

文字表述精练，准确。

具体设计可参阅功能设计中的相关部分，这里就不再赘述。

五、【编码实现】#include<iostream.h>#include"string.h"#define max_stopping 5 //车库容量，可以根据实际情况改变#define max_pavement 100#include <stdlib.h>typedef struct{char*license; //汽车牌照号码，定义为一个字符指针类型char state; //汽车当前状态，字符S表示停放在停车位上，//字符p表示停放在便道上，每辆车的初始状态用字符i 来表示}CAR;typedef struct {CAR car[max_stopping]; //各汽车信息的存储空间int top; //用来指示栈顶位置的静态指针}stack;typedef struct{CAR car[max_pavement]; //各汽车信息的存储空间int front,rear; //用来指示队头和队尾位置的静态指针} queue;/*方法声明*/void init_stack(stack&c); //初始化栈void init_queue(queue&c); //初始化便道int push_stack(stack&s,CAR&c);int push_queue(queue&q,CAR&c);void show_parking(stack&s,queue&c);void show_stopping(int i,stack&s);int car_leave(stack&s1,stack&s2,queue&q,char*c); //车辆离开void init_stack(stack&c){for(int i=0;i<max_stopping;i++){c.car[i].license=NULL;c.car[i].state='i';}c.top=-1;}void init_queue(queue&c){for(int i=0;i<max_pavement;i++){c.car[i].license=NULL;c.car[i].state='i';}c.front=c.rear=-1;}int push_stack(stack&s,CAR&c){if(s.top!=max_stopping){s.top++;s.car[s.top].license=new char[strlen(c.license)+1];strcpy(s.car[s.top].license,c.license);cout<<"车牌号为"<<c.license<<"的车进入停车位的"<<s.top+1<<"车位上"<<endl;s.car[s.top].state='s';return 1;}elsereturn 0;}int push_queue(queue&q,CAR&c){if(q.rear!=max_pavement){q.rear++;q.car[q.rear].license=new char[strlen(c.license)+1];strcpy(q.car[q.rear].license,c.license);q.car[q.rear].state='q';cout<<"车牌号为"<<c.license<<"的车进入便道"<<endl;return 1;}return 0;}void show_parking(stack&s,queue&q){int i;if(s.top==-1){cout<<"停车场上没有车"<<endl;return ;}for( i=0;i<=s.top;i++)cout<<s.car[i].license<<"----停车位的"<<i+1<<"车位"<<endl;if(q.front==q.rear){cout<<"便道上没有车"<<endl;return ;}for(i=q.front+1;i<=q.rear;i++)cout<<q.car[i].license<<"----便道上的"<<i+1<<"位置"<<endl; return ;}void show_stopping(int i,stack&s){if(i>max_stopping||i<1){cout<<"此停车场上没有该车位"<<endl;return;}if(s.car[i-1].license==NULL)cout<<"该车位没有汽车"<<endl;elsecout<<i<<"车位上停着车牌号为"<<s.car[i-1].license<<"的车"<<endl; }int car_leave(stack&s1,stack&s2,queue&q,char*c){int location;for(int i=0;i<=s1.top;i++){if(strcmp(s1.car[i].license,c)==0){location=i;break;}}if(i>s1.top){cout<<"停车位上没有该车"<<endl;return 0;}else{while(s1.top>location){s2.top++;s2.car[s2.top].license=newchar[strlen(s1.car[s1.top].license)+1];strcpy(s2.car[s2.top].license,s1.car[s1.top].license);s1.car[s1.top].license=NULL;cout<<"车牌号为"<<s2.car[s2.top].license<<"的车由停车位开到了辅助栈上"<<endl;s1.top--;}cout<<"车牌号为"<<s1.car[location].license<<"的车开走了"<<endl;s1.car[location].license=NULL;s1.top--;while(s2.top>=0){s1.top++;s1.car[s1.top].license=newchar[strlen(s2.car[s2.top].license)+1];strcpy(s1.car[s1.top].license,s2.car[s2.top].license);cout<<"车牌号为"<<s1.car[s1.top].license<<"的车由辅助栈开到了停车位的"<<s1.top+1<<"的车位上"<<endl;s2.car[s2.top].license=NULL;s2.top--;}if(q.front!=q.rear){q.front++;s1.top++;s1.car[s1.top].license=newchar[strlen(q.car[q.front].license)+1];strcpy(s1.car[s1.top].license,q.car[q.front].license);q.car[q.front].license=NULL;cout<<"便道上的"<<s1.car[s1.top].license<<"的停在了"<<max_stopping<<"车位上"<<endl;}return 1;}}void menu(){cout<<" ·欢迎使用本程序· "<<endl;cout<<" 1车辆到达； "<<endl;cout<<" 2车辆离开； "<<endl;cout<<" 3显示某停车位上的汽车； "<<endl;cout<<" 4显示该停车场的停车状况；"<<endl;cout<<" 5退出程序； "<<endl; }int main(){int key;stack stopping,temp;queue pavement;init_stack(stopping);init_stack(temp);init_queue(pavement);do{menu();cout<<"请输入选择"<<endl;cin>>key;while(key>5||key<1){cout<<"输入有误，请重新输入："<<endl;cin>>key;}switch(key){case 1:{CAR c;cout<<"请输入该车车牌号："<<endl;c.license=new char[10];cin>>c.license;c.state='i';if(stopping.top!=max_stopping-1)push_stack(stopping,c);elsepush_queue(pavement,c);break;}case 2:{char *s;cout<<"请输入您要出站的汽车的车牌号："<<endl;s=new char[10];cin>>s;car_leave(stopping,temp,pavement,s);break;}case 3:{int location;cout<<"请输入车位："<<endl;cin>>location;show_stopping(location,stopping);break;}case 4:{show_parking(stopping,pavement);break;}case 5:{exit(0);}};}while(key!=5);return 1;}六、【运行与测试】对于测试用例的设计注重所定义的数据结构的边界以及各种数据结构共存的可能性。