银行排队模拟（离散事件模拟）

1.银行排队模拟程序简介：

2.算法所需要的数据结构和相当解释说明

3.事件算法运行时的某个状态

初始化

生成随机数后要做的事情

LinkQueue.hpp

这里用的是链队列，所以要有一个节点结构体和一个队列类，其次节点的数据域里面存放的是用户结构体类型，所以还要定义一个用户结构体类型

#include<iostream>
using namespace std;
//客户结构体
typedef struct
{
    //用户到达时间
    int arriveTime;
    //用户办理业务需要的时间
    int durTime;
}cilent;

//队列节点类型--这里用的是链式队列
struct node
{
    cilent data;
    node* next;
};

//队列类
class linkQueue {
private:
    node* front, * rear;//指向队列头结点，指向队列尾节点
    int length;  //元素个数
public:
    //这里只需要默认无参构造，不需要有参构造
    linkQueue()
    {
        //在堆区创建一个头结点
        front = rear = new node;
        front->next = NULL;
        rear->next = NULL;
        length = 0;
    }
    ~linkQueue()//释放队列空间
    {
        //头结点为空，就不进行释放
        if (front == NULL)
        {
            return;
        }
        //如果不为空，就先释放除了子节点，再释放头节点
        for (int i = 0; i < length; i++)
        {
            //把每一个开辟在堆区的节点都进行释放，包括头节点
            //相当于销毁链表
           //用一个临时节点保存下一个要删除的节点
            node* temp;
            temp = front;
            front = front->next;
            free(temp);
        }
        length = 0;
    }
    //入队---尾插
    void enlinkQueue(cilent val)
    {
        //不用判断队列是否为满，因为是链式存储
        //头插
        node* s = new node;
        s->data = val;
        s->next = NULL;

        rear->next = s;
        rear = s;
        length++;

    }
    //出队---头删
    bool delinkQueue()
    {
        //队列为空，返回假
        if (front == rear)
        {
            return false;
        }
        //进行头删
        //提前保存下一个要删除的节点
        node* temp = front->next;
        front->next = temp->next;
        //判断删除的是否是最后一个节点，是的话把rear指向头结点
        if (temp == rear)
        {
            rear = front;
        }
        free(temp);
        temp = NULL;
        length--;
        return true;
    }
    //获取队头元素
    cilent getTop()
    {
        if (length == 0)
        {
            cout << "获取队头元素失败" << endl;
            system("pause");
            exit(0);
        }
         node* temp= front->next;
         cilent person = temp->data;
        return person;
    }
    //清空队列
    void clear()
    {
        //清空除头结点以外的节点
        node* workNode;
        workNode = front->next;
        while (workNode)
        {
            //保存下一个要删除的节点
            node* nextNode = workNode;
            workNode = workNode->next;
            free(nextNode);
        }
        workNode = NULL;
        //尾指针更新到头指针处
        front->next = NULL;
        rear = front;
        length = 0;
    }
    int queueLen()
    {
        return length;
    }
    bool isEmpty()
    {
        if (length == 0)
            return true;
        return false;
    }
};

LinkList.hpp

处理事件的链表有序类型，链表里面存放的是事件类型结构体

#include<iostream>
using namespace std;
//由于事件表需按事件发生的先后顺序排列，
//需经常进行插入动作，
//则也采用单链表做存储结构。
//每个结点包含两个数据域：
//occurTime和nType（分别表示事件发生的时间和事件的类型-1表示新用户，0-3表示客户离开1-4个窗口）
struct eventNode {
	int occurTime;//事件发生的时间
	int nType;//事件处理的类型
	eventNode* next;
};

class LinkList
{
private:
	eventNode pHeader;//头结点是一个结构体
	int length;
public:
	LinkList()
	{
		pHeader.next = NULL;
		length = 0;
	}
	~LinkList()
	{
		//释放再堆区开辟的所有节点
		//保存释放的下一个节点
		while (pHeader.next)
		{
			eventNode* nextNode = pHeader.next->next;
			free(pHeader.next);
			pHeader.next = nextNode;
		}
		length = 0;
	}
	bool isEmpty()
	{
		if (length==0)
		{
			return true;
		}
		return false;
	}
	void addNode(eventNode event)
	{
		//插入是要按离开或者到达的时间顺序进行插入
		 //时间顺序：从早到晚
		//将用户输入的数据开辟在堆区存放
		eventNode* newNode = new eventNode(event);
		newNode->next = NULL;
		//对链表进行遍历，找到新用户该插入的位置
		eventNode* prveNode = &pHeader;
		eventNode* workNode = pHeader.next;
		while (workNode)
		{
			if (newNode->occurTime <= workNode->occurTime)
			{
				//将新用户节点插在该节点前面
				newNode->next = prveNode->next;
				prveNode->next = newNode;
				break;
			}
			prveNode = workNode;
			workNode = workNode->next;

		}
		//进行尾部插入的情况
		prveNode->next = newNode;
		length++;
	}
	eventNode deleteNode()
	{
		//保存第一个节点的数据，并进行返回
		eventNode returnNode;
		returnNode.nType = pHeader.next->nType;
		returnNode.occurTime = pHeader.next->occurTime;
		//将节点最前面，即时间越早的先删除
		eventNode* temp;
		temp = pHeader.next;
		pHeader.next = temp->next;
		free(temp);
		temp = NULL;
		length--;
		return returnNode;
	}
	void displayNode()
	{
		eventNode* workNode = pHeader.next;
		while (workNode)
		{
			if (workNode->nType == -1)
			{
				cout << "新用户到达时间为：" << workNode->occurTime << endl;
			}
			else {
				cout << workNode->nType << "号窗口的用户离开时间为：" << workNode->occurTime << endl;
			}
			workNode = workNode->next;
		}
	}
};

main.cpp

#include<iostream>
using namespace std;
#include"LinkQueue.hpp"
#include"LinkList.hpp"
#include<ctime>
#define CloseTime 40 //银行关门时间
//找出排队人数最少的队列下标
int findMin(linkQueue queue[],int len)
{
	int min = queue[0].queueLen();
	int index = 0;
	for (int i = 0; i < len; i++)
	{
		if (min>queue[i].queueLen())
		{
			min = queue[i].queueLen();
			index = i;
		}
    }
	return index;
}




//现写出银行业务活动如下：
//模仿
int simulation()
{
	//为客户服务的总时长
	int totalTime=0;
	//客户人数
	int customerNum=0;
	//初始化四个窗口队列
	linkQueue queue[4];
	//初始化事件链表对象
	LinkList eventList;
	//初始化一个客户结构体
	cilent person;
	//设定第一个客户到达的时间
	eventNode eventItem = { 0,-1,NULL };
	//将第一个客户放到事件链表中
	eventList.addNode(eventItem);
     //判断事件链表是否为空，不为空取出事件链表中第一个事件节点，判断是用户到达事件还是用户离开事件
	while(!eventList.isEmpty())
	{
		//取出事件链表中第一个节点
		eventNode firstNode = eventList.deleteNode();

		cout <<"第一个事件类型："<<firstNode.nType << endl;

		if (firstNode.nType == -1)//表示是新用户到达
		{
			customerNum++;
			
			//用随机值随机决定该用户将要在银行逗留时间和下一个用户到来的间隔时间
			int duringTime=rand() % 30 + 1;//逗留时间范围是1到30
			int interTime = rand() % 20 + 1;//下一个用户到来的间隔时间范围是1到20
			cout << "当前用户逗留时间" << duringTime << endl;
			//下一个新用户到来的时间---下一个到来事件发生的时间
		     //要判断下一个用户到来的时候，银行有没有关门
			//当前新用户到达时间+间隔时间
			if (firstNode.occurTime + interTime < CloseTime)
			{
				//设定下一个用户的到达事件插入事件表
				eventNode nextPerson = { firstNode.occurTime + interTime,-1,NULL };

				cout << "下一个用户到达时间:" << nextPerson.occurTime << endl;

				eventList.addNode(nextPerson);
			}

			//把当前到达的用户，放到当前排队人数最少的队列中
			//若四个队列排队人数相同，就按队列的顺序从下标小的先插入
		      int min = findMin(queue,4);

			  cout << "当前min=" << min << endl;

			  //当前客户进入人数最少的队列
		      //先对客户结构体进行赋值
			  person.arriveTime = firstNode.occurTime;
			  person.durTime = duringTime;

			  //然后入队
			  queue[min].enlinkQueue(person);
			  //入队完了之后，判断当前客户是不是窗口的第一个人，如果是就要把他的离开事件放入事件表中
			  if (queue[min].queueLen() == 1)
			  {
				  //离开的时间和几号窗口离开的
				  eventNode putIntoList = {firstNode.occurTime+duringTime,min};
				  cout << "当前用户离开的时间:" << putIntoList.occurTime << endl;
				  cout << "离开的窗口" << min << endl;
				  //将离开事件插入事件链表中
				  eventList.addNode(putIntoList);
			  }

		}
		else 
		{
			//表示处理的是用户离开事件
			
			//记录该用户从几号窗口离开
			int index = firstNode.nType;
			//用一个结构体来接收该离开用户的信息，方便获取他的逗留时间
			cilent leavePer = queue[index].getTop();
			//客户离开的时候，要累积客户的逗留时长
			totalTime += leavePer.durTime;
			//出队
			queue[index].delinkQueue();

			//判断出完队后，当前队列是否为空，如果为空，就不管
			//如果还有下一个用户，就要把下一个用户的离开事件放入事件表中
			if (queue[index].queueLen() != 0)
			{
				cilent nextPer = queue[index].getTop();
				//离开的时间等于到达的时间加上逗留的时间
				eventNode tempNode = { nextPer.arriveTime + nextPer.durTime,index,NULL };
				//放入事件表
				eventList.addNode(tempNode);
			}
		}
		cout << "当前正在处理的事件" << endl;
	}
	//计算客户的平均逗留时间
	cout << "用户访问总数" << customerNum << endl;
	cout << "总时间" << totalTime << endl;
	return totalTime/customerNum;
	
}
int main()
{
	srand(unsigned int(time (NULL)));
	int num=simulation();
	cout << "用户平均逗留时间为：" << num << endl;
	system("pause");
	return 0;
}