停车场管理

整理了一下最近做的数据结构实习作业

【问题描述】设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端），若停车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。

【基本要求】以栈模拟停车场，以队列模拟车场外的便道。栈以顺序结构实现，队列以链表结构实现。每一组输入数据包括：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。输出信息：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。

【测试数据】设n=2，输入数据为：（’A’,1,5），（’A’,2,10），（’D’,1,15），（’A’,3,20），（’A’,4,25），（’A’,5,30），（’D’,2,35），（’D’,4,40），（’E’,0,0）。其中：’A’表示到达；’D’表示离去；’E’表示输入结束。【实现提示】需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也可用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。

  1 #include"stack.h"
  2 struct point {
  3     int number ;
  4     int time;
  5 };
  6 
  7 typedef struct {
  8     point stack[MaxStackSize];
  9     int top ;
 10 }SeqStack ;
 11 
 12 void StackInitiate(SeqStack *S)
 13 {
 14     S->top=0;
 15 }
 16 
 17 int StackNotEmpty(SeqStack *S)
 18 {
 19     if(S->top<=0)
 20         return 0;
 21     else
 22         return 1;
 23 }
 24 
 25 void  StackPush(SeqStack *S,point x)
 26 {
 27     if(S->top>=MaxStackSize){
 28         printf("堆栈已满无法插入！\n");
 29     }else {
 30         S->stack[S->top++]=x ;
 31     }
 32 }
 33 
 34 void  StackPop(SeqStack *S, point *d)
 35 {
 36     if(S->top<=0){
 37         printf("堆栈已空无数据元素出栈！\n");
 38     }else {
 39         *d=S->stack[--S->top];
 40     }
 41 }
 42 
 43 void   StackTop(SeqStack *S,point *d)
 44 {
 45     if(S->top<=0){
 46         printf("堆栈已空！\n");
 47     }else {
 48         *d=S->stack[S->top-1];
 49     }
 50 }
 51 #include"queue.h"
 52 typedef struct qnode {
 53     point  data;
 54     struct qnode *next ;
 55 }LQNode ;
 56 
 57 typedef struct {
 58     LQNode *front ;
 59     LQNode *rear ;
 60 }LQueue ;
 61 
 62 void QueueInitiate(LQueue *Q)
 63 {
 64     Q->front=NULL ;
 65     Q->rear=NULL ;
 66 }
 67 
 68 int QueueNotEmpty(LQueue *Q)
 69 {
 70     if(Q->front==NULL)
 71         return 0;
 72     else 
 73         return 1;
 74 }
 75 
 76 void QueueAppend(LQueue *Q,point  x)
 77 {
 78     LQNode  *p;
 79     if((p=(LQNode *)malloc(sizeof(LQNode)))==NULL)
 80         printf("内存空间不足！\n");
 81     else {
 82         p->data=x;
 83         p->next=NULL;
 84 
 85         if(Q->rear!=NULL) Q->rear->next=p;
 86         Q->rear=p ;
 87         if(Q->front==NULL) Q->front=p ;
 88     }
 89 }
 90 
 91 void QueueDelete(LQueue *Q,point *d)
 92 {
 93     LQNode *p;
 94     if(Q->front==NULL)
 95         printf("队列已空无数据元素出队列！\n");
 96     else {
 97         *d=Q->front->data ;
 98         p=Q->front ;
 99         Q->front=Q->front->next ;
100         if(Q->front==NULL) Q->rear=NULL ;
101         free(p) ;
102     }
103 }
104 
105 void QueueGet(LQueue Q,point  *d)
106 {
107     if(Q.front==NULL)
108         printf("队列已空无数据元素可删！\n");
109     else 
110         *d=Q.front->data ;
111 }
112 
113 #include<stdio.h>
114 #include<malloc.h>
115 #define MaxStackSize 10
116 //#include"stack.h"
117 //#include"queue.h"
118 #define price 5
119 
120 int n ;
121 char ch ;
122 
123 void Arrive(SeqStack *Sa,LQueue *Q,point p)
124 {
125     if(Sa->top<n){
126         printf("停车场未满！\n");
127         StackPush(Sa,p);
128     }else {
129         printf("停车场已满，车停便道！\n");
130         QueueAppend(Q,p);
131     }
132 }
133 
134 void Leave(SeqStack *Sa,SeqStack *Sb,LQueue *Q,point p)
135 {
136 
137     point ph,pt;
138     StackTop(Sa,&ph);
139     while(ph.number!=p.number){
140         StackPop(Sa,&pt);
141         StackPush(Sb,pt);
142         if(!StackNotEmpty(Sa))break;
143         else StackTop(Sa,&ph);
144     }
145     if(!StackNotEmpty(Sa)){
146         printf("该车不在停车场！\n");
147         while(StackNotEmpty(Sb)){
148             point t;
149             StackPop(Sb,&t);
150             StackPush(Sa,t);
151         }
152     }else {
153         StackPop(Sa,&pt);
154         int s_time=p.time-pt.time;
155         printf("%d\n",s_time*price);
156         while(StackNotEmpty(Sb)){
157             point t;
158             StackPop(Sb,&t);
159             StackPush(Sa,t);
160         }
161         if(QueueNotEmpty(Q)){
162             point t;
163             QueueDelete(Q,&t);
164             t.time=p.time ;
165             StackPush(Sa,t);
166         }
167     }
168 }
169         
170 int main()
171 {
172     SeqStack Sa,Sb ;
173     LQueue Q ;
174     point p;
175     printf("请输入停车场的容量：\n");
176     scanf("%d",&n) ;
177     StackInitiate(&Sa) ;
178     StackInitiate(&Sb) ;
179     QueueInitiate(&Q) ;
180     while(1)
181     {
182         scanf("%c,%d,%d",&ch,&p.number,&p.time) ;
183         if(ch=='A')
184             Arrive(&Sa,&Q,p);
185         else if(ch=='D')
186             Leave(&Sa,&Sb,&Q,p);
187         else if(ch=='E')
188             break ;
189     }
190     return 0;
191 }

【选作内容】（1）两个栈共享空间，思考应开辟数组的空间是多少？（2）汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3 辆小汽车的占地面积。（3）停放在便道上的汽车也收费，收费标准比停放在停车场的车低。