数据结构银行排队问题

实验任务

银行排队模拟程序功能
假设某银行有四个窗口对外接待客户,从早晨银行开门起不断有客户进入银行。由于每个窗口只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正在空闲，则可上前办理业务，反之，若四个窗口均有客户所占,他便会排在队伍的后面。现在需要编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。

前期准备工作

  • 链式队列书写完毕
  • 带头结点单向不循环链表按顺序插入节点已掌握

算法大致思路

1.2个重要的数据结构

  • 事件链表
  • 队列数组

image-20210530102000635

2.某个时刻运行状态

image-20210530102113272

解释如下：

  • 事件链表

    • occurTime :表示事件发生时间
    • ntype:表示事件类型，-1表示新客户到达，0-3表示0-3号窗口老客户离开时间

  • 队列数组：

    由四个队列对象组成

    对每个队列对象：

    • arrivalTime: 表示当前客户到达时间
    • duration：表示当前客户办理业务时间

3.2个重要的数据结构代码

  • 队列数组
#define datatype Client
//银行客户，队列节点的data域
typedef struct Client
{
	int arrivalTime;//当前客户到达时间
	int duration;//当前客户的服务时间
}Client;
//队列节点
typedef struct Node
{
	Clinet data;
	struct Node *next;
}Node;
//使用带头结点单链表来做，队列类
class LinkQueue
{
private:
	Node *rear, *front;
	int length;//队列中的元素个数
public:
	LinkQueue();
	~LinkQueue();
	bool getFront(datatype *item);
	void enQueue(datatype item);
	bool deQueue(datatype *item);
	bool isEmpty();
	void clearQueue();
	void displayQueue();
	int queueLength();
};
  • 事件链表
typedef struct evNode
{
	int occurTime;//事件发生时间
	int nType;//事件类型，-1表示到达事件，0-3表示0-3窗口离开事件
	struct evNode *next;
}evNode;
class EvList
{
private:
	evNode *head;
public:
	LinkList();
	~LinkList();
	bool insertNode(int occurTime,int nType);//按顺序插入
	bool deleteNode(int *occurTime,int *nType);//首部删除
	void displayNode();
	bool isEmpty();
};

4.运行流程模拟

image-20210530105052553

image-20210530105145652

image-20210530105209745

image-20210530105242810

image-20210530105303345

image-20210530105342301

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

5.结束条件

img

img

6.个人总结

  • 初始化事件链表

  • 判断事件链表是否为空

  • 若事件链表为空则表示所有事件已经处理完毕可以结束循环

  • 事件链表不为空，则进入主循环

    • 删除事件链表中的第一个节点，将第一个节点中的数据导入到evItem中，

    • 判断evItem中的事件类型，nType = -1表示新用户到达，nType>=0&&nType<=3表示老客户离开

    • nType = -1，新客户到达，customerNum++：

      • 生成两个随机数，分别表示当前客户接受服务的时间duration与下一个客户的间隔时间interTime
      • 判断一下，下一个客户是否在银行关门前到达，若在银行关门前到达则做两件事情（1.处理下一个客户2.处理当前客户），若在银行关门后到达则只做一件事情（处理当前用户）；
      • 处理下一个客户事件：计算下一个客户到达时间（下一个客户到达时间=当前客户到达时间+下一个客户间隔时间）
      • 处理当前客户事件：1.将当前客户的状态信息记录到人数最少的队列中（arrivalTime,duration),2.判断一下该队列中是否只有一个节点，若是，则将当前客户离开事件加入到事件链表（occurTime = arrivalTime + duration,ntype=队列编号)，原因：很简单银行前台一次只能为一名客户提供服务，若为队列中的第二个元素，则不插入事件链表，等着。

    • nType>=0&&nType<=3，老客户离开

      • 删除nType所对应的队列的队首节点，若队列中还有其他节点，则删除节点的下一个节点所对应的客户离开事件加入事件链表
      • 具体来说：
      • 找到离开客户的编号，等于evItem.nType
      • 客户离开，办完业务，删除队列节点，返回客户信息，用于计算总的服务时间
      • 该队列中/该窗口还有其他客户，则下一个客户离开事件加入事件链表

实验代码

bank.h

#ifndef LINKQUEUE_H__
#define LINKQUEUE_H__
#define datatype Client
#define evdatatype EventStruct
const int CLOSE_TIME = 40;//银行关门时间
const int MAX_INTERTIME =10 ;//相邻两个客户最大间隔时间
const int MAX_DURATION =30 ;//每位客户最大服务时间
//银行客户，队列节点的data域
typedef struct Client
{
	int arrivalTime;//当前客户到达时间
	int duration;//当前客户的服务时间
}Client;
//队列节点
typedef struct Node
{
	datatype data;
	struct Node *next;
}Node;
//使用带头结点单链表来做，队列类
class LinkQueue
{
private:
	Node *rear, *front;
	int length;//队列中的元素个数
public:
	LinkQueue();
	~LinkQueue();
	bool getFront(datatype *item);
	void enQueue(datatype item);
	bool deQueue(datatype *item);
	bool isEmpty();
	void clearQueue();
	void displayQueue();
	int queueLength();
};
struct EventStruct
{
	int occurTime;//事件发生时间
	int nType;//事件类型，-1表示到达事件，0-3表示0-3窗口离开事件
};
typedef struct evNode
{
	evdatatype data;
	struct evNode *next;
}evNode;
class LinkList
{
private:
	evNode *head;
public:
	LinkList();
	~LinkList();
	bool insertNode(evdatatype elem);//按顺序插入
	bool deleteNode(evdatatype *elem);//首部删除
	void displayNode();
	bool isEmpty();
};
double simulation(LinkList &evList, LinkQueue queueArr[], int size);
#endif

bank.cpp

#include<iostream>
using namespace std;
#include "LinkQueue.h"
#include<time.h>
#include<stdlib.h>
LinkQueue::LinkQueue()
{
	front = new Node;
	front->next = NULL;
	rear = front;
	length = 0;
}
LinkQueue::~LinkQueue()
{
	Node *p, *q;
	for (p = front->next; p != NULL; p = q)
	{
		q = p->next;
		delete p;
	}
	delete front;
	front = NULL;
	length = 0;
}

bool LinkQueue::getFront(datatype *item)
{
	if (isEmpty())
	{
		return false;
	}
	else
	{
		Node *p;
		p = front->next;
		*item = p->data;
		return true;
	}
}
void LinkQueue::enQueue(datatype item)
{
	Node *p = new Node;
	p->data = item;
	p->next = NULL;
	rear->next = p;
	rear = p;
	length++;
}
bool LinkQueue::deQueue(datatype *item)
{
	if (isEmpty())
	{
		return false;
	}
	else
	{
		Node *p = front->next;
		if (p->next == NULL)//队列中只有一个元素
		{
			rear = front;
		}
		front->next = p->next;
		*item = p->data;
		delete p;
		length--;
		return true;
	}
}
bool LinkQueue::isEmpty()
{
	if (front == rear)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void LinkQueue::clearQueue()
{
	Node *p, *q;
	for (p = front->next; p != NULL; p = q)
	{
		q = p->next;
		delete p;
	}
	front->next = NULL;
	length = 0;
	rear = front;
}
void LinkQueue::displayQueue()
{
	Node *p;
	
	for (p = front->next; p != NULL; p = p->next)
	{
		
		printf("[%d,%d]->",(p->data).arrivalTime,(p->data).duration);
	}
}
int LinkQueue::queueLength()
{
	return length;
}

LinkList::LinkList()
{
	head = new evNode;
	head->next = NULL;
}
LinkList::~LinkList()
{
	evNode *p, *q;
	for (p = head->next; p != NULL; p = q)
	{
		q = p->next;
		delete p;
	}
	delete head;
	head = NULL;
}
bool LinkList::insertNode(evdatatype elem)//按顺序插入
{
	evNode *p = head->next; 
	evNode *pre_p=head;
	//找到插入位置
	while (p)
	{	
		if ((p->data).occurTime > elem.occurTime)
		{
			break;
		}
		pre_p = p;
		p = p->next;
		
	}
	evNode *newNode = new evNode;
	newNode->data = elem;
	pre_p->next = newNode;
	newNode->next = p;
	return true;
}
bool LinkList::deleteNode(evdatatype *elem)//首部删除
{
	if (isEmpty())
	{
		return false;
	}
	else
	{
		evNode *p = head->next;
		head->next = p->next;
		*elem = p->data;
		delete p;
		return true;
	}
}
bool LinkList::isEmpty()
{
	if (head->next == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void LinkList::displayNode()
{
	evNode *p;
	for (p = head->next; p != NULL; p = p->next)
	{
		cout <<"[" <<(p->data).occurTime << "，" << (p->data).nType <<"]->";
	}
}
int findMin(LinkQueue queueArr[4], int size)
{
	int flag = 0;//假设下标为0的队列人数最少
	for (int i = 1; i < size; i++)
	{
		if (queueArr[i].queueLength() < queueArr[flag].queueLength())
		{
			flag = i;
		}
	}
	return flag;
}


double simulation(LinkList &evList, LinkQueue queueArr[4], int size)
{
	srand((unsigned)time(NULL));
	//customerNum表示客户数量，totalTime表示总的客户服务时间
	int customerNum = 0, interTime, duration, totalTime = 0;
	Client item;
	EventStruct evTemp, evItem;
	//初始化事件链表, 第一个新客户到达
	evTemp.occurTime = 0;
	evTemp.nType = -1;
	evList.insertNode(evTemp);
	int cnt = 1;
	//事件链表非空则执行循环,说明还有事情没有处理完毕
	while (!evList.isEmpty())
	{
		printf("---------------第%d次循环----------------------------\n", cnt);
		cnt++;
		evList.deleteNode(&evItem);//删除事件链表中第一个节点，将数据拷贝到evItem中
		printf("删除事件链表中第一个结点存入evItem中:%d,%d\n", evItem.occurTime, evItem.nType);

		if (evItem.nType == -1)//判断事件类型，-1表示新客户到达
		{
			//生成两个随机数，interTime表示下一个客户间隔时间
			//duration表示当前客户接收服务的时间
			interTime = rand() % MAX_INTERTIME+1;
			duration = rand() % MAX_DURATION+1;
			customerNum++;//客户数量自增
			printf("是新客户到达事件,请输入durTime,interTime:%d\t%d\n", duration, interTime);
			if (interTime + evItem.occurTime < CLOSE_TIME)//客户在银行关门后到达，银行不提供服务
			{
				//做两件事情
				//1.处理新客户
				evTemp.occurTime = evItem.occurTime + interTime;//下一个客户到达时间
				evTemp.nType = -1;
				evList.insertNode(evTemp);//新客户加入事件链表
				printf("把下一位客户到达的事件插入事件表\n");
				printf("显示事件%d\t%d\n", evTemp.occurTime, evTemp.nType);
			}
			//2.处理当前用户,其余只做一件事处理当前用户
			int min_flag = findMin(queueArr, 4);
			item.arrivalTime = evItem.occurTime;//将当前客户的状态信息添加到人数最少的队列中
			item.duration = duration;
			queueArr[min_flag].enQueue(item);
			printf("新客户进入人数最少的队列:queue[%d] [%d,%d]\n", min_flag, item.arrivalTime, duration);
			printf("queue[%d]队列数组中的元素依次为\n", min_flag);
			queueArr[min_flag].displayQueue();
			printf("\n");
			//判断该客户是否为队列中的第一个元素
			//是，则加入事件链表
			if (queueArr[min_flag].queueLength() == 1)
			{
				evTemp.occurTime = item.arrivalTime + item.duration;//计算当前客户离开时间
				evTemp.nType = min_flag;
				evList.insertNode(evTemp);
				printf("设定客户离开银行的事件，插入事件表\n");
			}
			printf("打印事件链表:\n");
			evList.displayNode();
			printf("\n");
		}
		else if (evItem.nType >= 0 && evItem.nType <= 3)//老客户离开
		{
			//1.删除ntype对应队列中的队首节点
			//获取客户所在窗口的编号
			int index = evItem.nType;
			printf("queue[%d]队列数组中的元素依次为\n", index);
			queueArr[index].displayQueue();
			printf("\n");
			//当前客户即将离开，从队列中删除,返回用户状态信息
			queueArr[index].deQueue(&item);
			printf("queue[%d]中第一个用户离开,用户信息为arrivlaTime=%d,duration=%d\n",
				index, item.arrivalTime, item.duration);
			totalTime += item.duration;
			
			if (queueArr[index].queueLength() > 0)//如果该对列中还有客户在排队，则下一个客户离开事件加入事件链表
			{
				queueArr[index].getFront(&item);
				evTemp.occurTime = item.duration + evItem.occurTime;//下一个客户离开时间=当前客户离开时间+下一个客户接受服务的时间
				evTemp.nType = index;
				evList.insertNode(evTemp);
			}
			printf("打印事件链表:\n");
			evList.displayNode();
			printf("\n");
		}

		
	}
	return totalTime * 1.0 / customerNum;
}

test.cpp

#include<iostream>
using namespace std;
#include "LinkQueue.h"
int main()
{
	LinkList evList;
	LinkQueue queueArr[4];
	int size = 4;
	double avgTime = 0;
	avgTime = simulation(evList, queueArr, size);
	cout << avgTime << endl;
	
	
	return 0;
}

运行结果

---------------第1次循环----------------------------
删除事件链表中第一个结点存入evItem中:0,-1
是新客户到达事件,请输入durTime,interTime:20     4
把下一位客户到达的事件插入事件表
显示事件4       -1
新客户进入人数最少的队列:queue[0] [0,20]
queue[0]队列数组中的元素依次为
[0,20]->
设定客户离开银行的事件，插入事件表
打印事件链表:
[4，-1]->[20，0]->
---------------第2次循环----------------------------
删除事件链表中第一个结点存入evItem中:4,-1
是新客户到达事件,请输入durTime,interTime:14     7
把下一位客户到达的事件插入事件表
显示事件11      -1
新客户进入人数最少的队列:queue[1] [4,14]
queue[1]队列数组中的元素依次为
[4,14]->
设定客户离开银行的事件，插入事件表
打印事件链表:
[11，-1]->[18，1]->[20，0]->
---------------第3次循环----------------------------
删除事件链表中第一个结点存入evItem中:11,-1
是新客户到达事件,请输入durTime,interTime:10     1
把下一位客户到达的事件插入事件表
显示事件12      -1
新客户进入人数最少的队列:queue[2] [11,10]
queue[2]队列数组中的元素依次为
[11,10]->
设定客户离开银行的事件，插入事件表
打印事件链表:
[12，-1]->[18，1]->[20，0]->[21，2]->
---------------第4次循环----------------------------
删除事件链表中第一个结点存入evItem中:12,-1
是新客户到达事件,请输入durTime,interTime:2      4
把下一位客户到达的事件插入事件表
显示事件16      -1
新客户进入人数最少的队列:queue[3] [12,2]
queue[3]队列数组中的元素依次为
[12,2]->
设定客户离开银行的事件，插入事件表
打印事件链表:
[14，3]->[16，-1]->[18，1]->[20，0]->[21，2]-> 
---------------第5次循环----------------------------
删除事件链表中第一个结点存入evItem中:14,3
queue[3]队列数组中的元素依次为
[12,2]->
queue[3]中第一个用户离开,用户信息为arrivlaTime=12,duration=2
打印事件链表:
[16，-1]->[18，1]->[20，0]->[21，2]->
---------------第6次循环----------------------------
删除事件链表中第一个结点存入evItem中:16,-1
是新客户到达事件,请输入durTime,interTime:12     7
把下一位客户到达的事件插入事件表
显示事件23      -1
新客户进入人数最少的队列:queue[3] [16,12]
queue[3]队列数组中的元素依次为
[16,12]->
设定客户离开银行的事件，插入事件表
打印事件链表:
[18，1]->[20，0]->[21，2]->[23，-1]->[28，3]->
---------------第7次循环----------------------------
删除事件链表中第一个结点存入evItem中:18,1
queue[1]队列数组中的元素依次为
[4,14]->
queue[1]中第一个用户离开,用户信息为arrivlaTime=4,duration=14
打印事件链表:
[20，0]->[21，2]->[23，-1]->[28，3]->
---------------第8次循环----------------------------
删除事件链表中第一个结点存入evItem中:20,0
queue[0]队列数组中的元素依次为
[0,20]->
queue[0]中第一个用户离开,用户信息为arrivlaTime=0,duration=20
打印事件链表:
[21，2]->[23，-1]->[28，3]->
---------------第9次循环----------------------------
删除事件链表中第一个结点存入evItem中:21,2
queue[2]队列数组中的元素依次为
[11,10]->
queue[2]中第一个用户离开,用户信息为arrivlaTime=11,duration=10
打印事件链表:
[23，-1]->[28，3]->
---------------第10次循环----------------------------
删除事件链表中第一个结点存入evItem中:23,-1
是新客户到达事件,请输入durTime,interTime:22     8
把下一位客户到达的事件插入事件表
显示事件31      -1
新客户进入人数最少的队列:queue[0] [23,22]
queue[0]队列数组中的元素依次为
[23,22]->
设定客户离开银行的事件，插入事件表
打印事件链表:
[28，3]->[31，-1]->[45，0]->
---------------第11次循环----------------------------
删除事件链表中第一个结点存入evItem中:28,3
queue[3]队列数组中的元素依次为
[16,12]->
queue[3]中第一个用户离开,用户信息为arrivlaTime=16,duration=12
打印事件链表:
[31，-1]->[45，0]->
---------------第12次循环----------------------------
删除事件链表中第一个结点存入evItem中:31,-1
是新客户到达事件,请输入durTime,interTime:6      10
新客户进入人数最少的队列:queue[1] [31,6]
queue[1]队列数组中的元素依次为
[31,6]->
设定客户离开银行的事件，插入事件表
打印事件链表:
[37，1]->[45，0]->
---------------第13次循环----------------------------
删除事件链表中第一个结点存入evItem中:37,1
queue[1]队列数组中的元素依次为
[31,6]->
queue[1]中第一个用户离开,用户信息为arrivlaTime=31,duration=6
打印事件链表:
[45，0]->
---------------第14次循环----------------------------
删除事件链表中第一个结点存入evItem中:45,0
queue[0]队列数组中的元素依次为
[23,22]->
queue[0]中第一个用户离开,用户信息为arrivlaTime=23,duration=22
打印事件链表:

12.2857

C:\Users\Administrator\source\repos\Project8\Debug\Project8.exe (进程 13000)已退出，返回代码为: 0。
若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口...

参考链接

b站up主懒猫老师

image-20210603124506010

版权声明：本文为qq_45767476原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。