[队列](2.1)离散事件模拟
为了计算这个平均时间，我们自然需要掌握每个客户到达银行和离开银行这两个时刻，后者减去前者即为每个客户在银行的逗留时间。
所有客户逗留时间的总和被一天内进入银行的客户数除便是所求的平均时间，称客户到达银行和离开银行这两个时刻发生的事情为“事件”，则整个模拟程序将事件发生的先后顺序进行处理，这样一种模拟程序称为事件驱动模拟。
这个例子其实乍一眼看上去很难理解，但是无非就是队列的操作和有序链表的操作罢了。
算法的主要对象是“事件”，事件的主要信息是事件类型和事件发生的时刻
算法中处理的事件有两类：
一类是客户到达事件，另一类是客户离开事件
- 前一类事件发生的时刻随客户到来自然形成
- 后一类事件发生的时刻则由客户事务所需时间和等待所耗时间而定。
由于程序驱动是按事件发生时刻的先后顺序进行，则事件表应该是有序表，其主要的操作是插入和删除。
还需要另外一个模拟窗口表示客户排队的队列，由于前面假设银行有4个窗口，因此程序中需要4个队列
队列中有关客户的主要信息是客户到达的时刻和客户办理事务所需的时间
他办完事务离开队列的时刻就是即将发生的客户离开事件的时刻，这就是说，对每个队头客户都存在：
- 新的客户到达
- 0号窗口客户离开
- 1号窗口客户离开
- 2号窗口客户离开
3号窗口客户离开
- 由于数组下标从0开始，则由0定义
从上分析可见，在这个模拟程序中只需要两种数据类型：有序链表和队列。
它们的类型分别定义如下：
typedef struct
{
int OccurTime;//事件发生时刻;
int NType;//事件类型，-1代表新事件，0到3代表离开事件
}Event,ElemType;//事件类型，有序链表LinkList的数据元素类型
typedef struct
{
int ArrivlTime;//到达时刻
int Duration;//办理事务所需时间
}QElemType;//队列数据元素类型由于在实际的银行中，客户到达的时刻及其办理事务所需的时间都是随机的，在模拟程序中可用随机数来代替。
不失一般性，假设第一个顾客进门的时刻为0，即是模拟程序处理的第一个事件,之后每个客户到达的时刻在前一个客户到达时设定。
因此，在客户到达时需先产生两个随机数。其一位此刻到达客户办理业务所需时间，其二是为下一个客户到达的时间间隔。
由此产生一个新的客户到达事件插入事件表，刚到达的客户则应插入到当前所含元素最少的队列中，若该队列在插入前为空，则还应产生一个客户离开事件插入事件表。
书上的例子很难理解，各位有相同书籍的就自己看看
我不放博客上了，我理解这算法观看的是懒猫老师的教程。
点击此处观看教程
教程通俗易懂，但是要了解思想必须二刷甚至三刷。
下面通过懒猫老师给的教程做一个笔记
首先需要定义一个模拟银行窗口的队列数组：由于由4个窗口，我不习惯定义尾指针，总觉得不好操作，则只定义了头指针，当作单链表去操作，尾指针通过遍历找到，这样更好理解和后续操作。定义如下：
typedef struct evNode
{
QElemType data;
struct evNode* next;
}evLNode, * evLinkList;
typedef struct evArr
{
evLinkList head;
}evArr;
evArr ev[4];然后我们需要建立一个存储事件的链表，删除在头端，而插入则需要找到正确的位置插入，定义如下：
typedef struct Node
{
ElemType data;
struct Node* next;
}LNode, * LinkList;
LinkList head, temp, node;temp作为临时指针，之后的程序可能用到，现在这定义了，head作为头指针，指向头结点，而node作为结点指针，用于生成新的链表结点。
由于需要的是有序链表，则还需要定义一个排序数组，思路是把已有链表当作一个有序链表，从头开始，用指定的数值去向后遍历，找到合适的位置插入，这就是一个插入算法增加一个条件而已，算法如下：
int InsertLinkList(LinkList *L,ElemType data)
{
LinkList p, s;
p = *L;
s = (*L)->next;
node = (LinkList)malloc(sizeof(LNode));
node->data.NType = data.NType;
node->data.OccurTime = data.OccurTime;
node->next = NULL;
if (p == NULL)
{
p->next = node;
}
else
{
while (s != NULL)
{
if (s->data.OccurTime > node->data.OccurTime)
{
break;
}
p = s;
s = s->next;
}
}
node->next = s;
p->next = node;
}然后就是链表的删除操作，根据前面分析，删除是从头端开始，则定义一个头删的算法，算法如下：
void DeleteLinkList(LinkList *L, ElemType* data)
{
LinkList p;
p = (*L)->next;
(*L)->next = p->next;
data->NType = p->data.NType;
data->OccurTime = p->data.OccurTime;
free(p);
}最重要的一步是初始化链表和队列
初始化链表的操作没有大的变化，初始化数组就是建立一个循环，逐次为数组中的4个元素去申请空间，算法如下：
链表
int InitLinkList(LinkList *L)
{
*L = (LinkList)malloc(sizeof(LNode));
if (L == NULL)
{
exit(0);
}
(*L)->next = NULL;
}队列数组
int InitevArr()
{
for (int i = 0; i < 4; i++)
{
ev[i].head = (evLinkList)malloc(sizeof(evLNode));
ev[i].head->next = NULL;
}
return 0;
}还有就是为队列插入数值，思路就是根据指定的下标找到对应的队列，进行插入操作，队列的特点就是先进先出，则删除和插入都是在头端。算法如下：
void InQueeArr(int i, QElemType data)
{
//为下标为i的队列元素插入data的值
struct evNode* node;
evLinkList p = ev[i].head;
node = (evLinkList)malloc(sizeof(LNode));
node->data.ArrivlTime = data.ArrivlTime;
node->data.Duration = data.Duration;
node->next = NULL;
while (p->next != NULL)
{
p = p->next;
}
p->next = node;
}删除操作也是在头端进行
void OutQueArr(int i, QElemType* data)
{
struct evNode* temp = ev[i].head->next;
ev[i].head->next = temp->next;
data->ArrivlTime = temp->data.ArrivlTime;
data->Duration = temp->data.Duration;
free(temp);
}我们来看看核心算法中需要用到那些功能，再依次去实现它的函数
- 首先，根据教程所述，队列的长度需要求出来
- 长度对应的是窗口排队的人数，每次插入新的事件到队列的时候，都需要找到人数最少，也就是长度最小的队列进行操作，我们需要定义一个求队列长度和比较队列长度并返回长度最小队列在数组中下标的函数。
求队列长度，定义一个计数变量，然后遍历队列，每走到一个结点，计数变量增1，直到走完，算法如下：
int QueueLength(int i)
{
int count = 0;
evLinkList p;
p = ev[i].head->next;
while (p != NULL)
{
p = p->next;
count++;
}
return count;
}如果窗口长度一样，则按先后顺序插入，算法如下：
int MinEvArr(evArr Arr[])
{
int a, b, c, d;
a = QueueLength(0);
b = QueueLength(1);
c = QueueLength(2);
d = QueueLength(3);
if (a <= b)
{
if (a <= c)
{
if (a <= d)
{
return 0;
}
}
}
if (b <= a)
{
if (b <= c)
{
if (b <= d)
{
return 1;
}
}
}
if (c <= a)
{
if (c <= b)
{
if (c <= d)
{
return 2;
}
}
}
if (d <= a)
{
if (d <= b)
{
if (d <= c)
{
return 3;
}
}
}
}这个时候就可以编写核心函数了，我们来看看大体思路：
我们需要定义一个事件表类型的临时变量
- 里边存储客户达到的时间和客户的类型
- 客户类型分为-1或对应数组下标0到3
我们需要定义一个队列元素类型的临时变量
- 里边存储客户到达的时间和客户需要服务的时间
- 在银行开门的时候，第一个客户到来，类型为-1，插入到事件表中
- 循环由事件表来决定，当还有新的事件，则循环不结束，所以循环的结束条件是事件表为空
进入循环的第一步就是从事件表中删除一个元素，放入临时变量中
- 判断事件的类型，如果是-1，则生成两个随机数，随机数为所需的服务时间和下一个客户的间隔时间
- 同时计算出当前排队人数最少的窗口，然后将当前客户的到达时间以及服务时间两个单元通过队列临时变量传入对应的队列中。
通过这两个随机数我们可以判断下一个客户到来的时间，由当前客户到来的时间加上下一个客户的时间间隔可以得到下一个客户的到达时间。
- 这个时候需要判断下一个客户到达时间是否超过了银行的关门时间，如果超过了，则停止将此插入事件表
- 如果事件类型是0-3，则需要删除对应队列的结点，同时需要判断删除后它后面
是否只存在一个结点
- 如果只存在一个结点，则可以预估出这个事件的离开时间，由服务时间和到达时间相加，通过事件临时变量传入事件表
上述是自己的思路理解，需要反复观看教程才能理解透彻，下面对代码做一个剖析
根据上述思路，核心代码如下所示：
int Bank_Simulation()
{
InitLinkList(&head);
InitevArr();
ElemType temp;
QElemType temp2;
int totalTime = 0, totalnum = 0;
temp.NType = -1;//到达类型，初始化
temp.OccurTime = 0;//到达时间
InsertLinkList(&head, temp);
while (head->next != NULL)
{
DeleteLinkList(&head, &temp);
if (temp.NType == -1)
{
totalnum++;
int Min = MinEvArr(ev);
int x = rand();
int y = rand();
temp2.ArrivlTime = temp.OccurTime;
temp2.Duration = x;
if (temp.OccurTime + y < COLSE_MAX)
{
temp.OccurTime = temp.OccurTime + y;
temp.NType = -1;
InsertLinkList(&head, temp);
}
InQueeArr(Min, temp2);
if (QueueLength(Min) <= 1)
{
temp.NType = Min;
temp.OccurTime = temp2.Duration + temp2.ArrivlTime;
InsertLinkList(&head, temp);
}
visit();
}
else
{
OutQueArr(temp.NType, &temp2);
totalTime += temp2.Duration;
if (ev[temp.NType].head->next != NULL)
{
temp.OccurTime = ev[temp.NType].head->next->data.Duration;
InsertLinkList(&head, temp);
}
}
printf("\n\n");
}
printf("接待总人数为：%d,总营业时间为：%d", totalnum, totalTime);
printf("平均逗留时间为：%.2lf分钟", totalTime*1.0 / totalnum);
system("pause");
return 0;
}
这一代码块初始化了事件表以及队列数组，同时定义了两个临时变量，用于后边存储链接所用，当银行开始的时候定义了第一个客户到来，类型为-1，到达时间为0，将它存入到链表中。
进入循环中判断的条件是链表是否为空，然后删除结点，取出值，更新temp的值，判断事件类型，同时人数字怎，再找到这个时候队列数组中人数最小的值，存放到Min变量中，然后生成两个随机数。
将当前客户的到达时间以及服务时间存入到temp2，传入到相应的队列中。
同时根据当前客户到达时间以及下一客户间隔时间判断是否到银行的关门时间，如果不到，则将下一客户事件传入到事件表。
然后再判断传入后队列长度是否为1，如果为1，则当前事件为唯一事件，将当前事件的服务时间加上到达时间，作为离开事件传入到事件表，代表在某某时间某一窗口会有客户离开
还有一种可能是不为-1，则代表遇到离开事件，需要从对应的队列中删除该事件结点，然后判断删除后的队列剩余结点是否唯一，如果唯一，则计算出该结点的离开事件插入到事件表中
其实这算法最核心的操作就是通过事件表摘除结点放入指定的队列，但难点就是：到达时间，服务时间，离开事件，下一个到达时间，事件类型的理解，通过教程可以理解透彻！
运行结果：
我们假设服务时间不能超过30分钟，而间隔时间不能超过十分钟，在银行下班四十分钟前不再接待客户，则：
完整算法如下：更易理解所以未修改，代码整洁之道不能忘记，但是此算法需要考虑的因素相对来说过多，所以我没有删掉输出语句，也没有整理函数的参数，更加易于自己的理解，和以后的复习：
#define COLSE_MAX 40
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int OccurTime;//事件发生时刻;
int NType;//事件类型，-1代表新事件，0到3代表离开事件
}Event,ElemType;//事件类型，有序链表LinkList的数据元素类型
typedef struct
{
int ArrivlTime;//到达时刻
int Duration;//办理事务所需时间
}QElemType;//队列数据元素类型
typedef struct Node
{
ElemType data;
struct Node* next;
}LNode, * LinkList;
LinkList head, node;
typedef struct evNode
{
QElemType data;
struct evNode* next;
}evLNode, * evLinkList;
typedef struct evArr
{
evLinkList head;
}evArr;
evArr ev[4];
int InitLinkList(LinkList *L)
{
*L = (LinkList)malloc(sizeof(LNode));
if (L == NULL)
{
exit(0);
}
(*L)->next = NULL;
}
int InitevArr()
{
for (int i = 0; i < 4; i++)
{
ev[i].head = (evLinkList)malloc(sizeof(evLNode));
ev[i].head->next = NULL;
}
return 0;
}
int InsertLinkList(LinkList *L,ElemType data)
{
LinkList p, s;
p = *L;
s = (*L)->next;
node = (LinkList)malloc(sizeof(LNode));
node->data.NType = data.NType;
node->data.OccurTime = data.OccurTime;
node->next = NULL;
if (p == NULL)
{
p->next = node;
}
else
{
while (s != NULL)
{
if (s->data.OccurTime > node->data.OccurTime)
{
break;
}
p = s;
s = s->next;
}
}
node->next = s;
p->next = node;
}
void DeleteLinkList(LinkList *L, ElemType* data)
{
LinkList p;
p = (*L)->next;
(*L)->next = p->next;
data->NType = p->data.NType;
data->OccurTime = p->data.OccurTime;
free(p);
}
void InQueeArr(int i, QElemType data)
{
struct evNode* node;
evLinkList p = ev[i].head;
node = (evLinkList)malloc(sizeof(LNode));
node->data.ArrivlTime = data.ArrivlTime;
node->data.Duration = data.Duration;
node->next = NULL;
while (p->next != NULL)
{
p = p->next;
}
p->next = node;
}
void OutQueArr(int i, QElemType* data)
{
struct evNode* temp = ev[i].head->next;
ev[i].head->next = temp->next;
data->ArrivlTime = temp->data.ArrivlTime;
data->Duration = temp->data.Duration;
free(temp);
}
int QueueLength(int i)
{
int count = 0;
evLinkList p;
p = ev[i].head->next;
while (p != NULL)
{
p = p->next;
count++;
}
return count;
}
int MinEvArr(evArr Arr[])
{
int a, b, c, d;
a = QueueLength(0);
b = QueueLength(1);
c = QueueLength(2);
d = QueueLength(3);
printf("排队人数：%d,%d,%d,%d\n", a, b, c, d);
if (a <= b)
{
if (a <= c)
{
if (a <= d)
{
return 0;
}
}
}
if (b <= a)
{
if (b <= c)
{
if (b <= d)
{
return 1;
}
}
}
if (c <= a)
{
if (c <= b)
{
if (c <= d)
{
return 2;
}
}
}
if (d <= a)
{
if (d <= b)
{
if (d <= c)
{
return 3;
}
}
}
}
void visit()
{
LinkList p = head->next;
printf("事件表：\n");
while (p != NULL)
{
printf("%d,%d\n", p->data.OccurTime, p->data.NType);
p = p->next;
}
evLinkList e;
for (int i = 0; i < 4; i++)
{
printf("第%d窗口：", i);
e = ev[i].head->next;
while (e != NULL)
{
printf("%d,%d ",e->data.ArrivlTime, e->data.Duration);
e = e->next;
}
printf("\n");
}
printf("\n");
}
int main()//Bank_Simulation()
{
InitLinkList(&head);
InitevArr();
ElemType temp;
QElemType temp2;
int totalTime = 0, totalnum = 0;
temp.NType = -1;//到达类型，初始化
temp.OccurTime = 0;//到达时间
InsertLinkList(&head, temp);
while (head->next != NULL)
{
DeleteLinkList(&head, &temp);
if (temp.NType == -1)
{
totalnum++;
printf("为新客户,此时人数：%d\n", totalnum);
int Min = MinEvArr(ev);
int x = rand()%30;
int y = rand()%10;
printf("当前客户服务时间：%d,下一客户间隔时间：%d\n", x, y);
temp2.ArrivlTime = temp.OccurTime;
temp2.Duration = x;
if (temp.OccurTime + y < COLSE_MAX)
{
temp.OccurTime = temp.OccurTime + y;
temp.NType = -1;
InsertLinkList(&head, temp);
}
printf("传入参数为：%d,%d\n", temp2.ArrivlTime, temp2.Duration);
InQueeArr(Min, temp2);
if (QueueLength(Min) <= 1)
{
temp.NType = Min;
temp.OccurTime = temp2.Duration + temp2.ArrivlTime;
InsertLinkList(&head, temp);
}
visit();
}
else
{
printf("老客户离开%d窗口\n", temp.NType);
OutQueArr(temp.NType, &temp2);
totalTime += temp2.Duration;
if (ev[temp.NType].head->next != NULL)
{
temp.OccurTime = ev[temp.NType].head->next->data.Duration;
InsertLinkList(&head, temp);
}
}
printf("\n\n");
}
printf("接待总人数为：%d,总营业时间为：%d", totalnum, totalTime);
printf("平均逗留时间为：%.2lf分钟", totalTime*1.0 / totalnum);
system("pause");
return 0;
}