【数据结构与算法（C语言）】离散事件模拟- 单链表和队列的混合实际应用

1. 前言
2. 流程图
3. 数据结构
- 3.1 单链表
- 3.2 链式队列
4. 核心函数
- 4.1 银行业务模拟 void BankSimulation()
- 4.2 初始化 void OpenForDay()
- 4.3 客户到达 void CustomerArrived(Event en)
- 4.4 客户离开 void CustomerArrived(Event en)
5. 非核心函数
- 5.1 新建客户 NewCustomer
- 5.2 新建事件 NewEvent
- 5.3 查找最短的队列 ShortestQueueIndex
- 5.4 打印队列信息 PrintQueues
- 5.5 销毁数据结构 DestoryDataStruct
- 5.6 休眠函数 sleep
6. 编码全过程
- 6.1 数据结构头文件
- 6.2 队列函数文件
- 6.3 有序链表函数文件
- 6.4 新建主程序文件
7. 运行结果
8. 小结

1. 前言

假设银行有4个窗口对外接待客户，从早晨银行开门不断有客户进入银行。每个客户总是排队到人员最少的窗口办理业务。现在需要编写一个程序以模拟银行的这种业务并计算一天中银行逗留的平均时间。
为了计算这个平均时间，只需要将每个客户的离开银行时间减去到达银行时间得到一个客户的逗留事件，将所有客户的时间总和除以客户数就是所有的平均时间。称客户到达银行和离开银行这两个时刻发生的事情为事件,则整个模拟程序将按事件发生的先后顺序进行处理，这样一种模拟程序称作事件驱动模拟。

2. 流程图

在这里插入图片描述

3. 数据结构

需要两种数据结构：有序单链表和链式队列。

3.1 单链表

单链表用于存放事件，事件分类为两类：一类客户到达事件；另一类客户离开事件。事件按照发生时刻按照顺序存放在单链表中。

3.2 链式队列

4个队列分别模拟4个窗口，用于存放排队的客户。客户信息主要包括客户的编号、客户到达的时候、客户办理业务的时间。因为客户的人数不确定，所以使用链式存储方式。

4. 核心函数

为了让程序更加清晰，本文不详细介绍队列和单链表的实现，具体实现详解可查看以往的博客《线性表-单链表》和《队列-链队列》，本博文直接展示如何使用这些数据结构。
核心函数只有4个：银行业务模拟总函数 void BankSimulation()、银行开始营业(初始化) void OpenForDay()、客户达到函数 void CustomerArrived(Event en) 、客户离开函数void CustomerDeparture(Event en)。

4.1 银行业务模拟 void BankSimulation()

功能：银行业务的总体运行，其他所有函数都包含在此函数中。
主要包含一个循环，每次从事件链表中提取一个事件，并根据事件类型来驱动具体的流程。这个流程包括客户达（入列），客户离开（出列）。
实现：

void BankSimulation(){
	Event e;
	srand((unsigned)time(NULL));//使用时间生成一个随机种子
	OpenForDay();
	while(!ListEmpty(eventList))
	{
		ListDelFstNode(&eventList, &e); //从链表中提取一个事件
		if(e.nType==0)								//事件类型0，即客户到达
			CustomerArrived(e);				  //客户到达
		else 
			CustomerDeparture(e);			  //客户离开

		/*下面几行就是打印当前链表和队列*/
		printf("\n事件链表： ");
		ListTraverse(eventList);
		printf("\n\n");
		PrintQueues();
		printf("\n\n");

	}
	printf("每个客户平均时间:%f",(float)TotalTime/CustomerNumber);
	DestoryDataStruct();//最后销毁链表和数据结构，释放内存空间
}

4.2 初始化 void OpenForDay()

功能：银行开门，即初始化函数。
初始化事件链表、4个队列，同时生成第一个客户的到达事件，插入到事件链表中。
实现：

void OpenForDay()
{
	int i;
	InitList(&eventList);
	ListInsertByOrder(&eventList, NewEvent(0,0));
	for(i=0;i<4;i++)
		InitQueue(&queue[i]);
}

4.3 客户到达 void CustomerArrived(Event en)

功能：客户到达，主要功能有以下三个。
a). 生成一个新的客户到达事件，插入到事件链表中；
b). 将事件en中的刚到达客户信息插入到最短的队列中；
c). 如果队列插入前是空队列，则生成一个离开事件插入到事件链表中（空队列，说明客户到队列中，业务就立马办理了，无需等待)。
实现：

/*	事件en到达，主要有以下功能
	1. 生成一个新的客户到达事件，插入到事件链表中
	2. 将事件en中的刚到达客户信息插入到最短的队列中；
	3. 如果队列 插入前是空队列，则生成一个离开事件插入到事件链表中（空队列，说明客户到队列中，业务就立马办理了，无需等待)
*/
void CustomerArrived(Event en)
{	
	int i,duration;	//duration当前到达事件中的客户办理业务的持续时间
	int interTime_newCustomer;   // 新生成客户达到的间隔时间；
	int arrivalTime_newCustomer; //新生成客户的到达事件
	interTime_newCustomer = rand()%5 + 1;//新生成客户到达时间设置5分钟之内
	duration = rand()%30 + 1;			 //当前到达客户业务办理时间在30分钟
	arrivalTime_newCustomer = en.occurTime+interTime_newCustomer ;
	printf("时刻 %d: %d号 客户到达;\n",en.occurTime,++CustomerNumber);
	if(arrivalTime_newCustomer < CloseTime)
	ListInsertByOrder(&eventList,NewEvent(arrivalTime_newCustomer,0)); //生成一个新的客户到达事件插入到事件链表中

	i=ShortestQueueIndex();
	EnQueue(&queue[i],NewCustomer(CustomerNumber,en.occurTime,duration)); //到达客户入列
	if(QueueLength(queue[i])==1)//插入之前是空队列
		ListInsertByOrder(&eventList,NewEvent(en.occurTime+duration,i+1));//生成一个离开事件插入到事件链表中
}

4.4 客户离开 void CustomerArrived(Event en)

功能：客户到达，主要功能有以下两个。
a).从队列中删除客户，打印离开信息，统计总用时;
b). 如果队列不空，则获取队列（删除客户）的下一个客户，以表示下一个客户开始办理业务，并将这个客户的离开事件插入到事件链表中去。
实现：

// 顾客离开事件
// 功能1 ：从队列中删除客户，打印离开信息，统计总用时; 
// 功能2 ：如果队列不空，则获取队列（删除客户）的下一个客户，
//		   以表示下一个客户开始办理业务，并将这个客户的离开事件插入到LinkList中去。
void CustomerDeparture(Event en)
{
	int i=en.nType-1;
	QElemType customer;
	DeQueue(&queue[i],&customer);
	printf("时刻 %d: %d号 客户离开;\n",en.occurTime,customer.number);
	TotalTime += en.occurTime - customer.arrivalTime;
	if(!QueueEmpty(queue[i])){
		GetHead(queue[i],&customer); //从队列中获取下一个客户
		ListInsertByOrder(&eventList,NewEvent(en.occurTime+customer.duration,i+1));//下个客户的离开事件插入事件链表
	}
}

5. 非核心函数

除了上面4个核心函数，还有几个非核心函数。很简单，无需花时间去理解。如生成新的事件、生成新的客户、获取长达字段的队列等等

5.1 新建客户 NewCustomer

功能：新建一个客户信息的元素（队列的元素）
实现：

/*新建一个客户信息的元素（队列的元素）*/
QElemType NewCustomer(int number, int arrivalTime,int duration)
{
	QElemType e;
	e.number=number;
	e.arrivalTime=arrivalTime;
	e.duration=duration;
	return e;
}

5.2 新建事件 NewEvent

功能：新建一个事件（单链表结点中的数据）
实现：

/*新建一个事件（单链表结点中的数据）*/
ElemType NewEvent(int occurTime,int nType)
{
	Event e;
	e.occurTime=occurTime;
	e.nType=nType;
	return e;
}

5.3 查找最短的队列 ShortestQueueIndex

功能：查找长度最短的队列
实现：

/*在队列数组中查找长度最短的队列，并返回其下标*/
int ShortestQueueIndex()
{
	int i,minQueueIndex=0;			 //minQueueIndex 最短队列下标
	int minLen=QueueLength(queue[0]);//定义一个最小长度变量
	for(i=1;i<4;i++)
	{
		if(minLen>QueueLength(queue[i])){
			minLen=QueueLength(queue[i]);
			minQueueIndex=i;
		}
	}
	return minQueueIndex;
}

5.4 打印队列信息 PrintQueues

功能：打印4个队列的信息
实现：

/*打印4个队列*/
void PrintQueues()
{
	int i=0;
	for(;i<4;i++)
	{
		printf("%d 号窗口：",i+1);
		QueueTraverse(queue[i]);
	}
}

5.5 销毁数据结构 DestoryDataStruct

功能：销毁数据结构，程序运行完毕，务必销毁数据结构，释放手动申请的内存空间
实现：

/*销毁链表和队列*/
void DestoryDataStruct()
{
	int i=0;
	DestroyList(&eventList);
	for(;i<4;i++)
	{
		DestroyQueue(&queue[i]);
	}
}

5.6 休眠函数 sleep

功能：程序休眠（暂停）一段时间。这个函数不是必要的。本示例在循环中加上，纯粹是为了更加清楚的在控制台观察程序运行过程
实现：

//休眠函数
void sleep(float time)
{
   clock_t   now   =   clock(); 
   while( clock() - now < time*1000); 
}

6. 编码全过程

为了项目的清晰，将单链表和队列的实现方法单独存放两个文件中。

6.1 数据结构头文件

首先新建一个数据结构的头文件 DataStruct.h，其中包含有序单链表和队列的元素、结点、结构定义。

/*队列*/
#define TRUE  1
#define FALSE 0
#define OK    1
#define ERROR 0

typedef  int Status;

/* 以下是队列Queue的结构和基本操作 的声明*/
typedef struct {
	 int number;	   //编号，标识客户
	 int arrivalTime;  //客户到达时间
	 int duration;	   //办理事务时间
} QElemType;		   //队列的元素类型

typedef struct QNode{
	QElemType data;	   
	struct QNode * next;
} QNode;			   //队列的结点类型

typedef struct {
	QNode * front;	   //队头指针
	QNode * rear;	   //队尾指针
	int length;		   //队列长度
}LinkQueue;			   //定义一个链式队列

Status InitQueue(LinkQueue * queue);			/*初始化队列,申请一个头结点的内存*/
void DestroyQueue(LinkQueue * queue);			/*销毁队列*/
Status ClearQueue(LinkQueue * queue);			//将队列queue清空
Status QueueEmpty(LinkQueue queue);				//判断队列是否为空
Status GetHead(LinkQueue queue ,QElemType * e); //获取队列第一个元素
int QueueLength(LinkQueue queue);				//返回队列长度
Status EnQueue(LinkQueue * queue, QElemType e);	//元素e 插入队列queue
Status DeQueue(LinkQueue * queue ,QElemType * e);  //若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status QueueTraverse(LinkQueue queue);			//遍历队列，对队列的每个元素调用Visit函数



/*以下为单链表的结构和基本操作 的声明*/
typedef struct Event{
	int occurTime;	  //事件发生时刻
	int nType;		  //事件类型，0：到达事件；1到4表示四个窗口的离开事件;
	
}Event,ElemType;	  //单链表的结点：事件

typedef struct LNode{
	ElemType data;		  //单链表的事件(即单链表的元素)
	struct LNode * next;  //下一个结点指针
}LNode;			 //单链表的结点

typedef struct {
	LNode * head;		//头指针
	LNode * rear;		//尾指针
	int length;			//链表长度
}LinkList;				//单链表结构

Status InitList(LinkList * L);						//初始化单链表
void DestroyList(LinkList * L);					//销毁单链表
Status ListInsertByOrder(LinkList * L, Event e);    //将事件e（链表的元素)的发生时间顺序插入到链表中
Status ListEmpty(LinkList  L);						//判断链表是否为空，空返回TRUE,否则返回FALSE;
Status ListDelFstNode(LinkList * L, Event * e);		//从链表中删除首结点，并将结点中的元素（事件）使用 e 返回
Status ListTraverse(LinkList  L);					//遍历链表

6.2 队列函数文件

第二步，新建队列基本操作的文件 LinkQueue.c。

#include <stdio.h>
#include <stdlib.h>
#include "DataStruct.h"

/*初始化队列,申请一个头结点的内存*/
Status InitQueue(LinkQueue * queue)
{
	queue->front=(QNode *) malloc(sizeof(QNode));
	if(queue->front == NULL)
		exit(0);
	queue->front->next = NULL;
	queue->rear = queue->front;
	queue->length = 0;
	return OK;
}

/*销毁队列*/
void DestroyQueue(LinkQueue * queue)
{
	ClearQueue(queue);
	free(queue->front);
	queue->rear=queue->front=NULL;
}

 /* 将队列queue清空*/
Status ClearQueue(LinkQueue * queue)
{
	QNode * curNode;
	while((curNode= queue->front->next)!=NULL)
	{
		queue->front->next = curNode->next;
		free(curNode);
	}
	queue->rear=queue->front;
	queue->length=0;
	return OK;
}
//判断队列是否为空
Status QueueEmpty(LinkQueue queue)
{
	return queue.front == queue.rear? TRUE:FALSE;
}

 //获取队列第一个元素
Status GetHead(LinkQueue queue, QElemType * e)
{
	if(queue.length==0)
		return FALSE;
	*e=queue.front->next->data;
	return TRUE;
}

int QueueLength(LinkQueue queue)
{
	return queue.length;
}

//元素e 插入队列queue
Status EnQueue(LinkQueue * queue, QElemType e)
{
	QNode * curNode;
	curNode=(QNode *)malloc(sizeof(QNode));
	if(curNode == NULL)
	{
		printf("申请空间失败");
		exit(0);
	}
	curNode->data = e ;
	curNode->next = NULL;
	queue->rear->next = curNode;
	queue->rear = curNode;
	queue->length++;
	return TRUE;
}

//若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status DeQueue(LinkQueue * queue ,QElemType * e)
{
	QNode * firstNode;
	if(queue->length == 0)
		return FALSE;
	firstNode=queue->front->next;
	*e=firstNode->data;
	queue->front->next=firstNode->next;
	free(firstNode);
	if(--queue->length==0)
		queue->rear=queue->front;
	return TRUE;
}
//队列遍历
Status QueueTraverse(LinkQueue queue)
{
	QNode * curNode;
	if(queue.length==0)
	{
		printf("队列为空\n");
		return FALSE;
	}
	curNode=queue.front->next;
	while(curNode)
	{
		printf("(编号:%d,达到时间:%d,持续时间:%d) ",curNode->data.number,curNode->data.arrivalTime,curNode->data.duration);
		curNode=curNode->next;
	}
	printf("\n");
	return TRUE;
}

6.3 有序链表函数文件

第三步，新建有序单链表基本操作函数的文件 LinkList.c。

#include <stdio.h>
#include <stdlib.h>
#include "DataStruct.h"

 /*初始化单链表*/
Status InitList(LinkList * list)
{
	list->head=(LNode*) malloc(sizeof(LNode));
	if(list->head == NULL)
		exit(0);
	list->head->next = NULL;
	list->rear=list->head;
	list->length=0;
	return TRUE;
}

 /* 销毁单链表 */
void DestroyList(LinkList * list)
{
	LNode * curNode, * tempNode;
	curNode= list->head->next;
	while(curNode)
	{
		tempNode=curNode;
		curNode=curNode->next;
		free(tempNode);
	}
	free(list->head); //释放头结点
	list->head = list->rear = NULL;
	list->length = 0;
}


/* 将事件e（链表的元素)的发生时间顺序插入到链表中*/
Status ListInsertByOrder(LinkList * list, Event e)
{
	LNode * newNode,*curNode;
	newNode=(LNode *) malloc(sizeof(LNode));
	if(newNode == NULL)
		exit(0);
	newNode->data = e;
	
	if(list->length==0)			//链表为空
	{
		list->rear = list->head->next = newNode;
		newNode->next = NULL;

	}else						//链表不为空，需要循环找到插入位置
	{
		curNode=list->head;
		while(curNode->next != NULL && curNode->next->data.occurTime < e.occurTime) //遍历链表，找到e的合理位置
			curNode=curNode->next;

		if(curNode->next ==NULL) //在链表尾部
			list->rear=newNode;

		newNode->next = curNode->next;
		curNode->next = newNode;
	}
	list -> length++;
	return TRUE;

}

/*判断链表是否为空，空返回TRUE,否则返回FALSE;*/
Status ListEmpty(LinkList  list)
{
	return list.length == 0? TRUE:FALSE;
}

 /*从链表中删除首结点，并将第一个结点使用 node返回 */
Status ListDelFstNode(LinkList * list, Event * e)
{
	LNode * fstNode =list->head->next; //获取第一个结点
	if(ListEmpty(*list))
		return FALSE;
	*e= fstNode->data;
	list->head->next = fstNode->next;
	list->length--;
	if(list->length==0) //如果删除的结点是最后一个结点
		list->rear=list->head;
	free(fstNode);
	return TRUE;
}

/* 遍历链表 */
Status ListTraverse(LinkList  list)
{

	LNode * curNode=list.head->next;
	if(list.length==0){
		printf("链表为空\n");
		return ERROR;
	}
	while(curNode)
	{
		printf("(发生时刻:%d,事件类型:%d),",curNode->data.occurTime,curNode->data.nType);
		curNode = curNode->next;
	}

	return OK;
}

6.4 新建主程序文件

最后一步，新建银行业务模拟的主程序

#include <stdio.h>
#include <time.h>
#include "DataStruct.h"

int CustomerNumber = 0;	//顾客的编号
int CloseTime = 50 ;	//银行关闭时间,即营业时间长度
int TotalTime = 0;		//所有客户总耗时
LinkQueue queue[4];		//4个队列模拟四个窗口
LinkList  eventList;	//事件链表

/*新建一个客户信息的元素（队列的元素）*/
QElemType NewCustomer(int number, int arrivalTime,int duration);
/*新建一个事件（单链表结点中的数据）*/
ElemType NewEvent(int occurTime,int nType);
/*在队列数组中查找长度最短的队列，并返回其下标*/
int ShortestQueueIndex();
/*打印4个队列*/
void PrintQueues();
//休眠函数
void sleep(float time);
/*销毁链表和队列*/
void DestoryDataStruct();


/*下面4个函数为核心函数*/
/*银行开门营业*/
void OpenForDay();
/*客户到达事件*/
void CustomerArrived(Event en);
/*客户离开*/
void CustomerDeparture(Event en);
/*银行模拟程序*/
void BankSimulation();


/*新建一个客户信息的元素（队列的元素）*/
QElemType NewCustomer(int number, int arrivalTime,int duration)
{
	QElemType e;
	e.number=number;
	e.arrivalTime=arrivalTime;
	e.duration=duration;
	return e;
}

/*新建一个事件（单链表结点中的数据）*/
ElemType NewEvent(int occurTime,int nType)
{
	Event e;
	e.occurTime=occurTime;
	e.nType=nType;
	return e;
}

/*在队列数组中查找长度最短的队列，并返回其下标*/
int ShortestQueueIndex()
{
	int i,minQueueIndex=0;			 //minQueueIndex 最短队列下标
	int minLen=QueueLength(queue[0]);//定义一个最小长度变量
	for(i=1;i<4;i++)
	{
		if(minLen>QueueLength(queue[i])){
			minLen=QueueLength(queue[i]);
			minQueueIndex=i;
		}
	}
	return minQueueIndex;
}

/*打印4个队列*/
void PrintQueues()
{
	int i=0;
	for(;i<4;i++)
	{
		printf("%d 号窗口：",i+1);
		QueueTraverse(queue[i]);
	}
}
//休眠函数
void sleep(float time)
{
   clock_t   now   =   clock(); 
   while( clock() - now < time*1000); 
}

/*销毁链表和队列*/
void DestoryDataStruct()
{
	int i=0;
	DestroyList(&eventList);
	for(;i<4;i++)
	{
		DestroyQueue(&queue[i]);
	}
}

/*银行开门营业，有以下几个功能：
	1. 初始化事件链表，并生成第一个客户到达事件插入链表
	2. 初始化4个队列，用于模拟银行窗口。
*/
void OpenForDay()
{
	int i;
	InitList(&eventList);
	ListInsertByOrder(&eventList, NewEvent(0,0));
	for(i=0;i<4;i++)
		InitQueue(&queue[i]);
}



/*	客户到达事件，主要有以下功能
	1. 生成一个新的客户到达事件，插入到事件链表中
	2. 将事件en中的刚到达客户信息插入到最短的队列中；
	3. 如果队列 插入前是空队列，则生成一个离开事件插入到事件链表中（空队列，说明客户到队列中，业务就立马办理了，无需等待)
*/
void CustomerArrived(Event en)
{	
	int i,duration;	//duration当前到达事件中的客户办理业务的持续时间
	int interTime_newCustomer;   // 新生成客户达到的间隔时间；
	int arrivalTime_newCustomer; //新生成客户的到达事件
	interTime_newCustomer = rand()%5 + 1;//新生成客户到达时间设置5分钟之内
	duration = rand()%30 + 1;			 //当前到达客户业务办理时间在30分钟
	arrivalTime_newCustomer = en.occurTime+interTime_newCustomer ;
	printf("时刻 %d: %d号 客户到达;\n",en.occurTime,++CustomerNumber);
	if(arrivalTime_newCustomer < CloseTime)
	ListInsertByOrder(&eventList,NewEvent(arrivalTime_newCustomer,0)); //生成一个新的客户到达事件插入到事件链表中

	i=ShortestQueueIndex();
	EnQueue(&queue[i],NewCustomer(CustomerNumber,en.occurTime,duration)); //到达客户入列
	if(QueueLength(queue[i])==1)//插入之前是空队列
		ListInsertByOrder(&eventList,NewEvent(en.occurTime+duration,i+1));//生成一个离开事件插入到事件链表中
}

/*客户离开*/
void CustomerDeparture(Event en)
{
	int i=en.nType-1;
	QElemType customer;
	DeQueue(&queue[i],&customer);
	printf("时刻 %d: %d号 客户离开;\n",en.occurTime,customer.number);
	TotalTime += en.occurTime - customer.arrivalTime;
	if(!QueueEmpty(queue[i])){
		GetHead(queue[i],&customer); //从队列中获取下一个客户
		ListInsertByOrder(&eventList,NewEvent(en.occurTime+customer.duration,i+1));//下个客户的离开事件插入事件链表
	}
		
}

void BankSimulation(){
	Event e;
	srand((unsigned)time(NULL));//使用时间生成一个随机种子
	OpenForDay();
	while(!ListEmpty(eventList))
	{
		ListDelFstNode(&eventList, &e);
		if(e.nType==0)
			CustomerArrived(e);
		else 
			CustomerDeparture(e);

		/*下面几行就是打印当前链表和队列*/
		printf("\n事件链表： ");
		ListTraverse(eventList);
		printf("\n\n");
		PrintQueues();
		printf("\n\n");
		sleep(1);//休眠1秒,可以注释掉
	}
	printf("每个客户平均时间:%f",(float)TotalTime/CustomerNumber);
	DestoryDataStruct();//最后销毁链表和数据结构，释放内存空间
}


int main()
{
	BankSimulation();
	getchar();
	return 0;
}