数据结构队列离散事件模拟银行排队问题

【数据结构】队列离散事件模拟银行排队问题

1.问题介绍

假设银行有四个窗口对外接待客户，从早晨开门起不断有客户进入
银行每个窗口每个时刻只能接待一个客户，因此人数过多时需在每个窗口进行排队
现在编制一个程序模型银行的业务活动，并计算一天中客户在银行逗留平均时间

2.问题分析

该问题可以分为几个事件，1.客户到达事件 2.客户离开事件（四个窗口）
按事件发生的先后顺序进行处理
所有的事件可以使用一个有序链表存储，事件的插入按发生时间进行排序
四个窗口中排队可以用四个队列表示

3.基本思路

各种类型的定义

客户：客户是队列中的数据元素，包括到达时间，办理业务所需时间
事件：事件是有序链表中的数据元素，包括事件发生时间事件类型（到达事件，四个窗口离开事件）

事件的定义：

到达事件：每次客户到达产生两个随机数，一个表示该客户需要办理业务的时间，另一个表示下一个客户达到的间隔时间
假设第一个客户到达的时间是0，这样便实现了客户的不间断到达。
客户达到后需要找到最短的队列，然后将该客户的到达时间和处理时间插入队列
如果该队列的长度为1，设定一个离开事件并插入事件表

离开事件：
首先确定客户离开的是哪一个队列，删除其队头元素
计算客户逗留时间
如果该队列非空，设定下一个离开事件并插入事件表

模拟结果：

设定每个客户逗留时间不超过三十分钟，两个客户到达时间相隔不超过八分钟，设置营业时间为600分钟，运行结果如下：
平均逗留时间为27.1173分钟。
数据结构队列离散事件模拟银行排队问题

上述为书本中的基本思路，但与实际情况肯定有较大出入，一个明显的问题是：没有更换队列的操作，
倘若某一队列中的人处理事务时间较短，则会造成某个时间一个队列为空，其余队列有两人以上在排队的情况，这在现实中显然是难以发生的
解决方法是在离开事件中加入判断，倘若该队列为空且其余队列有两人以上排队，进行更换队列操作。
更换队列：
1.找到需要更换的客户所在队列
2.将客户转移到空队列
3.设定该队列的一个离开事件

优化后模拟结果

使用同样参数，运行优化后程序，客户平均逗留时间为23.61分钟，有较大提升，且与实际预测情况一致
附加部分代码博客最后。
数据结构队列离散事件模拟银行排队问题

核心代码：

初始化

void OpenForDay() {
	//初始化操作
	TotalTime = 0; CustomerNum = 0;   //初始化累计事4件和客户数为 0
	InitList(ev);					  //初始事件链表为空表
	en.OccurTime = 0; en.NType = 0;	  //设定第一个客户到达事件
	ListInsert_L(ev, 1, en);		  //插入事件表
	for (int  i = 1; i <= 4; i++)
	{
		InitQueue(q[i]);			  //初始化队列
	}
}//OpenForDay

客户到达事件：

void CustomerArrived() {
	//处理客户到达事件 en.Type = 0.
	++CustomerNum;
	int durtime, intertime;
	durtime = rand() % 30;		//客户处理事务时间
	intertime = rand() % 8;		//下一个客户到达事件间隔
	int t = en.OccurTime + intertime;  //下一个客户到达时刻
	if (t < CloseTime)
		OrderInsert(ev, { t,0 }, cmp);
	int i = Minmum(q);					//找到最短队列
	EnQueue(q[i], { en.OccurTime, durtime });	//客户进入队列i
	if (QueueLenth(q[i]) == 1)
		OrderInsert(ev,{en.OccurTime + durtime, i}, cmp); //队列长度为1时，设定一个离开事件
}//CustomerArrived

客户离开事件

void CustomerDeparture() {
	//处理客户离开事件,en.NTpye>0
	QElemType customer ;
	int i = en.NType;
	DeQueue(q[i], customer);  //删除第i队列的排头客户
	TotalTime += en.OccurTime - customer.ArrivaTime;//累计客户逗留时间
	if (!QueueEmpty(q[i])) {
		GetHead(q[i], customer);
		OrderInsert(ev, { en.OccurTime + customer.Duration,i }, cmp);//设定第i队列的离开事件
	}
}//CustomerDeparture

模拟过程

void Bank_Simulation() {
	OpenForDay();
	while (!ListEmpty(ev)) {
		Link p;
		DelFirst(GetHead(ev), p); en = GetCurElem(p);
		if (en.NType == 0) {
			CustomerArrived();			//处理客户到达事件
			cout << p->data.OccurTime << " 有客户到达" << endl;

		}
		else {
			CustomerDeparture();
			cout << p->data.OccurTime << " 有客户离开" << endl;
		}		//处理客户离开事件
	}
	cout << (float)TotalTime / CustomerNum;
}//Bank_Simulation

其余代码

LinkQueue代码见队列的基本操作
只需修改 QElemType 数据类型

typedef struct {
	int ArrivaTime;		//到达时刻
	int Duration;		//办理事务所需要时间
}QElemType;				//队列的数据元素类型

其他函数

#pragma once
#include"..\..\Project1\Project1\LinkQueue.h"
#include"C:\Users\lwww\source\repos\线性链表\线性链表\List.h"

//基本结构体定义

typedef LinkList EvenList ;//事件链表类型，定义为有序链表

//主要变量
EvenList ev;	 //事件表
Event	en;		 //事件
LinkQueue q[5];  //四个客户队列
int TotalTime, CustomerNum; //累计客户逗留时间，客户数
int CloseTime = 600;
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 OrderInsert(EvenList ev, Event en, int (*cmp)(Event a,Event b)) {
	//定义事件插入操作，按发生时间非递减排序
	Link w;
	w = ev.head;
	int i = 1;
	while (w->next&&cmp(en, w->next->data) > 0) {
		w = w->next;
		i++;
	}
	ListInsert_L(ev, i, en);
}
int Minmum(LinkQueue q[5]) {
	int minlenth = QueueLenth(q[1]);
	int i=1;
	for (int j = 2; j < 5; j++)
	{	
		if (minlenth == 0) return i;
		if (minlenth > QueueLenth(q[j])) {
			minlenth = QueueLenth(q[j]);
			i = j;
		}
	}
	return i;
}

List.h

该代码依照书P37页写成，有很多函数在此处用不到。
代码可能存在一些问题，因为书中一些函数的定义本身有问题，主要是关于头尾指针的问题，修改后该程序可以正常运行（修改了很多次）

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define TRUE	1
#define FALSE	0
#define	OK		1
#define ERROR	0
#define	INFEASLBLE	-1
typedef int Status;

typedef struct {
	int OccurTime;  //事件发生时刻
	int NType;		//事件类型，0表示到达事件，1-4表示4个窗口的离开事件

}Event, ElemType;	//事件类型，有序链表LinkList的数据元素类型

typedef struct LNode {
	//结点类型
	ElemType	data;
	struct  LNode *next;
}*Link, *Position;

typedef	struct {
	//链表类型
	Link head, tail;	//头结点和末尾节点
	int len;//指示线性链表中元素个数
}LinkList;

//分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR
Status MakeNode(Link &p, ElemType e);
//释放p所指结点
void FreeNode(Link &p);
//构造一个空的线性表L
Status  InitList(LinkList &L);
//销毁线性表L，L不再存在
Status	DestroyList(LinkList &L);
//将线性表L置空，并释放原链表的结点空间
Status  ClearList(LinkList &L);
//已知h指向线性表的头结点，将s所指结点插入在第一个结点之前			//无法修改len
Status	InsFirst(Link h, Link s);
// 已知h指向线性表的头结点，删除链表中第一个元素并用结点q返回        //无法修改len
Status	DelFirst(Link h, Link &q);
//将指针s所指的一串结点链接在线性表L的最后一个结点；并改变链表L的尾指针指向新的尾结点
Status	 Append(LinkList &L, Link s);
//删除线性链表L中的尾结点并以q返回，改变链表中尾结点
Status	Remove(LinkList &L, Link &q);
//已知p指向线性链表中的一个结点，将s所指结点插入在p所指结点之前，修改指针p指向新的插入点
Status	InsBefore(LinkList &L, Link &p, Link s);
// 已知p指向线性链表中的一个结点，将s所指结点插入在p所指结点之后，修改指针p指向新的插入点
Status  InsAfter(LinkList &L, Link &p, Link s);
//已知p指向线性链表中的一个结点，用e更新p所指结点中元素的值
Status  SetCurElem(Link &p, ElemType e);
//已知p指向线性链表中的一个结点，返回p所指结点中元素的值
ElemType GetCurElem(Link p);
//若线性链表为空表，则返回TRUE,否则返回FALSE
Status	ListEmpty(LinkList L);
//返回链表中元素个数
int ListLenth(LinkList L);
//返回线性链表L中头结点的位置
Position GetHead(LinkList L);
//返回线性链表中最后一个结点的位置；
Position Getlast(LinkList L);
//返回P所指结点的直接前驱
Position PriorPos(LinkList L, Link p);
//返回P所指结点的直接后继
Position NextPos(LinkList L, Link p);
//返回p指示链表中第i个结点的位置
Status LocatePos(LinkList L, int i, Link &p);
//返回线性链表中第一个与e满足函数关系compare的元素位置
Position LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType));
//依次对L中每个元素调用函数visit（）
Status ListTraverse(LinkList L, Status(*visit)(Link));
//在i处插入值为e的元素
Status ListInsert_L(LinkList &L, int i, ElemType e);

List.c

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include"List.h"

using namespace std;
Status MakeNode(Link &p, ElemType e) {
	
	p = (Link)malloc(sizeof(LNode));
	
	if (!p)	return ERROR;
	p->data = e;
	p->next = NULL;
	return OK;
}

void FreeNode(Link &p) {
	free(p);
}

Status  InitList(LinkList &L) {
	
	L.head = (Link)malloc(sizeof(LNode));
	L.tail = (Link)malloc(sizeof(LNode));
	if (!L.head || !L.tail)return ERROR;
	L.len = 0;
	L.tail = L.head;
	L.head->next = NULL;

	//L.tail->next = L.head;
	return OK;
}

Status	DestroyList(LinkList &L) {
	Link p;
	
	while(L.head->next){
		p = L.head->next;
		free(L.head);
		L.head = p;
	}
	L.len = 0;
	free(L.head);
	free(L.tail);
	return OK;
}

Status  ClearList(LinkList &L) {
	Link p;
	p = L.head->next;
	Link q;
	while (p) {
		q = p->next;
		free(p);
		p = q;
	}
	L.head->next = L.tail;
	L.len = 0;
	
	return OK;
}

Status	InsFirst(Link h, Link s) {
	Link p;
	p = h->next;
	h->next = s;
	s->next = p;
	return OK;

}

Status	DelFirst(Link h, Link &q) {
	
	Link p;
	p = (Link)malloc(sizeof(LNode));
	if (!h->next)return ERROR;
	p = h->next;
	q = p;
	h->next = p->next;
	
	//free(p);
	return	OK;
}

Status	 Append(LinkList &L, Link s) {
	if (!s)
	{
		return ERROR;
	}

	Link p;
	p = L.tail;	//p为末尾结点

	p->next = s;		//将q串入L
	int j = 1;
	while (s->next) {
		s = s->next;
		j++;
	}
	L.tail = s;	//改变尾指针
	L.len += j;			//修改表长
	return OK;
}

Status	Remove(LinkList &L, Link &q) {
	if (!L.tail) {
		return ERROR;
	}
	Link p;
	p = L.head;
	q = L.tail;
	
	while (p->next->next) {
		p = p->next;
	}
	L.tail = p; //修改尾指针
	p->next = NULL;
	L.len--;
	return OK;

}

Status	InsBefore(LinkList &L, Link &p, Link s) {
	//已知p指向线性链表中的一个结点，将s所指结点插入在p所指结点之前，修改指针p指向新的插入点
	Link q;
	q = L.head;
	while (!(q->next==p)) {
		if (!q->next)return ERROR;
		q = q->next;
	}
	q->next = s;
	s->next = p;
	p = s;
	L.len++;
	return OK;
}

Status  InsAfter(LinkList &L, Link &p, Link s) {

	Link q;
	q = (Link)malloc(sizeof(LNode));
	if (p->next) {		//P不指向最后一个结点
		q = p->next;
		s->next = q;
		p->next = s;
		
	}
	else {				//p指向最后一个结点
		p->next = s;
		L.tail = s;  //尾指针指向s
	}
	free(q);
	L.len++;
	return OK;
}

Status  SetCurElem(Link &p, ElemType e) {
	if (!p)return ERROR;
	p->data = e;
	return OK;
}

ElemType GetCurElem(Link p) {
	return p->data;
}

Status	ListEmpty(LinkList L){
	if (!L.head->next)return TRUE;
	return FALSE;
}

int ListLenth(LinkList L) {
	return L.len;
}

Position GetHead(LinkList L) {
	return L.head;
}

Position Getlast(LinkList L) {
	return L.tail;
}

Status LocatePos(LinkList L, int i, Link &p) {
	Link q;
	q = L.head;
	int j = 0;
	while (j < i&&q) {
		q = q->next;
		j++;
	}
	if (j > i || !q)	return ERROR;
	p = q;
	return OK;
}

Position PriorPos(LinkList L, Link p) {
	Link q;
	q = L.head;
	if (p == q->next) return ERROR; 
	while (!(q->next == p)) {
		q = q->next;
	}
	return q;

}

Position NextPos(LinkList L, Link p) {
	if (!p->next)return ERROR;
	return p->next;
}

Position LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) {
	Link p;
	p = L.head->next;
	while (!compare(p->data, e)) {
		p = p->next;
		if (!p)return ERROR;
	}
	return p;

}

Status ListTraverse(LinkList L, Status(*visit)(Link)) {
	Link p;
	p = L.head->next;
	int j = 0;

	while (p) {
		
		if (!visit(p))return ERROR;
		p = p->next;
	}
	return OK;
}

Status visit(Link p) {
	return OK;
}

Status ListInsert_L(LinkList &L, int i, ElemType e) {
	Link h;
	Link s;
	h = (Link)malloc(sizeof(LNode));
	if (!LocatePos(L, i - 1, h))return ERROR;
	if (!MakeNode(s, e)) return ERROR;
	InsFirst(h, s);				
	L.len++;
	return OK;
}

优化模型的附加代码：

1.在LinkQueue中增加一个删除队尾元素操作

Status DerearQueue(LinkQueue &Q, QElemType &e) {
	//若队列不空，删除Q的队尾元素，用e返回其值，并返回OK
	if (Q.front == Q.rear)return ERROR;
	QueuePtr p;
	p = Q.front;
	while (!(p->next == Q.rear))p = p->next;
	e = Q.rear->data;
	free(Q.rear);
	Q.rear = p;
}

2.增加一个寻找最大长度队列函数

若最大长度小于2，返回0,此时不需要插队操作

int Maxmum(LinkQueue q[5]) {
	int maxlenth = QueueLenth(q[1]);
	int i = 1;
	for (int j = 2; j < 5; j++)
	{
		if (maxlenth < QueueLenth(q[j])) {
			maxlenth = QueueLenth(q[j]);
			i = j;
		}
	}
	if (maxlenth >= 2)
		return i;
	else return 0;
}

3.修改客户离开操作，增加更换队列操作

void CustomerDeparture() {
	//处理客户离开事件,en.NTpye>0
	QElemType customer ;
	int i = en.NType;
	DeQueue(q[i], customer);  //删除第i队列的排头客户
	TotalTime += en.OccurTime - customer.ArrivaTime;//累计客户逗留时间
	if (!QueueEmpty(q[i])) {
		GetHead(q[i], customer);
		OrderInsert(ev, { en.OccurTime + customer.Duration,i }, cmp);//设定第i队列的离开事件
	}
	else{
	//如果离开后该队列为空，判断是否进行换队列操作
		int k = Maxmum(q);
		if (k>0) {
			//K>0,则进行换队列操作
			DerearQueue(q[k], customer);
			EnQueue(q[i], customer);
			OrderInsert(ev, { en.OccurTime + customer.Duration, i }, cmp); //更换队伍后插入一个离开事件
		}
	}
}//CustomerDeparture

数据结构队列 离散事件模拟 银行排队问题