班级：计算机11-2 学号：40 姓名：朱报龙成绩：_________
实验六栈和队列的应用
一、实验目的
1 掌握栈的数据类型描述及栈的特点；
2 掌握栈的顺序存储结构的特点及算法描述；
3 掌握队列的数据类型描述及链式存储结构的特点和算法描述。
二、实验内容
停车场管理。设有一个可以停放n辆汽车的狭长停车场（先进后出），它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后依次从停车场最里面向大门口处停放（最先到达的第一辆车停放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车离开，则排在便道上的第一辆车就可以进入停车场。停车场内如有某辆车要离开，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再按原来的次序进停车场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车没进停车场就要离开，允许其离开，不收停车费，并且仍然保持在便道上的车辆次序。试编程模拟停车场管理。
二、设计与编码
#include
using namespace std;
const int Max=2;//车库最大容量
const double price=30;//每小时的费用
class car//车的信息类
{
public:
double time;//计费时间
int number;//车牌号
car *next;//存放car类型元素的数组初始地址
};
class carstack//栈（停车场）的类
{
friend class parkingmanagement;//parkingmanagement能访问carstack类中所有成员
public:
carstack();//构造函数，栈的初始化
int empty();//判断栈是否为空
int full();//判断栈是否为满
car *s;//存放car类型栈元素的数组初始地址
int top;//栈顶指针
};
class carqueue//队列（便道）的类
{
friend class parkingmanagement;//parkingmanagement能访问carstack类中所有成员
public:
carqueue();//构造函数，队列的初始化
int full();//判断队列是否为满
car *front,*rear;//存放car类型队列元素的数组初始地址
};
class parkingmanagement
{
public:
int pushstack(carstack &cs,int cnum,double ctime);//入栈,cs栈内进行调整，返回栈内位置void popstack(carstack &cs,int cnum);//出栈，cs栈内进行调整，
int pushqueue(carqueue &cq,int cnum,double ctime);//入队,队内进行调整，返回队内位置int popqueue(carqueue &cq);//出队,队内进行调整，返回汽车车牌号
void arrival(carstack &cs,carqueue &cq,int cnum,double ctime);//车辆到达，
//根据输入的车牌号、到达时间，变更函数参数；并cout车位信息
void leave(carstack &cs,carqueue &cq,int cnum,double ctime);//车辆离开，
void deletequeue(carqueue &cq,int i);//删除cq过道中第i辆车
int popstacknumber;//专门存放出栈的时候返回的车牌号
double popstacktime;//专门存放出栈的时候返回的时刻
};
carstack::carstack()//构造函数，栈的初始化
{
top=-1;
s=new car[Max];//创建car类型栈元素的数组
if(s==NULL)
{
cout<<"栈空间分配不成功！"< exit(1); } } int carstack::full()//判断栈是否为满 { return top==Max-1; } carqueue::carqueue()//构造函数，队列的初始化 { rear=front=NULL; } int parkingmanagement::pushstack(carstack &cs,int cnum,double ctime)//入栈,cs栈内进行调整，返回栈内位置 { if(cs.top==Max-1)//Max从开始，top从开始 { cout<<"停车场已满！"< return Max; } else { cs.top++; (cs.s[cs.top]).number=cnum;//将cnum赋给栈顶位置的车的车牌号，s是car类型栈元素的数组 (cs.s[cs.top]).time=ctime;//将ctime赋给栈顶位置的车的入栈时间，s是car类型栈元素的数组 return (cs.top+1);//返回栈内位置加，即停车场内车位从号开始 } } void parkingmanagement::popstack(carstack &cs,int cnum)//出栈，cs栈内进行调整， //根据车牌号把车弹出栈,将出栈car的number赋值给int popstacknumber //将出栈car的time赋值给double popstacktime，无返回值！ { int i; car p; carstack stemp;//定义一个carstack类型的临时存放出栈元素的栈 for(i=0; i<=cs.top; i++) if((cs.s[i]).number==cnum) break;//当要出栈的车的车牌号=栈内的车牌号元素时，跳出循环 p=cs.s[i];//将要出栈的元素赋给car类型的p存放 while(cs.top>i) stemp.s[++(stemp.top)]=cs.s[(cs.top)--];//出栈的元素数组逐个赋给临时栈 popstacknumber=p.number;//将这个车牌号信息传给int popstacknumber() popstacktime=p.time;//将该车的时间信息传给double popstacktime() cs.top--;//栈顶指针回到原来位置 while(stemp.top>=0) cs.s[++(cs.top)]=stemp.s[(stemp.top)--];//临时栈出栈的元素逐个赋给原栈，完成先退再进的工作 } int parkingmanagement::pushqueue(carqueue &cq,int cnum,double ctime)//入队,队内进行调整，返回队内位置 { car *p,*countp; int count(1);//count用于记录车在过道上的位置信息，因队列为链式的，所以进行循环累加 p=new car;//创建一个car类型的指针 p->number=cnum; p->time=ctime; p->next=NULL;//首先将指向存放car类型元素的数组初始地址置空 if (cq.front==NULL)//第一次入队要判断头结点是否为空 { cq.front=cq.rear=p; } else {//尾插法插入元素 p->next=(cq.rear)->next; (cq.rear)->next=p; cq.rear=(cq.rear)->next; } countp=(cq.front)->next; while(countp!=NULL) { count++; countp=countp->next; }//count即车在过道上的位置，【从开始计！！！】 return count; } int parkingmanagement::popqueue(carqueue &cq)//出队,队内进行调整，返回汽车车牌号 { car p; p.number=((cq.front)->next)->number;//cq队里，从cq.front开始指向下一个元素的车牌号赋给car类型的车信息 p.time=((cq.front)->next)->time;//cq队里，从cq.front开始指向下一个元素的时刻 //赋给car类型的车信息 p.next=((cq.front)->next)->next;//cq队里，从cq.front开始指向下一个元素的指针 //赋给car类型的车信息的下一个元素的指针 return p.number; cq.front=(cq.front)->next; } void parkingmanagement::arrival(carstack &cs,carqueue &cq,int cnum,double ctime) //车辆到达，根据输入的车牌号、到达时间，变更函数参数；并cout车位信息 { int pos; if(!(cs.full()))//如果栈未满，车辆停入停车场 { int fl(0),i;//定义一个从开始的标记fl for(i=0;i<=cs.top;i++) { if(cs.s[i].number==cnum)//如果到达的车的车牌号=栈内已有车辆的车牌号 { fl=1;//fl记 break; } } if(fl==1)//如果到达的车的车牌号!=栈内已有车辆的车牌号 cout<<"输入错误！请重新输入！"< else { pos=pushstack(cs,cnum,ctime);//入栈，返回车位信息 cout<<"该停车场还有空位，请到"< cout< } } else//如果栈满，车辆暂停便道 { pos=pushqueue(cq,cnum,ctime);//入队，返回车位信息 cout<<"该停车场已满，请将车停到便道"< cout< } } void parkingmanagement::leave(carstack &cs,carqueue &cq,int cnum,double ctime) {//车辆离开，根据输入的车牌号找到汽车，并进行出栈操作、出队操作和入栈操作；并cout停留时间和收费情况 int i,flag(0),pstack,count(1),outcarnum; double hour; car *p; for(i=0;i<=cs.top;i++) if((cs.s[i]).number==cnum) { flag=1; break; } if(flag)//如果输入的车牌号与栈内已有车辆的车牌号一致 { popstack(cs,cnum);//出栈操作 hour=ctime-popstacktime;//时间计算 outcarnum=popqueue(cq);//将便道上的第一辆车出队，入栈。并将其车牌号赋给outcarnum pstack=pushstack(cs,outcarnum,ctime);//将便道上的第一辆车，入栈 cout<<"该车在本停车场内停留时间为"< } else//如果输入的车牌号与队列里已有车辆的车牌号一致 { p=cq.front; while(p!=NULL) { count++;//如果在过道中找到该车，则该车的位置为过道中的第count位置（count从开始） p=p->next; if(p->number==cnum)//在过道中找到要出去的车，则在队列中删除该car。 //后面的车辆依然顺序排列，补足空位 { deletequeue(cq,count); if(count>Max) { cout<<"您的车在便道上的位置为"< break; } } } if(p==NULL) cout<<"您的车不在本停车场内，或输入有误，请重新输入！"< } } void parkingmanagement::deletequeue(carqueue &cq,int i) { car *p,*q; int j(0); p=cq.front; while(p && j { p=p->next; j++; }//找到第i个节点(i从开始) if(!p || !p->next) cout<<"i不合法"; else { q=p->next; p->next=q->next; delete q; } } //*******************************【以下是主程序】************************************ void print() { cout<<"= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ="< cout<<"= ="< cout<<"= 本停车场收费标准为：元/小时；车库容量为：="< cout<<"= ="< cout<<"= 请输入您的泊车信息：格式为：（到达/离去/退出）；车牌号；现在时刻="< cout<<"= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ="< void main() { char acc; int carnum; double cartime; parkingmanagement park; carstack cars; carqueue carq; while(1) { print(); cin>>acc>>carnum>>cartime; if(acc=='A') park.arrival(cars,carq,carnum,cartime); else if(acc=='D') park.leave(cars,carq,carnum,cartime); else if(acc=='E') break; else cout<<"您的输入有误，请重新输入！"< } } 三、运行与调试 a)在调试程序的过程中遇到什么问题，是如何解决的？ 答：经常忘记对头结点的定义，以至于程序出错，经定义头结点，使程序正常运行 b)程序运行的结果如何？ 四、实验小结 栈和队列是两种常用的数据结构，栈是后进先出，队列是先进先出，栈和队列广泛运用于操作系统和各种编程软件，必须掌握栈和队列的运用。
相关主题
文本预览