C语言数据结构-algo3-12.c

blake

1. /* algo3-12.c 银行业务模拟。实现算法3.6、3.7的程序 */
   
2. #define Qu 4 /* 客户队列数 */
   
3. #define Khjg 5 /* 两相邻到达的客户的时间间隔最大值 */
   
4. #define Blsj 30 /* 每个客户办理业务的时间最大值 */
   
5. #include"c1.h"
   
6. 
   
7. typedef struct /* 定义ElemType为结构体类型 */
   
8. {
   
9.    int OccurTime; /* 事件发生时刻 */
   
10.    int NType; /* 事件类型，Qu表示到达事件,0至Qu-1表示Qu个窗口的离开事件 */
    
11. }Event,ElemType; /* 事件类型，有序链表LinkList的数据元素类型 */
    
12. 
    
13. #include"c2-5.h"
    
14. typedef LinkList EventList; /* 事件链表类型，定义为有序链表 */
    
15. #include"bo2-6.c" /* 使用已有的链表基本操作 */
    
16. 
    
17. typedef struct
    
18. {
    
19.    int ArrivalTime; /* 到达时刻 */
    
20.    int Duration; /* 办理事务所需时间 */
    
21. }QElemType; /* 定义QElemType(队列的数据元素类型)为结构体类型; */
    
22. 
    
23. #include"c3-2.h"
    
24. #include"bo3-2.c" /* 使用已有的队列基本操作 */
    
25. 
    
26. /* 程序中用到的主要变量(全局)。算法3.7 */
    
27. EventList ev; /* 事件表 */
    
28. Event en; /* 事件 */
    
29. Event et; /* 临时变量 */
    
30. LinkQueue q[Qu]; /* Qu个客户队列 */
    
31. QElemType customer; /* 客户记录 */
    
32. int TotalTime=0,CustomerNum=0; /* 累计客户逗留时间,客户数(初值为0) */
    
33. int CloseTime; /* 银行营业时间(单位是分) */
    
34. 
    
35. int cmp(Event a,Event b)
    
36. { /* 依事件a的发生时刻<、=或>事件b的发生时刻分别返回-1、0或1 */
    
37.    if(a.OccurTime==b.OccurTime)
    
38.      return 0;
    
39.    else
    
40.      return (a.OccurTime-b.OccurTime)/abs(a.OccurTime-b.OccurTime);
    
41. }
    
42. 
    
43. void OpenForDay()
    
44. { /* 初始化操作 */
    
45.    int i;
    
46.    InitList(&ev); /* 初始化事件链表为空 */
    
47.    en.OccurTime=0; /* 设定第一个客户到达事件 */
    
48.    en.NType=Qu; /* 到达 */
    
49.    OrderInsert(&ev,en,cmp); /* 插入事件表 */
    
50.    for(i=0;i<Qu;++i) /* 置空队列 */
    
51.      InitQueue(&q[i]);
    
52. }
    
53. 
    
54. void Random(int *d,int *i)
    
55. {
    
56.    *d=rand()%Blsj+1; /* 1到Blsj之间的随机数 */
    
57.    *i=rand()%Khjg+1; /* 1到Khjg之间的随机数 */
    
58. }
    
59. 
    
60. int Minimum(LinkQueue Q[]) /* 返回最短队列的序号 */
    
61. {
    
62.    int l[Qu];
    
63.    int i,k;
    
64.    for(i=0;i<Qu;i++)
    
65.      l[i]=QueueLength(Q[i]);
    
66.    k=0;
    
67.    for(i=1;i<Qu;i++)
    
68.      if(l[i]<l[0])
    
69.      {
    
70.        l[0]=l[i];
    
71.        k=i;
    
72.      }
    
73.    return k;
    
74. }
    
75. 
    
76. void CustomerArrived()
    
77. { /* 处理客户到达事件，en.NType=Qu */
    
78.    QElemType f;
    
79.    int durtime,intertime,i;
    
80.    ++CustomerNum;
    
81.    Random(&durtime,&intertime); /* 生成随机数 */
    
82.    et.OccurTime=en.OccurTime+intertime; /* 下一客户到达时刻 */
    
83.    et.NType=Qu; /* 队列中只有一个客户到达事件 */
    
84.    if(et.OccurTime<CloseTime) /* 银行尚未关门，插入事件表 */
    
85.      OrderInsert(&ev,et,cmp);
    
86.    i=Minimum(q); /* 求长度最短队列的序号,等长为最小的序号 */
    
87.    f.ArrivalTime=en.OccurTime;
    
88.    f.Duration=durtime;
    
89.    EnQueue(&q[i],f);
    
90.    if(QueueLength(q[i])==1)
    
91.    {
    
92.      et.OccurTime=en.OccurTime+durtime;
    
93.      et.NType=i;
    
94.      OrderInsert(&ev,et,cmp); /* 设定第i队列的一个离开事件并插入事件表 */
    
95.    }
    
96. }
    
97. 
    
98. void CustomerDeparture()
    
99. { /* 处理客户离开事件，en.NTyPe<Qu */
    
100.    int i;
     
101.    i=en.NType;
     
102.    DeQueue(&q[i],&customer); /* 删除第i队列的排头客户 */
     
103.    TotalTime+=en.OccurTime-customer.ArrivalTime; /* 累计客户逗留时间 */
     
104.    if(!QueueEmpty(q[i]))
     
105.    { /* 设定第i队列的一个离开事件并插入事件表 */
     
106.      GetHead_Q(q[i],&customer);
     
107.      et.OccurTime=en.OccurTime+customer.Duration;
     
108.      et.NType=i;
     
109.      OrderInsert(&ev,et,cmp);
     
110.    }
     
111. }
     
112. 
     
113. void Bank_Simulation()
     
114. {
     
115.    Link p;
     
116.    OpenForDay(); /* 初始化 */
     
117.    while(!ListEmpty(ev))
     
118.    {
     
119.      DelFirst(&ev,GetHead(ev),&p);
     
120.      en.OccurTime=GetCurElem(p).OccurTime;
     
121.      en.NType=GetCurElem(p).NType;
     
122.      if(en.NType==Qu)
     
123.        CustomerArrived(); /* 处理客户到达事件 */
     
124.      else
     
125.        CustomerDeparture(); /* 处理客户离开事件 */
     
126.    } /* 计算并输出平均逗留时间 */
     
127.    printf("顾客总数:%d, 所有顾客共耗时:%d分钟, 平均每人耗时: %d分钟\n",CustomerNum,TotalTime,TotalTime/CustomerNum);
     
128. }
     
129. 
     
130. void main()
     
131. {
     
132.    printf("请输入银行营业时间长度(单位:分)\n");
     
133.    scanf("%d",&CloseTime);
     
134.    Bank_Simulation();
     
135. }

复制代码