《数据结构（C语言版）》离散事件模拟之银行业务模拟
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟民 编著
数据结构（C语言版）
以下是本人对该紫皮书第三章栈和队列中3.5节离散事件模拟的银行业务模拟代码实现，整个代码需要用到第二章线性链表的绝大部分函数和第三种链队列的绝大部分函数，是一个综合性很强的问题，有亿点点复杂，本人也是多方借鉴整合并优化弄出来的代码，另外把每一步顾客到了哪个窗口和事件链表打印出来，便于读者理解
事实上，这个银行业务模拟仍有很多地方可以优化，比如课本上就没有考虑到排队时，若到某个窗口办事的客户很快就办理好业务，队伍比较短，这时在旁边排长队的客户会转到短队上
话不多说上运行结果
代码如下：加上注释与换行约350行
（貌似专栏把我缩进吃了，懒得加了，另外建议用visual studio编译）
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef struct
{
int OccurTime;//事件发生时刻
int NType;//事件类型，0表示到达事件，1-4表示四个窗口的离开事件
}Event, ElemType;
typedef struct LNode
{
ElemType data;
struct LNode* next;
}LNode, * LinkList;
typedef LinkList EventList;
typedef struct
{
int ArrivalTime;//到达时刻
int Duration;//办理事务所需事件
}QElemType;
typedef struct QNode
{
QElemType data;
struct QNode* next;
}QNode, * QueuePtr;
typedef struct
{
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;
EventList ev;//事件表
Event en;//事件
LinkQueue q[5];//四个客户队列
QElemType customer;//客户记录
int TotalTime, CustomerNum, CloseTime;
void Bank_Simulation(int CloseTime);//银行业务模拟，统计一天内客户在银行逗留的平均时间
int cmp(Event a, Event b);//比较事件发生先后
void OpenForDay();//银行开门
void OrderInsert(EventList L, Event en, int(*cmp)(Event a, Event b));//插入事件
void CustomerArrived();//客户进门
void CustomerDepature();//客户离开
int Minimum(LinkQueue Q[5]);//求长度最短队列
Status InitList(LinkList& L);//链表初始化
Status ListInsert_L(LinkList& L, int i, ElemType e);//在第i个位置之前插入元素e
Status ListEmpty(LinkList L);//判断链表是否为空
Status DelFirst(LinkList L, LNode*& q);//删除链表中第一个结点并以q返回
LNode* GetHead(LinkList L);//返回链表头结点
ElemType GetCurElem(LNode* p);//已知p指向线性链表中的一个结点，返回p所指结点中元素的值
void PrintEventList();//打印事件链表
Status ListTraverse(LinkList& L);//遍历链表
Status InitQueue(LinkQueue& Q);//链队列的初始化
Status EnQueue(LinkQueue& Q, QElemType e);//入队
Status DeQueue(LinkQueue& Q, QElemType& e);//出队
int QueueLength(LinkQueue Q);//返回队列的长度
Status GetHead(LinkQueue Q, QElemType& e);//获取队头元素 注：由于参数个数不同，发生函数重载
Status QueueEmpty(LinkQueue Q);//判断队列是否为空
void PrintQueue();//打印队列
Status QueueTraverse(LinkQueue Q);//遍历队列Q
/*
系统每次随机生成的是
1）当前顾客顾客的柜台被服务时间
2）当前顾客和下一个顾客到达的间隔时间
记住这2点就便于理解整个代码
每个顾客在银行的等待时间取决于队列里前一个节点的离开时间，而不是自己的到达时间+服务时间。
*/
int main()
{
srand((unsigned)time(NULL));//设定随机数种子
printf("请输入银行的营业时间(min)：");
scanf("%d", &CloseTime);
Bank_Simulation(CloseTime);
return 0;
}
void Bank_Simulation(int CloseTime)//银行业务模拟，统计一天内客户在银行逗留的平均时间
{
OpenForDay();//开始营业
LNode* p;
while (!ListEmpty(ev))
{
DelFirst(GetHead(ev), p);
printf("********action********\n");
en = GetCurElem(p);
if (en.NType == 0)
{
CustomerArrived();
}
else
{
CustomerDepature();
}
PrintQueue();
PrintEventList();
}
printf("The Average Time is %f\n", (float)TotalTime / CustomerNum);
}
int cmp(Event a, Event b)//比较事件发生先后
{
if (a.OccurTime > b.OccurTime) return 1;
if (a.OccurTime = b.OccurTime) return 0;
if (a.OccurTime < b.OccurTime) return -1;
}
void OpenForDay()//银行开门
//初始化操作
{
TotalTime = 0;//初始化累计时间为0
CustomerNum = 0;//初始化客户数为0
InitList(ev);//初始化事件链表为空表
en.OccurTime = 0;
en.NType = 0;//设定第一个客户到达事件
OrderInsert(ev, en, cmp);
for (int i = 1; i <= 4; i++)
{
InitQueue(q[i]);//将四个银行窗口队列初始化
}
}
void OrderInsert(EventList L, Event en, int(*cmp)(Event a, Event b))//插入事件
//事件插入函数，将不同事件按发生时间递增排序
{
LNode* p = L;
int i = 1;
while (p->next && cmp(en, p->next->data) > 0)//找到事件发生时间所在事件链表中的位置
{
p = p->next;
i++;
}
ListInsert_L(ev, i, en);//插入该事件
}
void CustomerArrived()//客户进门
//处理客户到达事件，en.NType=0
{
CustomerNum++;
int durtime = rand() % 30 + 1;//客户处理事务时间
int intertime = rand() % 8;//下一个客户到达的时间间隔
int t = en.OccurTime + intertime;//下一个客户到达的时刻
if (t < CloseTime)//如果他在营业时间内进来
{
printf("一个新客户在银行营业%2dmin后进来，办理业务花费了%2dmin，下一个客户过了%2dmin后进来\n", en.OccurTime, durtime, intertime);
OrderInsert(ev, { t, 0 }, cmp);//插入客户进门事件，NType=0为到达事件
}
int i = Minimum(q);//客户找最短队开始排队
EnQueue(q[i], { en.OccurTime, durtime });
if (QueueLength(q[i]) == 1)
{
OrderInsert(ev, { en.OccurTime + durtime,i }, cmp);//队列长度为1时，设定一个离开事件
}
}
void CustomerDepature()//客户离开
{
int i = en.NType;
DeQueue(q[i], customer);//删除第i队列的排头客户
TotalTime += en.OccurTime - customer.ArrivalTime;//累计客户逗留时间
if (!QueueEmpty(q[i])) {
GetHead(q[i], customer);
OrderInsert(ev, { en.OccurTime + customer.Duration, i }, cmp);//插入事件
}
}
int Minimum(LinkQueue Q[5])//求长度最短队列
{
int minLength = QueueLength(Q[1]);
int i = 1;
for (int j = 2; j < 5; j++)
{
if (minLength > QueueLength(Q[j]))
{
minLength = QueueLength(Q[j]);
i = j;
}
}
return i;
}
Status InitList(LinkList& L)//链表初始化
{
L = (LinkList)malloc(sizeof(LNode));
if (!L)
{
exit(OVERFLOW);
}
L->next = NULL;
return OK;
}
Status ListInsert_L(LinkList& L, int i, ElemType e)//在第i个位置之前插入元素e
{
LinkList p = L;
int j = 0;
while (p && j < i - 1)//注意是i-1,因为要找被插入元素的前一个元素
{
p = p->next;
j++;
}
if (!p || j > i - 1)
{
return ERROR;
}
LinkList s = (LinkList)malloc(sizeof(LNode));
if (!s)
{
exit(OVERFLOW);
}
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
Status ListEmpty(LinkList L)//判断链表是否为空
//空表：头指针和头结点仍然存在，但头结点指向NULL
{
if (L->next)
{
return FALSE;
}
else
{
return TRUE;
}
}
Status DelFirst(LinkList L, LNode*& q)//删除链表中第一个结点并以q返回
{
if (!L->next)
{
return ERROR;
}
q = L->next;
L->next = q->next;
return OK;
}
LNode* GetHead(LinkList L)//返回链表头结点
{
return L;
}
ElemType GetCurElem(LNode* p)//已知p指向线性链表中的一个结点，返回p所指结点中元素的值
{
return p->data;
}
void PrintEventList()//打印事件链表
{
printf("Current Eventlist is:\n");
ListTraverse(ev);
}
Status ListTraverse(LinkList& L) //遍历链表
{
LNode* p = L->next;
if (!p) {
printf("List is empty.\n");
return ERROR;
}
while (p != NULL) {
printf("OccurTime:%d,Event Type:%d\n", p->data.OccurTime, p->data.NType);
p = p->next;
}
printf("\n");
return OK;
}
Status InitQueue(LinkQueue& Q)//链队列的初始化
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q.front)
{
exit(OVERFLOW);
}
Q.front->next = NULL;
return OK;
}
Status EnQueue(LinkQueue& Q, QElemType e)//入队
{
QNode* p = (QueuePtr)malloc(sizeof(QNode));
if (!p)
{
exit(OVERFLOW);
}
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
Status DeQueue(LinkQueue& Q, QElemType& e)//出队
{
if (Q.front == Q.rear)
{
return ERROR;
}
QNode* p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)//注意这里要考虑到,当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对队尾指针重新复制(指向头结点)
{
Q.rear = Q.front;
}
free(p);
return OK;
}
int QueueLength(LinkQueue Q)//返回队列的长度
{
int count = 0;
QNode* p = Q.front->next;
while (p) {
p = p->next;
count++;
}
return count;
}
Status GetHead(LinkQueue Q, QElemType& e)//获取队头元素
{
if (Q.front == Q.rear)
{
return ERROR;
}
e = Q.front->next->data;
}
Status QueueEmpty(LinkQueue Q)//判断队列是否为空
{
if (Q.front == Q.rear)
{
return TRUE;
}
return FALSE;
}
void PrintQueue()//打印队列
{
//打印当前队列
int i;
for (i = 1; i <= 4; i++) {
printf("窗口 %d 有 %d 个客户:", i, QueueLength(q[i]));
QueueTraverse(q[i]);
}
printf("\n");
}
Status QueueTraverse(LinkQueue Q)//遍历队列Q
{
QNode* p = Q.front->next;
if (!p) {
printf("--Is empty.\n");
return ERROR;
}
while (p) {
printf("(到达时刻 %d min 办理业务需要花费 %d min) ", p->data.ArrivalTime, p->data.Duration);
p = p->next;
}
printf("\n");
return OK;
}
