为啥队列指针指着指着就不运行了,前面都能进去,到这就不行了
#include <stdio.h>
#include <stdlib.h>
#include <time.h.>
//#define PAUSE
// window number 银行业务窗口数量
// 程序中窗口编号为 0 ~ WINNUM-1
#define WINNUM 4
/*
// 事件类型,包括到达银行和办完业务后离开所在窗口
// 用不同的整数来区分这些事件
//
// 窗口编号为 0 ~ WINNUM-1
// 客户离开某窗口事件用 0 ~ WINNUM-1 间一个整数来表示
// 表示客户办完业务后离开了排队的窗口
//
// 客户的到达事件用整数 WINNUM 表示
*/
typedef int EventType; // EventType 就是 int
#define ArrEvent WINNUM // 整数 WINNUM 表示到达事件
// 事件,作为链表结点的数据域
typedef struct _Event
{
int time; // 事件发生时刻
EventType type; // 事件类型
}Event, LNData; // 事件,有序链表结点数据域 Link Node Data
// 链表结点 Link Node
typedef struct _LNode
{
LNData data; // 数据域
struct _LNode* next;// 指针域
}LNode, * PLNode;
// 链表
typedef struct _LinkList
{
int len; // 线性链表长度
PLNode head, tail; // 分别指向线性链表中的头结点和最后一个结点
} LinkList;
// 定义“客户”类型,作为窗口队列结点的数据域
typedef struct _Customer
{
int ord; // 到达序号
int arrtime; // 到达时刻
int duration; // 办理业务时间
}Customer, QNData; // Queue Node Data
// 窗口队列结点 Queue Node
typedef struct _QNode
{
QNData data; // 数据域
struct _QNode* next;// 指针域
}QNode, * PQNode;
// 链式队列
typedef struct _LinkQueue
{
PQNode front; // 队头指针 指向头结点
PQNode rear; // 队尾指针 指向最后一个结点
}LinkQueue;
// 队列 8个 函数声明
int InitQueue(LinkQueue* pq); // 构造
void BrowseQueue(const LinkQueue lq); // 显示
int QueueEmpty(const LinkQueue lq); // 判空
int EnQueue(LinkQueue* pq, QNData d); // 入队
int QueueLength(const LinkQueue lq); // 队长
int DeQueue(LinkQueue* pq, QNData* pd); // 出队
int GetHead(LinkQueue lq, QNData* pd); // 队头
int DestroyQueue(LinkQueue* pq); // 销毁
// 链表 8个 函数声明
int InitList(LinkList* pl); // 构造
int ListEmpty(LinkList ll); // 判空
void BrowseList(const LinkList ll); // 显示
int cmp(Event a, Event b); // 比较两个事件的发生时刻
int OrderInsert(LinkList* pl, LNData d, int (*cmp)(LNData, LNData)); // 插入
int DelFirst(LinkList* pl, LNData* pd); // 删除
int ClearList(LinkList* pl); // 清空
int DestroyList(LinkList* pl); // 销毁
// #########################################################
// #########
/*
* 程序以分钟为单位,设定一天的营业时间为8小时共480分钟
*
* 客户的到达时间和办理业务所需时间都是随机的
* 程序中用随机函数来产生这两个时间
*
* 到达时间:第一个客户的到达时间可以指定为 0
* 然后用前一个客户的到达时间加上一个随机的间隔时间
* 作为一下个客户的到达时间
*
* 客户的离开时间,是他所在窗口队列中
* 排在他前面的客户的离开时间
* 加上他办理业务的时间
*/
// 全局变量
int CloseTime = 480; // 银行营业时间( 单位是分钟 8小时*60分 )
int TotalTime = 0; // 统计所有客户的逗留时间,初始为0
int CustomerNum = 0; // 统计一天的客户数,初值为0
// 相邻两客户到达时间相间隔的最大值
// 即前后两客户到达时间相间隔是 0 ~ INTERVAL 中一个随机值
#define INTERVAL 10
// 客户办理业务时间最大值
// 每个客户办理业务用时为 0 ~ DURATION 中一个随机值
#define DURATION 20
// 新增加的函数
typedef LinkList EventList; // 事件链表,EventList 是 LinkList 的另一个名字
typedef LinkQueue WinQueue; // 窗口队列,WinQueue 是 LinkQueue 的另一个名字
// 已完成
void OpenForDay(EventList* pl, WinQueue wq[]); //
void CloseForDay(EventList* pl, WinQueue wq[]);
void Bank_Simulation();
// 待完成
int MinQueue(WinQueue wq[]);
void CustomerArrive(EventList* pl, WinQueue wq[], Event evt);
void CustomerDepart(EventList* pl, WinQueue wq[], Event evt);
// 银行开门时,进行的初始化操作。
// 对一个事件链表 *pel,若干个窗口队列进行初始化
// 假设第一个顾客到达的时间为 0 时刻
void OpenForDay(EventList* pel, WinQueue wq[])
{
InitList(pel); // 初始化“事件”链表为空
for (int i = 0; i < WINNUM; ++i) // 初始化各个窗口的队列
InitQueue(&wq[i]);
Event evt; // 事件变量
evt.time = 0; // 直接指定第一个客户到达时间
evt.type = ArrEvent; // 事件类型:“到达事件”
OrderInsert(pel, evt, cmp); // 一产生到达和离开事件,马上插入到有序事件表中
}
// 关门,清理 链表 队列
void CloseForDay(EventList* pel, WinQueue wq[])
{
DestroyList(pel); // 销毁链表
for (int i = 0; i < WINNUM; ++i)
DestroyQueue(&wq[i]); // 销毁各窗口队列
}
// 模拟银行业务,计算客户在银行的逗留时间。
void Bank_Simulation()
{
EventList el; // “事件”表,有序单链表
WinQueue wq[WINNUM]; // 窗口队列数组
srand((unsigned)time(NULL)); // 随机种子
OpenForDay(&el, wq); // 银行开门初始化
// 当事件链表非空时,利用循环按时间顺序逐一处理事件表中的各个事件
while (!ListEmpty(el))
{
Event evt;
DelFirst(&el, &evt); // 取得并删除事件表的第一个结点
if (evt.type == ArrEvent)// 根据不同的事件类型
{
printf("11111111111");
CustomerArrive(&el, wq, evt); // 处理到达事件
printf("333333333");
}
else {
printf("4444444");
CustomerDepart(&el, wq, evt); // 处理离开事件
printf("555555");
}
printf("2222222222\n");
}
CloseForDay(&el, wq); // 关门
printf("顾客总数: %d 人, 所有顾客共耗时: %d 分钟, 平均每人耗时: %d 分钟\n",
CustomerNum, TotalTime, TotalTime / CustomerNum);
}
int main()
{
// 模拟银行事务处理。
Bank_Simulation();
return 0;
}
// 参数 wq:窗口队列数组,按先来先服务的顺序排队
int MinQueue(WinQueue wq[])
{
int m, ml, len;
m = 0; // 先选择0号队列
len = QueueLength(wq[0]); // 0号队列长度
ml = len;
// 1. *********** 此处添加代码 **************
// 和其它队列进行比较,选取长度最短队列
int i=0;
while (i < WINNUM)
{
i++;
len = QueueLength(wq[i]);
if (len < ml)
{
m = i;
ml = len;
}
}
return m; // 返回最短队列的编号( 0 ~ WINNUM-1)
}
// 函数 CustomerArrive
// 处理客户到达事件
/*
参数:
pel:事件链表,如果有新的事件,按发生的时间顺序插入到表中
wq: 窗口队列,总是处理队首结点
evt:客户到达事件,其发生时间就是一个客户的到达时间
*/
void CustomerArrive(EventList* pel, WinQueue wq[], Event evt)
{
Customer cust; // 客户,和队列结点的数据域实际上是同一类型,有3个成员
cust.ord = ++CustomerNum; // 全局变量CustomerNum记录了客户的数量
cust.arrtime = evt.time; // 到达事件evt中的时间作为客户的到达时间
cust.duration = rand() % DURATION;// 办理业务时间为随机值
// 2. *********** 此处添加代码 **************
int wi = 0; // 窗口编号
wi = MinQueue(wq);// 一个新客户到达后,会选择一个窗口排队
// 求长度最短队列的序号 wi,若有等长情况,取最小的序号
printf("5555555");
EnQueue(&wq[wi], cust);// 将顾客入队
printf("666665");
// 注意要使用变量 wi
// 调试用代码,显示所有客户, 可删除
printf("客户 %4d 于 %5d 分到达 %2d 号窗口 所办业务需要 %4d 分钟 队伍前面有 %2d 人\n",
cust.ord, cust.arrtime, wi + 1, cust.duration, QueueLength(wq[wi]) - 1);
///////////////////////////////
// 如果该队列恰好只有一个顾客,马上可以确定一个离队事件
// 到达时间+办理业务时间 就是离开时间
// 将该事件插入到事件链表中
if (1 == QueueLength(wq[wi])) // 队列中只有一个客户
{
// 3. *********** 此处添加代码 **************
// 给事件 depevt 成员赋值,并将其插入到事件表中
Event depevt; // 离队事件
depevt.time = cust.arrtime + cust.duration;
depevt.type = wi;
OrderInsert(pel,depevt,cmp);
}
// 产生下一位客户
Customer nextcust;
nextcust.arrtime = cust.arrtime + rand() % INTERVAL; // 下一客户到达时刻
if (nextcust.arrtime < CloseTime) // 尚未关门,插入事件表
{
// 4. *********** 此处添加代码 **************
// 给事件 arrevt 成员赋值,并将其插入到事件表中
Event arrevt; // 产生一个到达事件
arrevt.time = nextcust.arrtime;
arrevt.type = WINNUM;
OrderInsert(pel,arrevt,cmp);
}
}
// 函数 CustomerDepart,处理客户的离开事件
// evt.type 提供了所在窗口的编号
// 离队,计算逗留时间 = 出队时间 - 到达时间
// 由于队列中一个客户的离开,他后面的客户可以开始办理业务
// 前面客户的离开时间 + 当前客户的业务时间
// 可以确定一个离开事件并插入事件表中
void CustomerDepart(EventList* pel, WinQueue wq[], Event evt)
{
int wi = 0;// 窗口的编号
Customer cust = { 0 };
Event depevt;
// 5. *********** 此处添加代码 **************
wi = evt.type;
DeQueue(&wq[wi], &cust);
if (wq[wi].front->next != NULL)
{
depevt.time = evt.time + wq[wi].front->next->data.duration;
depevt.type = evt.type;
OrderInsert(pel, depevt, cmp);
}
///////////////////////////////
// 调试用,可删除
printf("客户 %4d 于 %5d 分离开 %2d 号窗口 共用时 %10d 分钟\n",
cust.ord, evt.time, wi + 1, evt.time - cust.arrtime);
#ifdef PAUSE
if (cust.ord % 10 == 0)
system("pause");
#endif
/////////////////////////////////
}
// 构造一个空队列,只有头结点
int InitQueue(LinkQueue* pq)
{
// 生成头结点
pq->front = pq->rear = (QNode*)malloc(sizeof(QNode));
if (!pq->front) // 生成失败
{
printf("InitQueue fail\n");
exit(0);
}
pq->front->next = NULL; // 指针域置空
return 1;
}
// 判断队列是否为空,若为空队列,则返回 1,否则返回 0
int QueueEmpty(const LinkQueue lq)
{
return lq.front == lq.rear;
}
// 显示队列
void BrowseQueue(const LinkQueue lq)
{
if (QueueEmpty(lq)) // 空队列
{
printf("Empty Queue\n\n");
return;
}
PQNode pq; // 结点指针
pq = lq.front->next; // 指向第一个结点
do
{
printf("%d -> ", pq->data.ord); // 显示数据域
pq = pq->next; // 指向下一个结点
} while (pq);
printf("\b\b\b \n\n");
}
// 入队,插入新结点到队尾
int EnQueue(LinkQueue* pq, QNData d)
{
// 生成新结点
QNode* p = (QNode*)malloc(sizeof(QNode));
if (!p) // 存储分配失败
{
printf("EnQueue Fail\n");
exit(0);
}
// 结点数据域、指针域赋值
p->data = d;
p->next = NULL;
// 插到队尾
printf("44444444");
printf("1213145222");
printf("%d,,,,,%d,,,,%d\n", pq->front->data.arrtime, pq->front->data.duration, pq->front->data.ord);
printf("%d,,,,,%d,,,,%d\n", pq->rear->data.arrtime, pq->rear->data.duration, pq->rear->data.ord);
pq->rear->next = p;
pq->rear = p;
printf("%d,,,,,%d,,,,%d\n",pq->rear->data.arrtime,pq->rear->data.duration,pq->rear->data.ord);
return 1;
}
// 求队列的长度,不包括头结点
int QueueLength(const LinkQueue lq)
{
int len = 0;
PQNode p;//创建一个新的指针指向4个节点的第一个节点
p = lq.front;
while (p != lq.rear)//移动指针直到指向最后一个节点
{
p = p->next;
len++;
}
return len;//返回队伍的长度
}
int DeQueue(LinkQueue* pq, QNData* pd)//实现队列的出队操作,删除第一位顾客的节点
{
int a;
a = QueueEmpty(*pq);//先判断队列是否为空
if (a == 1)
return 0;
else //如果不为空
{
QNode* p;//定义一个可以指向节点的指针
p = pq->front->next;//让p指向第一个人所在的节点
pq->front->next = p->next;//让头节点的指针域指向第二个人所在的节点
if (pq->front->next == NULL)//当删完节点,只剩头结点时
pq->rear = pq->front;
*pd = p->data;//传出要删除节点的数据域
free(p);//删除要删除的节点
}
return 1;
}
int GetHead(LinkQueue lq, QNData* pd)//队列为空返回0,不为空读取队头节点的数据域,返回1
{
int a;
a = QueueEmpty(lq);//先判断队列是否为空
if (a == 1)
return 0;
else//如果不为空
*pd = lq.front->next->data;//把剩下两个顾客第一个顾客的数据域返回
return 1;
}
int DestroyQueue(LinkQueue* pq)//摧毁整个队列并删除头结点
{
int a;
PQNode b;//先定义一个可以指向节点的指针
pq->rear = NULL;//让队列末指针指向NULL
do//进行循环依次删去节点
{
b = pq->front;//让指针指向头节点
pq->front = pq->front->next;//移动头节点
free(b);//释放头结点之前的节点
a = QueueEmpty(*pq);//判断是否还有节点
} while (a == 0);//还有节点,继续删除节点直到删完,最后头结点指向NULL
return 1;//操作完成返回1
}
// 构造一个空的线性链表,只有头结点
int InitList(LinkList* pl)
{
LNode* p; // link node pointer 结点指针
p = (LNode*)malloc(sizeof(LNode)); // 生成结点
if (!p) // 生成失败
{
printf("InitList Fail.\n");
return 0;
}
p->next = NULL; // 指针域置为空,头结点数据域不用
pl->head = pl->tail = p; // 作为头结点,插入到链表中
pl->len = 0; // 长度为 0
return 1;
}
// 若线性链表为空表,则返回1,否则返回0。
int ListEmpty(LinkList ll)
{
return (ll.len == 0);
}
// 显示链表
void BrowseList(const LinkList ll)
{
if (ListEmpty(ll)) // 空链表
{
if (ll.head == NULL)
printf("Linklist is non-existent\n\n"); // 没有头结点,链表不存在
else
printf("Empty Linklist\n\n");
return;
}
PLNode p; // 结点指针 也可以定义为 LNode *p;
p = ll.head->next; // 指向第一个结点
do
{
printf("( time:%d ) -> ", p->data.time); // 显示数据域
p = p->next; // 指向下一个结点
} while (p);
printf("\b\b\b \n\n");
}
// 比较两个事件的发生时刻
// 事件 ea 的发生时刻 <、= 或 > 事件 eb 的发生时刻
// 分别返回 -1、0或 1
int cmp(Event ea, Event eb)
{
if (ea.time == eb.time)
return 0;
else
return
(ea.time - eb.time) / abs(ea.time - eb.time);
}
// 将数据按升序插入有序线性链表中
int OrderInsert(LinkList* pl, LNData d, int (*cmp)(LNData, LNData))
{
PLNode p, q; // 也可以写成 LNode *p,*q;
q = pl->head; // q 指向头结点
p = q->next; // p指向第一个结点,如果链表为空,p为 NULL,即 0
// 确定插入的位置,保证整个链表从第一个结点开始,数据域从小到大有序
while (p != NULL && cmp(p->data, d) < 0) // p所指结点不是表尾,且结点的数据域值小于 d
{
q = p; // p q都向后移动 在此过程中 q是前一个结点 p是后一个结点
p = p->next;
}
// 生成新结点 把d作为数据域 插在 q后 、p前 表长加1
PLNode b;
b = (LNode*)malloc(sizeof(LNode)); // 生成结点
if (!b) // 生成失败
{
printf("InitList Fail.\n");
return 0;
}
b->data = d;//把d作为数据域
q->next = b;//插在q后p前
b->next = p;
pl->len = pl->len + 1;//表长加1
// 如果新结点成了尾结点,修改pl->tail
if (b->next == NULL)
pl->tail = b;
// 函数返回 1
return 1;
}
// 删除链表中的第一个结点并带回其数据,若链表为空返回0。
int DelFirst(LinkList* pl, LNData* pd) //
{
if (ListEmpty(*pl)) // 链表空
return 0;
PLNode p; // 也可以定义为 LNode* p;
p = pl->head->next; // 指向第一个结点
pl->head->next = p->next;//让头节点的指针域指向要删去节点的下一个节点
// 删除第一个结点
*pd = p->data;//返回数据
if (pl->tail == p)//如果第一个节点是尾节点在删除前处理尾节点
pl->tail = NULL;
free(p);
return 1;
}
// 将线性链表重置为空表
// 保留头结点
// 释放链表中其它结点的空间
int ClearList(LinkList* pl)
{
PLNode p, q;
if (!ListEmpty(*pl)) // 不是空表
{
q = pl->head->next;//让q指向第一个节点
do//循环删去节点,留下头节点
{
p = q;
q = q->next;//移动q
free(p);
} while (q != NULL);//直到q指向空
}
pl->len = 0;//删完让链表长度变为0
return 1;
}
// 销毁线性链表,同时删除头结点
int DestroyList(LinkList* pl)
{
ClearList(pl);//销毁线性链表
free(pl->head);//删除头结点
pl->head = NULL;//处理头尾节点
pl->tail = NULL;
return 1;
}