数据结构——银行排队模拟

  1 //离散事件模拟，模拟银行营业排队情况
  2 #include <stdio.h>
  3 #include <time.h>
  4 #include <stdlib.h>
  5 
  6 #define OK 1
  7 #define  ERROR 0
  8 #define TRUE 1
  9 #define FALSE 0
 10 
 11 typedef int Status;
 12 
 13 typedef struct Event{    //事件类型
 14     int OccurTime;        //事件发生时刻
 15     int NType;            //事件类型，0表示到达事件，1-4表示4个窗口离开事件
 16     struct Event *next;
 17 }Event,*ElemType;
 18 
 19 typedef struct{            //链表类型
 20     ElemType head;
 21     ElemType tail;
 22     int len;
 23 }LinkList;
 24 
 25 typedef LinkList EventList;        //事件链表
 26 
 27 typedef struct QElem{            //队列元素
 28     int ArrveTime;                //到达时间
 29     int Duration;                //办理事务所需事件
 30     struct QElem *next;
 31 }QElem,*QElemType;
 32 
 33 typedef struct{        //队列类型
 34     QElemType head;
 35     QElemType tail;
 36 }LinkQueue;
 37 
 38 Status InitList(LinkList *L);    //初始化事件链表
 39 Status OrderInsert(LinkList *L, Event e);    //将事件e按时间顺序插入有序链表L中
 40 Status ListEmpty(LinkList *L);    //判断链表为空，为空返回TRUE
 41 Status DelFirst(LinkList *L,ElemType e);    //删除链表首结点，用e返回
 42 Status ListTraverse(LinkList *L);    //遍历链表
 43 
 44 Status InitQueue(LinkQueue *Q);        //初始化队列
 45 Status EmptyQueue(LinkQueue *Q);    //判断队列为空
 46 Status DelQueue(LinkQueue *Q, QElemType e);    
 47 Status EnQueue(LinkQueue *Q, QElem e);    //接点e插入队列
 48 int       QueueLength(LinkQueue Q);
 49 Status GetHead(LinkQueue *Q, QElemType e);    //取队列首部结点e
 50 Status QueueTraverse(LinkQueue *Q);
 51 
 52 Event NewEvent(int occurTime, int nType);    //创建新事件
 53 
 54 int Min(int a[], int n);    //返回长度为n的数组a[]第一个最小下标，从1开始
 55 int ShortestQueue();        //获取最短队列编号
 56 void OpenForDay();            //初始化操作
 57 void CustomerArriver();        //顾客到达事件
 58 void CustomerDeparture();    //顾客离开事件
 59 void Bank_Simulation();        //银行排队模拟
 60 void PrintEventList();        //输出事件列表
 61 void PrintQueue();            //打印当前队列
 62 
 63 EventList ev;
 64 Event en;
 65 LinkQueue q[5];
 66 QElem customer;
 67 int TotalTime, CustomerNum;
 68 int CloseTime = 50;
 69 
 70 //----------------------main()--------------------//
 71 int main()
 72 {
 73     Bank_Simulation();
 74     return 0;
 75 }
 76 
 77 //-----------------------模拟排队----------------//
 78 void OpenForDay()
 79 {
 80     int i;
 81     TotalTime = 0; 
 82     CustomerNum = 0;
 83     InitList(&ev);
 84     en.OccurTime = 0;
 85     en.NType = 0;
 86     OrderInsert(&ev, en);
 87     for (i = 1; i < 5; i++)
 88         InitQueue(&q[i]);
 89 }
 90 
 91 void CustomerArrived() 
 92 {
 93     int durtime, intertime, i, t;
 94     QElem e;
 95     ++CustomerNum;
 96     intertime = rand() % 5 + 1;
 97     durtime = rand() % 30 + 1;
 98     t = en.OccurTime + intertime;
 99     if (t < CloseTime)
100     {
101         printf("A new customer will arrive at:%d
", t);
102         OrderInsert(&ev, NewEvent(t, 0));
103         i = ShortestQueue();
104         e.ArrveTime = en.OccurTime;
105         e.Duration = durtime;
106         EnQueue(&q[i], e);
107         if (QueueLength(q[i]) == 1)
108             OrderInsert(&ev, NewEvent(en.OccurTime + durtime, i));
109     }
110 }
111 
112 void CustomerDeparture() 
113 {    
114     int i = en.NType;
115     DelQueue(&q[i], &customer);
116     printf("A customer leaves at:%d
", en.OccurTime);
117     TotalTime += en.OccurTime - customer.ArrveTime;
118     if (!EmptyQueue(&q[i]))
119     {
120         GetHead(&q[i], &customer);
121         OrderInsert(&ev, NewEvent(en.OccurTime + customer.Duration, i));
122     }
123 }
124 
125 void Bank_Simulation()
126 {
127     OpenForDay();
128     srand((unsigned)time(NULL));
129     while(!ListEmpty(&ev)) {
130         DelFirst(&ev, &en);
131         if (en.NType == 0)
132             CustomerArrived();
133         else
134             CustomerDeparture();
135         PrintQueue();
136     }
137     printf("
Total time is:%d min,average time is: %g min.
",TotalTime,
138         (float)TotalTime/CustomerNum);
139 }
140 
141 void PrintQueue()
142 {
143     int i;
144     for ( i = 1; i < 5; i ++)
145     {
146         printf("Queue %d have %d customer(s):", i, QueueLength(q[i]));
147         QueueTraverse(&q[i]);
148     }
149     printf("
");
150 }
151 
152 void PrintEventList() 
153 {
154     printf("Current Eventlist is:
");
155     ListTraverse(&ev);
156 }
157 
158 int Min(int a[], int n)
159 {
160     int i, tmp, ind = 0;
161     tmp = a[0];
162     for (i = 1; i < n; i ++)
163         if (a[i] < tmp)
164         {
165             tmp = a[i];
166             ind = i;
167         }
168     return ind;
169 }
170 
171 int ShortestQueue()
172 {
173     int i, a[4];
174     for(i = 1; i <= 4; i++)
175         a[i-1] = QueueLength(q[i]);
176     return Min(a, 4) + 1;
177 }
178 
179 //------------------------队和栈表操作-------------------//
180 Event NewEvent(int occurT, int nType)
181 {
182     Event e;
183     e.OccurTime = occurT;
184     e.NType = nType;
185     return e;
186 }
187 
188 Status InitList(LinkList *L)
189 {
190     L->head = L->tail = (ElemType)malloc(sizeof(Event));
191     if (!L->head) 
192     {
193         printf("Apply for memory error.LinkList initializefailed.
");
194         exit(0);
195     }
196 
197     L->head->next = NULL;
198     return OK;
199 }
200 
201 Status OrderInsert(LinkList *L, Event e)
202 {
203     ElemType p, q, newptr;
204     newptr = (ElemType)malloc(sizeof(Event));
205     if(!newptr)
206     {
207         printf("Apply for memory error.
");
208         exit(0);
209     }
210     *newptr = e;
211     if (TRUE == ListEmpty(L))
212     {
213         L->head->next = newptr;
214         L->tail = newptr;
215         L->tail->next = NULL;
216         return OK;
217     }
218     q = L->head;
219     p = L->head->next;
220     while(p)
221     {
222         if (p->OccurTime >= newptr->OccurTime)
223             break;
224         q = p;
225         p = p->next;
226     }
227     q->next = newptr;
228     newptr->next = p;
229     if (!p)
230         L->tail = newptr;
231     return OK;
232 }
233 
234 Status ListEmpty(LinkList *L)
235 {
236     if((L->head == L->tail) && (L->head != NULL))
237         return TRUE;
238     else
239         return FALSE;
240 }
241 
242 Status DelFirst(LinkList *L, ElemType e)
243 {
244     ElemType p = L->head->next;
245     if (!p)
246         return ERROR;
247     L->head->next = p->next;
248     *e = *p;
249     free(p);
250     if (L->head->next == NULL)
251         L->tail = L->head;
252     return OK;
253 }
254 
255 Status ListTraverse(LinkList *L)
256 {
257     ElemType p = L->head->next;
258     if (!p)
259     {
260         printf("List is empty.
");
261         return ERROR;
262     }
263     while (p)
264     {
265         printf("OccurTime:%d, Event Type:%d
", p->OccurTime, p->NType);
266         p = p->next;
267     }
268     printf("
");
269     return OK;
270 }
271 
272 Status InitQueue(LinkQueue *Q)
273 {
274     Q->head = Q->tail = (QElemType)malloc(sizeof(QElem));
275     if (!Q->head)
276     {
277         printf("Apply for memory error.LinkQueue initialize failed.
");
278         exit(0);
279     }
280     Q->head->next = NULL;
281     return OK;
282 }
283 
284 Status EmptyQueue(LinkQueue *Q)
285 {
286     if ((Q->head == Q->tail) && (Q->head != NULL))
287         return TRUE;
288     else
289         return FALSE;
290 }
291 
292 Status DelQueue(LinkQueue *Q, QElemType e)
293 {
294     QElemType p = Q->head->next;
295     if (!p)
296         return    ERROR;
297     *e = *p;
298     Q->head->next = p->next;
299     free(p);
300     if (!Q->head->next)
301         Q->tail = Q->head;
302     return OK;
303 }
304 
305 Status EnQueue(LinkQueue *Q, QElem e)
306 {
307     QElemType p = (QElemType)malloc(sizeof(QElem));
308     if (!p)
309     {
310         printf("Apply for memory error, new element can't enqueue.
");
311         exit(0);
312     }
313     *p = e;
314     p->next = NULL;
315     Q->tail->next = p;
316     Q->tail = p;
317     return OK;
318 }
319 
320 int QueueLength(LinkQueue Q)
321 {
322     int count = 0;
323     QElemType p = Q.head->next;
324     while(p)
325     {
326         count ++;
327         p = p->next;
328     }
329     return count;
330 }
331 
332 Status GetHead(LinkQueue *Q, QElemType e)
333 {
334     if (EmptyQueue(Q))
335         return ERROR;
336     e = Q->head->next;
337     return OK;
338 }
339 
340 Status QueueTraverse(LinkQueue *Q)
341 {
342     QElemType p = Q->head->next;  
343     if(!p){  
344         printf("--Is empty.
");  
345         return ERROR;  
346     }  
347     while(p){  
348         printf("(%d,%d) ",p->ArrveTime,p->Duration);  
349         p = p->next;  
350     }  
351     printf("
");  
352     return OK;  
353 }