|
|
#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; // 事件发生时刻
|
|
|
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); // 银行业务模拟，统计一天内客户在银行逗留的平均时间
|
|
|
int cmp(Event a, Event b); // 比较事件发生先后
|
|
|
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); // 获取队头元素 注：由于参数个数不同，发生函数重载
|
|
|
Status QueueEmpty(LinkQueue Q); // 判断队列是否为空
|
|
|
void PrintQueue(); // 打印队列
|
|
|
Status QueueTraverse(LinkQueue Q); // 遍历队列Q
|
|
|
|
|
|
/*
|
|
|
系统每次随机生成的是
|
|
|
1）当前客户的柜台被服务时间
|
|
|
2）当前客户和下一个客户到达的间隔时间
|
|
|
每个客户在银行的等待时间取决于队列里前一个节点的离开时间，而不是自己的到达时间+服务时间。*/
|
|
|
|
|
|
int main()
|
|
|
{
|
|
|
srand((unsigned)time(NULL)); // 设定随机数种子
|
|
|
printf("请输入银行的营业时间(min)：");
|
|
|
scanf("%d", &CloseTime);
|
|
|
Bank_Simulation(CloseTime);
|
|
|
return 0;
|
|
|
}
|
|
|
void Bank_Simulation(int CloseTime) // 银行业务模拟，统计一天内客户在银行逗留的平均时间
|
|
|
{
|
|
|
OpenForDay(); // 开始营业
|
|
|
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) // 比较事件发生先后
|
|
|
{
|
|
|
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)) // 插入事件
|
|
|
// 事件插入函数，将不同事件按发生时间递增排序
|
|
|
{
|
|
|
LNode *p = L;
|
|
|
int i = 1;
|
|
|
while (p->next && cmp(en, p->next->data) > 0) // 找到事件发生时间所在事件链表中的位置
|
|
|
{
|
|
|
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) // 如果他在营业时间内进来
|
|
|
{
|
|
|
printf("一个新客户在银行营业%2dmin后进来，办理业务花费了%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 办理业务需要花费 %d min) ", p->data.ArrivalTime, p->data.Duration);
|
|
|
p = p->next;
|
|
|
}
|
|
|
printf("\n");
|
|
|
return OK;
|
|
|
}
|
