停车场问题求解（经典算法）

#include <stdlib.h> #include <stdio.h> #define STACK_SIZE 3 enum boolean{ ERROR,OVERFLOW,OK }; typedef unsigned int STATUS; //--------------------------各个结构体定义-----------------------------------------------// struct SNode { int car_num; int arr_time; }; struct QNode { int car_num; int arr_time; QNode* next; }; struct Stack { SNode* base; SNode* top; int stacksize; }; struct Queue { QNode* front; QNode* rear; }; //---------------------------------结构体Stack操作函数定义-----------------------------------------// STATUS initStack(Stack &s) { s.base=(SNode*)malloc(STACK_SIZE*sizeof(SNode)); if(!s.base) return ERROR; s.top=s.base; s.stacksize=STACK_SIZE; return OK; } STATUS push(Stack &s,SNode &car) { *s.top++=car; return OK; } STATUS isfull(Stack &s) { if(s.top-s.base>=s.stacksize) return OK; return ERROR; } STATUS pop(Stack &s,SNode &car) { if(s.top==s.base) return ERROR; car=*--s.top; return OK; } STATUS Sisempty(Stack &s) { if(s.top==s.base) return OK; return ERROR; } //-----------------------------------------结构体Queue操作函数定义--------------------------------------------------// STATUS initQueue(Queue &q) { q.front=q.rear=(QNode*)malloc(sizeof(QNode)); if(!q.front) exit(OVERFLOW); q.front->next=NULL; return OK; } STATUS enQueue(Queue &q,SNode &car) { QNode* qcar = (QNode*)malloc(sizeof(QNode)); if(!qcar) exit(OVERFLOW); qcar->car_num=car.car_num; qcar->arr_time=car.arr_time; qcar->next=NULL; q.rear->next=qcar; q.rear = qcar; return OK; } STATUS deQueue(Queue &q,SNode &car,int leav_time) { if(q.front==q.rear) return ERROR; car.arr_time = leav_time; QNode* temp = q.front->next; car.car_num = temp->car_num; q.front->next=temp->next; free(temp); return OK; } STATUS Qisempty(Queue &q) { if(q.front->next==NULL) return OK; return ERROR; } void main() { char fir,te; int sec,thi; int fee = 0; struct SNode car; struct Stack box; struct Stack temp; struct Queue wait; initStack(box); initStack(temp); initQueue(wait); printf("enter the car's infor:"); scanf("%c %d %d",&fir,&sec,&thi); te = getchar(); car.car_num = sec; car.arr_time = thi; while(thi!='E') { if(fir == 'A') { if(isfull(box)) { enQueue(wait,car); } else { push(box,car); } } else if(fir == 'D') { struct SNode tem_car; struct SNode tem_car2; pop(box,tem_car); while(tem_car.car_num!=car.car_num) { push(temp,tem_car); pop(box,tem_car); } while(!Sisempty(temp)) { pop(temp,tem_car2); push(box,tem_car2); } if(!Qisempty(wait)) { deQueue(wait,tem_car2,thi); push(box,tem_car2); } fee = thi - tem_car.arr_time; printf("the fee of %d car is:%d\n",tem_car.car_num,fee); } printf("enter the car's infor:"); scanf("%c %d %d",&fir,&sec,&thi); te = getchar(); car.car_num = sec; car.arr_time = thi; } }