数据结构综合实验
1 排队问题仿真
事件表数据类型定义
typedef struct { //数据域 //数据域 int occurTime; // 事件发生时刻 occurTime; char NType; NType; // 事件类型 } ElemType,Event; ElemType,Event; typedef struct Lnode { //链表结点 //链表结点 ElemType data; struct Lnode *next; }*Link,*Position;
数据结构综合实验
1 排队问题仿真
if (freeChair){ // 顾客即刻开始理发，freeChair 的初 顾客即刻开始理发， //值即为 chairNum。 //值即为 chairNum。 dT = en.occurTime + durtime; newDEvent = (dT, ‘D’); // 新的出门事件 MakeNode(newp, newDEvent); LocateElem(evL, newDEvent, compare);
1 排队问题仿真
else { //事件类型=1，处理顾客离开事件 //事件类型 ， 事件类型=1 if（队列不空）{ if（队列不空） 删除队头元素； 删除队头元素； 记录顾客离开的最晚时间； 记录顾客离开的最晚时间； 新出门事件插入事件表； 新出门事件插入事件表； 累计顾客逗留时间； 累计顾客逗留时间； }// if }// else }// while
数据结构综合实验
1 排队问题仿真
主算法详细描述 算法详细描述
BarberShop_Simulation { 设定事件表中的第一个元素 事件表中的第一个元素； 设定事件表中的第一个元素； 置空队列； 置空队列； while （当事件表不空）{ 当事件表不空） 删除事件表中发生时刻最早的元素 事件表中发生时刻最早的元素； 删除事件表中发生时刻最早的元素； if（事件类型=0）{ if（事件类型=0） //处理顾客进门事件 //处理顾客进门 处理顾客进门事件 累计顾客进门人数； 累计顾客进门人数； if（下一个到达时刻<关门时刻） if（下一个到达时刻<关门时刻） 进门事件插入事件表； 进门事件插入事件表；
需求分析
数据结构综合实验
1 排队问题仿真
建立数据模型建立数据模型-数据结构设计
本题目需要两种数据结构： 本题目需要两种数据结构： 链队列： 链队列：登录排队等候理发的顾客情 况，队列中的每个元素应包括顾客进门的 时刻和理发所需的时间。 时刻和理发所需的时间。 链表：登录顾客进门和出门的事件。 链表：登录顾客进门和出门的事件。 表中的元素应包括事件类型， 表中的元素应包括事件类型，还应按事件 发生的先后次序有序。 发生的先后次序有序。
数据结构综合实验
数据结构综合实验
1 银行排队事件模拟 2 迷宫问题
数据结构综合实验
1 排队问题仿真
例1 排队问题 用队列结构可以模拟现实生活中 的很多排队现象， 如车站候车、 的很多排队现象 ， 如车站候车 、 医院 候诊、 候诊 、 银行排队等都可以通过程序进 行仿真模拟， 行仿真模拟 ， 并由此预测客流等多种 经营指标。 下面以理发店为背景， 经营指标 。 下面以理发店为背景 ， 讨 论排队类问题的系统仿真。 论排队类问题的系统仿真。
数据结构综合实验
1 排队问题仿真
问题描述
假设理发店内设有N把理发椅，可同 假设理发店内设有 把理发椅， 把理发椅 时为N位顾客进行理发 顾客进门， 位顾客进行理发。 时为 位顾客进行理发。顾客进门，可能 有两种情况。 有两种情况。 若当时理发店内尚有空闲理发椅， ①若当时理发店内尚有空闲理发椅， 则该顾客可立即入座理发， 则该顾客可立即入座理发，他在店内的逗 留时间即为他理发所需时间； 留时间即为他理发所需时间；
数据结构综合实验
1 排队问题仿真
if (nextAT<closeTime) { newAEvent = ( nextAT, ‘A’); // 新的进门事件 MakeNode(newp, newAEvent); LocateElem(evL, newAEvent, compare); Insafter(evL, newp); // 插入事件表 }
数据结构综合实验
1 排队问题仿真
② 否则需要排队候理 ， 则他在店内的 否则需要排队候理， 逗留时间应为他理发所需时间和排队等候 的时间之和。 的时间之和。 一旦有顾客理完发离去时， 一旦有顾客理完发离去时 ， 排在对头 的顾客便开始理发。 的顾客便开始理发 。 顾客的到达时间和理 发所需时间均可随机生成，并约定， 发所需时间均可随机生成 ， 并约定 ， 过了 营业时间顾客不再进门， 营业时间顾客不再进门 ， 但仍需继续为已 进入店内的顾客理发， 进入店内的顾客理发 ， 直至最后一名顾客 离开为止。 离开为止。
数据结构综合实验
1 排队问题仿真
事件链表结构定义
typedef struct { Link head,tail; // 头、尾指针 head,tail; int length; // 链表长度 Link current; //当前指针 //当前指针 } Link List; typedef LinkList EventList; //事件链表类型，定义为有序链表 事件链表类型， 事件链表类型
主算法设计
数据结构综合实验
1 排队问题仿真
生成“顾客理发所需时间 durtime” 生成“顾客理发所需时间 durtime” 和 “下一顾客到达的时间间隔 intertime” 两个 intertime” 随机数可从 语言的随机数函数得到。 可从C 随机数可从C语言的随机数函数得到。 occurtime， 假设当前事件发生的时刻为 occurtime， 则下一顾客进门事件发生的时刻则为 则下一顾客进门事件发生的时刻则为 occurtime + intertime。 intertime。 该顾客在当前时刻开始理发，经过 该顾客在当前时刻开始理发， durtime 时间之后便可离开理发馆，则应发 时间之后便可离开理发馆， 生时刻为 occurtime + durtime 。
数据结构综合实验
1 排队问题仿真
排队问题主算法描述
主算法是以处理顾客进门事件 主算法是以处理顾客进门事件和顾客离 顾客进门事件和 开事件为线索进行的 为线索进行的。 开事件为线索进行的。 void BarberShop_Simulation( int chairNum, BarberShop_Simulation( chairNum, int closeTime ) { // 理发店馆业务模拟 // chatrNum 为假设的理发馆的 //规模closeTime 为营业时间 //规模 规模closeTime OpenForDay; OpenForDay; // 初始化
数据结构综合实验
1 排队问题仿真
计算平均队列长度； 计算平均队列长度； 计算平均逗留时间； 计算平均逗留时间； }// BarberShop_Simulation
数据结构综合实验
1 排队问题仿真
void CustomerArrived(eventList evL, Queue CustomerArrived( evL, Q, Event en ) { // 处理顾客进门事件 Random(durtime, intertime); Random(durtime, intertime); nextAT = en.occurTime + intertime; intertime; // 下一顾客到达时刻， evL 为事件表，表 下一顾客到达时刻， 为事件表， //中的第1个事件为(0,‘A’)。durtime 为当 //中的第 个事件为(0,‘A’)。 中的第1 //前进门的顾客理发所需时间，intertime //前进门的顾客理发所需时间 前进门的顾客理发所需时间， //为下一个顾客即将进门的间隔时间。 //为下一个顾客即将进门的间隔时间 为下一个顾客即将进门的间隔时间。
数据结构综合实验
1 排队问题仿真
if（有空闲理发椅）{ if（有空闲理发椅） 出门事件插入事件表； 新出门事件插入事件表； 累计顾客逗留时间 顾客逗留时间； 累计顾客逗留时间； } else{ 当前顾客插入队尾； 当前顾客插入队尾； 累计队列长度； 累计队列长度； } }// if
数据结构综合实验
数据结构综合实验
1 排队问题仿真
default : Invalid; }//switch }//while CloseForDay; CloseForDay; //计算平均逗留时间和排队的平均长度 //计算平均逗留时间和排队的平均长度 }//BarberShop_Simulation }//BarberShop_Simulation
数据结构综合实验
1 排队问题仿真
链队列结构定义 链队列结构定义
typedef struct { QueuePtr front; // 头指针 QueuePtr rear; // 尾指针 } LinkQueue; LinkQueue;
数据结构综合实验
1 排队问题仿真
假设进门事件类型 假设进门事件类型为’ A’，出门事件类型 进门事件类型为 ’D’。 为’D’。为便于按事件发生的先后次序顺序进 行处理，事件表应按发生的“时刻”有序。 行处理，事件表应按发生的“时刻”有序。 实际问题中，顾客进门的时刻和理发所 实际问题中， 需要的时间都是随机的。 需要的时间都是随机的。假设第一个顾客进 门的时刻为0 门的时刻为0。之后每个顾客进门的时刻在 前一个顾客进门时设定， 前一个顾客进门时设定，即以两个顾客之间 的时间间隔来确定下一个顾客的到达时间。 的时间间隔来确定下一个顾客的到达时间。
数据结构综合实验
ห้องสมุดไป่ตู้
1 排队问题仿真