栈和队列及其应用——停车场管理.doc

华北水利水电学院 数据结构 实验报告20122013学年 第 二 学期 2012 计算机科学与技术 专业班级： 2012196 学号： 40 姓名： 贾宁 实验二 栈和队列及其应用一、 实验题目：栈和队列及其应用停车场管理二、 实验内容：设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北段），若停车厂内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车迹可开入；停车场内某辆车要离开时，在它之后进入的车连必须先退出车厂为它让路，待该车辆开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车时必须按它停留的时间长短缴纳费用。编写按上述要求进行管理的模拟程序。可以将停车场定义成一个顺序栈s0，便道定义成一个链队列q，而停车场中的某辆车要离开，则在它后面进停车场的车必须让道，让其离开，所以必须有一个临时的顺序栈s1，存放让道的车辆。当有车辆进停车场时，若栈s0不满，则直接进入栈s0；若栈s0满，则进入便道（链队列q）。若有s0中车辆x离开时，先让在x后面进栈的车从s0退栈并进入栈s1中，让x离开并收取停车费（在便道上停留的时间不收费），然后再把s1中所有元素退栈并重新进入s0栈，最后，将链队列q中的队头元素出队并进栈到s0中。三、 程序源代码： #include #include #include #include #include #define SIZE 2 /停车场的停车位数量#define PRICE 6 /按分钟计费struct Car /车辆信息int carId;int inTime3;int outTime3;struct Time /时间int hour;int minute;int second;Time GetTime() /返回系统当前时间，返回值类型为Time型time_t nowtime; struct tm *gettime;time(&nowtime);gettime=localtime(&nowtime);Time time;time.hour=gettime-tm_hour;time.minute=gettime-tm_min;time.second=gettime-tm_sec;return time;struct StopStack /停车位信息Car *base;Car *top;int stackSize; /停车场容纳汽车数量int Count; /用来记录某车在车场中的车位序号，以及车场中已有的车辆数目;struct StopQueue /便道结点Car data;StopQueue *next;struct LinkQueue /便道队列StopQueue* front;StopQueue* rear;void InitStack(StopStack * S) /停车场位初始化，栈初始化（包括停车场和临时停车场的初始化）S-base=(Car*)malloc(SIZE*sizeof(Car);S-top=S-base;S-stackSize=SIZE;S-Count=0;void InitQueue(LinkQueue *Q) /初始化带头结点的对列Q-front=Q-rear=(StopQueue*)malloc(sizeof(StopQueue);Q-rear-next=NULL;/判断停车场是否为空int IsEmptyStack(StopStack *S)if(S-base=S-top)return 1;else return 0;/判断车辆是否存在int IsExist(StopStack *S,int num)Car *p=S-top;while(p!=S-base)p-;if(p-carId=num)return 1;return 0;/进入主停车场时获取该车进去的时间void InsertStack(StopStack *S,Car data) /向栈中添加元素，即进入主停车场if(S-Count=SIZE)return;S-top-carId=data.carId;/获取该车进入主停车场的时间 S-top-inTime0=GetTime().hour;S-top-inTime1=GetTime().minute;S-top-inTime2=GetTime().second;S-top+;S-Count+;/从临时停车场进入主停车场，此时不用获取进入车场的时间，进入时间仍是原先进入时间void InsertStack2(StopStack *S,Car data) if(S-Count=SIZE)return;S-top-carId=data.carId;S-top+;S-Count+;/进入临时停车场void InsertTempStack(StopStack *S,Car data) /进入临时停车场S-top-carId=data.carId;S-top+;S-Count+;/从主车场中出来Car OutStack(StopStack *S, int carNum) /出栈，出车场，carNum为当前要出车场的车牌号Car car;if(S-top!=S-base) /车场中有车辆时 S-top-; car.carId=S-top-carId; if(car.carId=carNum) /当是要出停车场的那辆车时才获取该车的进出时间 car.outTime0=GetTime().hour; /将出车场时的系统时间赋给car的出去时间 car.outTime1=GetTime().minute; car.outTime2=GetTime().second; car.inTime0=S-top-inTime0;/将该车进车场的时间赋给car的inTime car.inTime1=S-top-inTime1; car.inTime2=S-top-inTime2; S-Count-; return car;/从临时停车场中出去Car OutTempStack(StopStack *S) /从临时栈（临时车场）出去Car car;if(S-top!=S-base)S-top-;car.carId=S-top-carId;/strcpy_s(car.carId,S-top-carId);S-Count-;return car;/进入便道，不获取任何时间void InsertQueue(LinkQueue *Q,Car data) /进入队列（便道）,进去便道不计时StopQueue *p=(StopQueue*)malloc(sizeof(StopQueue);p-next=Q-rear-next;Q-rear-next=p;Q-rear=p;p-data.carId=data.carId;/strcpy_s(p-data.carId,data.carId);/从便道中出来Car OutQueue(LinkQueue *Q) /出队列Car car;StopQueue *p=Q-front-next;if(p=Q-rear) /当队列中只有一个元素是，需要在将结点释放前将rear指向front car.carId=p-data.carId; Q-rear=Q-front; free(p);else car.carId=p-data.carId; Q-front-next=p-next; free(p);return car;void print()printf(ttt欢迎使用XX停车场2.0Beta版n);printf(ttt请选择要进行的操作：（1-4）n);printf(ttt1 查看车位t 2 进入车场tn);printf(ttt3 出场缴费t 4 退出tn);/显示当前车场情况void ShowState(StopStack *S) /case 1if(S-Count=SIZE)printf(车位已满，请在便道上等候n);elseprintf(还有%d个车位n,SIZE-S-Count);/进入停车场void EnterPark(StopStack *S,LinkQueue *Q) /进入停车场 （case 1）Car car;printf(请输入您的车辆信息：n);printf(请输入您的车牌号：n);scanf(%d,&car.carId);if(S-Count=SIZE) /车位已满时，车辆进去便道等待printf(车位已满，请在便道上等候、n);InsertQueue(Q,car); /进入便道else InsertStack(S,car);/从停车场中出来void OutPark(LinkQueue *Q,StopStack *S0,StopStack *S1) /出车场时 case2int carNum; /carNum为要出车场的车辆printf(请输入您的车牌号：n); /按照车牌号进行查找scanf(%d,&carNum);while(1)if(IsExist(S0,carNum)=0) printf(不存在的车辆，请查询后再尝试、n); return ; Car car=OutStack(S0,carNum); /将车场中的车依次出车场，知道找到要出车场那辆车if(car.carId=carNum) /将是要出主停车场的车辆信息显示printf(您进停车场的时间为：%d:%d:%dn,car.inTime0,car.inTime1,car.inTime2);printf(您出停车场的时间为：%d:%d:%dn,car.outTime0,car.outTime1,car.outTime2);printf(您一共停了%d长时间，需缴纳%d刀费用n,(car.outTime0-car.inTime0)*60+(car.outTime1-car.inTime1),(car.outTime0-car.inTime0)+car.outTime1-car.inTime1)*PRICE);break;else/将不是要离开主停车场的车辆进入临时停车场InsertTempStack(S1,car);/在车辆从主停车场出来后，需要使停放在临时停车场中的车辆进入主停车场while(S1-Count!=0)Car car=OutTempStack(S1); /InsertStack(S0,car,carNum); /调用进入主停车场的重载函数，使从临时车场进入主车场InsertStack2(S0,car);if(Q-front!=Q-rear) /便道上车辆非空时，使最先进入便道的车辆进入主车场Car car1=OutQueue(Q);InsertStack(S0,car1);void main()StopStack S0; /初始化主停车场InitStack(&S0);LinkQueue Q;InitQueue(&Q); /初始化便道StopStack S1;InitStack(&S1); /初始化临时车场int num;while(1)print();scanf(%d,&num);switch(num)case 1:ShowState(&S0);break;case 2:EnterPark(&S0,&Q);break;case 3:OutPark(&Q,&S0,&S1);break;case 4:printf(感谢您的使用);exit(0);break;default :break;四、 测试结果：进入车场测试，车位初始大小为2，进入的第三辆车进入便道等候，运行结果如图2-1所示图2-1 入车场 出场缴费时，按照所停留的分钟数进行收费，便道车辆不计时，其结果如图2-2，车场中不存