实验五 栈、队列的高级应用—停车场管理.doc

实验五 栈、队列的高级应用停 车 场 管 理【实验目的】实现停车场管理【问题描述】设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆次序。编制一程序模拟该停车场的管理。【需求分析】停车场采用栈式结构，停车场外的便道采用队列结构（即便道就是等候队列）。停车场的管理流程如下： 当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进栈（车辆进入停车场）；如果停车场已满，则车辆进入等候队列（车辆进入便道等候）。 当车辆要求出栈时，该车到栈顶的那些车辆先弹出栈（在它之后进入的车辆必须先退出车场为它让路），再让该车出栈，其他车辆再按原次序进栈（进入车场）。当车辆出栈完毕后，检查等候队列（便道）中是否有车，有车则从队列头取出一辆车压入栈中。候车场停车场让车场进出让提示：可把停车场内的车辆管理看做是堆栈，采用先进后出的运算规则；而在停车场外排队的车辆管理，可以看做是队列，采用先进先出的运算规则。基本思想：根据题目要求，停车场只有一个大门，因此可用一个栈来模拟。而当栈满后，继续来到的车辆只能停在便道上，根据便道停车的特点，可知这可以用一个队列来模拟，先排队的车辆先离开便道，进入停车场。由于排在停车场中间的车辆可以提出离开停车场，并且要求在离开车辆到停车场大门之间的车辆都必须离开停车场，让此车辆离去，然后再让这些车辆依原来的次序进入停车场，因此在一个栈和一个队列的基础上，还需要有一个地方保存为了让路离开停车场的车辆，很显然这也应该用一个栈来模拟，因此，本题中要用到两个栈和一个队列。【实验环境】VC+运行环境【实验步骤及代码】 #include stdio.h #include stdlib.h #include string.h /*-*/ #define MAX 2 /*车库容量*/ #define price 0.05 /*每车每分钟费用*/ typedef struct time int hour; int min; Time; /*时间结点*/ typedef struct node char num10; Time reach; Time leave; CarNode; /*车辆信息结点*/ typedef struct NODE CarNode *stackMAX+1; int top; SeqStackCar; /*模拟车站*/ typedef struct car CarNode *data; struct car *next; QueueNode; typedef struct Node QueueNode *head; QueueNode *rear; LinkQueueCar; /*模拟通道*/ /*-*/ void InitStack(SeqStackCar *); /*初始化栈*/ int InitQueue(LinkQueueCar *); /*初始化便道*/ int Arrival(SeqStackCar *,LinkQueueCar *); /*车辆到达*/ void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *); /*车辆离开*/ void List(SeqStackCar,LinkQueueCar); /*显示存车信息*/ /*-*/ void main() SeqStackCar Enter,Temp; LinkQueueCar Wait; int ch; InitStack(&Enter); /*初始化车站*/ InitStack(&Temp); /*初始化让路的临时栈*/ InitQueue(&Wait); /*初始化通道*/ while(1) printf(n1. the car arrive); printf( 2. the car leave); printf( 3. the schedule ); printf( 4. outn); while(1) scanf(%d,&ch); if(ch=1&chtop=0; for(i=0;istacks-top=NULL; int InitQueue(LinkQueueCar *Q) /*初始化便道*/ Q-head=(QueueNode *)malloc(sizeof(QueueNode); if(Q-head!=NULL) Q-head-next=NULL; Q-rear=Q-head; return(1); else return(-1); void PRINT(CarNode *p,int room) /*打印出站车的信息*/ int A1,A2,B1,B2; printf(nplease input thedepart time:/*:*/); scanf(%d:%d,&(p-leave.hour),&(p-leave.min); printf(nthe number of the car:); puts(p-num); printf(nthe time the car arrive: %d:%d,p-reach.hour,p-reach.min); printf(the depart time: %d:%d,p-leave.hour,p-leave.min); A1=p-reach.hour; A2=p-reach.min; B1=p-leave.hour; B2=p-leave.min; printf(nthe fee: %2.1f元,(B1-A1)*60+(B2-A2)*price); free(p); int Arrival(SeqStackCar *Enter,LinkQueueCar *W) /*车辆到达*/ CarNode *p; QueueNode *t; p=(CarNode *)malloc(sizeof(CarNode); flushall(); printf(ninput the number of the car(例:陕A1234):); gets(p-num); if(Enter-toptop+; printf(nthe place of the car.,Enter-top); printf(nthe time thecar arrive:/*:*/); scanf(%d:%d,&(p-reach.hour),&(p-reach.min); Enter-stackEnter-top=p; return(1); else /*车场已满，车进便道*/ printf(n该车须在便道等待!); t=(QueueNode *)malloc(sizeof(QueueNode); t-data=p; t-next=NULL; W-rear-next=t; W-rear=t; return(1); void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) /*车辆离开*/ int i, room; CarNode *p,*t; QueueNode *q; /*判断车场内是否有车*/ if(Enter-top0) /*有车*/ while(1) /*输入离开车辆的信息*/ printf(n请输入车在车场的位置/1-%d/：,Enter-top); scanf(%d,&room); if(room=1&roomtop) break; while(Enter-toproom) /*车辆离开*/ Temp-top+; Temp-stackTemp-top=Enter-stackEnter-top; Enter-stackEnter-top=NULL; Enter-top-; p=Enter-stackEnter-top; Enter-stackEnter-top=NULL; Enter-top-; while(Temp-top=1) Enter-top+; Enter-stackEnter-top=Temp-stackTemp-top; Temp-stackTemp-top=NULL; Temp-top-; PRINT(p,room); /*判断通道上是否有车及车站是否已满*/ if(W-head!=W-rear)&Enter-tophead-next; t=q-data; Enter-top+; printf(n便道的%s号车进入车场第%d位置.,t-num,Enter-top); printf(n请输入现在的时间/*:*/:); scanf(%d:%d,&(t-reach.hour),&(t-reach.min); W-head-next=q-next; if(q=W-rear) W-rear=W-head; Enter-stackEnter-top=t; free(q); else printf(n便道里没有车.n); else printf(n车场里没有车.); /*没车*/ void List1(SeqStackCar *S) /*列表显示车场信息*/ int i; if(S-top0) /*判断车站内是否有车*/ printf(n车场:); printf(n 位置 到达时间 车牌号n); for(i=1;itop;i+) printf( %d ,i); printf(%d:%d ,S-stacki-reach.hour,S-stacki-reach.min); puts(S-stacki-num); else printf(n车场里没有车); void List2(LinkQueueCar *W) /*列表显示便道信息*/ QueueNode *p; p=W-head-next; if(W-head!=W-rear) /*判断通道上是否有车*/ printf(n等待车辆的号码为:); while(p!=NULL) puts(p-data-num); p=p-next; else printf(n便道里没有车.); void List(SeqStackCar S,LinkQueueCar W) int flag,tag; flag=1; while(flag) printf(n请