《數據結構（C語言版）》離散事件模擬之銀行業(yè)務模擬
清華大學計算機系列教材? ?累計發(fā)行超400萬冊
嚴蔚敏 吳偉民 編著
數據結構（C語言版）
以下是本人對該紫皮書第三章棧和隊列中3.5節(jié)離散事件模擬的銀行業(yè)務模擬代碼實現，整個代碼需要用到第二章線性鏈表的絕大部分函數和第三種鏈隊列的絕大部分函數，是一個綜合性很強的問題，有億點點復雜，本人也是多方借鑒整合并優(yōu)化弄出來的代碼，另外把每一步顧客到了哪個窗口和事件鏈表打印出來，便于讀者理解
事實上，這個銀行業(yè)務模擬仍有很多地方可以優(yōu)化，比如課本上就沒有考慮到排隊時，若到某個窗口辦事的客戶很快就辦理好業(yè)務，隊伍比較短，這時在旁邊排長隊的客戶會轉到短隊上
話不多說上運行結果
代碼如下：加上注釋與換行約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;//事件發(fā)生時刻
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);//銀行業(yè)務模擬，統計一天內客戶在銀行逗留的平均時間
int cmp(Event a, Event b);//比較事件發(fā)生先后
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);//獲取隊頭元素 注：由于參數個數不同，發(fā)生函數重載
Status QueueEmpty(LinkQueue Q);//判斷隊列是否為空
void PrintQueue();//打印隊列
Status QueueTraverse(LinkQueue Q);//遍歷隊列Q?
/*
系統每次隨機生成的是
1）當前顧客顧客的柜臺被服務時間
2）當前顧客和下一個顧客到達的間隔時間
記住這2點就便于理解整個代碼
每個顧客在銀行的等待時間取決于隊列里前一個節(jié)點的離開時間，而不是自己的到達時間+服務時間。
*/
int main()
{
srand((unsigned)time(NULL));//設定隨機數種子
printf("請輸入銀行的營業(yè)時間(min)：");
scanf("%d", &CloseTime);
Bank_Simulation(CloseTime);
return 0;
}
void Bank_Simulation(int CloseTime)//銀行業(yè)務模擬，統計一天內客戶在銀行逗留的平均時間
{
OpenForDay();//開始營業(yè)
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)//比較事件發(fā)生先后
{
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))//插入事件
//事件插入函數，將不同事件按發(fā)生時間遞增排序
{
LNode* p = L;
int i = 1;
while (p->next && cmp(en, p->next->data) > 0)//找到事件發(fā)生時間所在事件鏈表中的位置
{
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)//如果他在營業(yè)時間內進來
{
printf("一個新客戶在銀行營業(yè)%2dmin后進來，辦理業(yè)務花費了%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 辦理業(yè)務需要花費 %d min) ", p->data.ArrivalTime, p->data.Duration);
p = p->next;
}
printf("\n");
return OK;
}
