学 海 无 涯
理发馆排队系统仿真
一．仿真问题
理发馆一天的工作情况如下：
1） 理发馆有n把理发椅，可同时为n位顾客理发。 2） 理发师不分等级，只要有顾客需要服务，就可理发。 3） 当顾客进门时，只要有理发师有空椅，就可坐下理发，
否则需排队等候。
4） 一旦有理发师的顾客理发完离去，排在对头的顾客便可
开始理发。
5） 若理发馆每天营业T分钟，求：
一天内顾客在理发馆内平均逗留的时间； 顾客排队等候理发的队列长度平均值； 统计每天的营业额。 二．基本要求
1） 模拟理发馆一天的工作过程：必须采用事件驱动的离散
模型；
2） 每个顾客到达和下个顾客到达的时间间隔是随机的； 3） 理发师编号和每天的营业时间由用户输入；
4） 某顾客挑选理发师而不得时，选第一个队列排队等候； 5） 每个顾客进门时都将生成三个随机数：
1>durtime:进门顾客理发所需服务时间（简称理发时间）
1
学 海 无 涯
2>intertime:下个顾客将到达的时间间隔（简称间隔时间） 3>select:服务选项
4>服务收费：包含服务时间；
5>除了输出统计的数据外，还需要显示理发馆的状态； 三．测试数据：用户输入椅子数，营业时间，结合随机数进行测试。
四．实现提示：本题设计两个抽象数据类型，队列抽象数据类型：登录排队等候理发的顾客情况。每个元素应包括顾客进门时刻、理发所需时间。N把椅子对应N个队列。事件链表抽象数据类型：登录顾客进门事件、出门事件。每个事件应包括事件类型（进门事件类型为0，出门事件类型按N把椅子所排队列分为为1、2、...N）和事件发生的时刻occurtime。为便于按事件发生先后顺序逐一处理事件，事件表应按“时刻”有序。对理发椅需要进行编号。 五．问题讨论：
1) 顾客排队前，可以在等待该理发师的各个队列中，选择最短队列。
2） 更进一步,顾客可以选择最快队列（设计选最快的策略）。 3) 可以发挥创造性，采用更直观漂亮的图形方式显示理发馆的状态。 六．程序代码：
#include \"stdlib.h\"
2
学 海 无 涯
#include \"stdio.h\" #include \"conio.h\"
#define MAX 30000 //宏定义 #define TRUE 1 #define FALSE 0 #define R rand()
float wait_length; //int totalnum; //float totaltime; //int curtime; //int chairnum; //int addtime; //typedef struct customer {
int NO; // int intime; // int durtime; int intertime;
int starttime; // int leavetime; // int serve_flag; //}customer;
等待队列的总长度 总共顾客数
顾客理发所需总时间当前时间
当前可用的椅子数 扫尾工作时间 编号
进入理发店时间 开始理发时间 离开理发店的时间 是否在理发 3
学 海 无 涯
customer cus[MAX]; typedef struct Qnode {
int num; //理发者的编号 struct Qnode *next; }Qnode,*QueuePtr; typedef struct {
QueuePtr front; //队头指针 QueuePtr rear; //队头指针 }LinkQueue;
LinkQueue W; //等待队列 void InitQueue(LinkQueue &Q) //队列初始化 {
Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode)); Q.front->next=NULL; }
void outQueue(LinkQueue &Q) //输出队列中的元素 {
QueuePtr p; p=Q.front; while(p->next)
4
学 海 无 涯
{
p=p->next;
printf(\"%d\ }
printf(\" \"); }
int Queue_Length(LinkQueue &Q) //{
int length=0; QueuePtr p; p=Q.front; while(p->next) {
p=p->next; ++length; }
return length; }
void EnQueue(LinkQueue &Q,int e) //尾 {
QueuePtr p;
5
求等待队列的当前长度 将编号为e的顾客插入队学 海 无 涯
p=(QueuePtr)malloc(sizeof(Qnode)); p->num=e; p->next=NULL; Q.rear->next=p; Q.rear=p; }
int DeQueue(LinkQueue &Q) //队头元素出队，并用e返其编号 {
QueuePtr p; int e;
p=Q.front->next; e=p->num;
Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); return e; }
int QueueEmpty(LinkQueue &Q)//判断等待队列是否为空，若空返回1 {
6
学 海 无 涯
return(Q.front==Q.rear? TRUE:FALSE); }
void customer_serve(int n) //为顾客理发 {
cus[n].starttime=curtime; cus[n].leavetime=cus[n].durtime+curtime;
chairnum--; //当前可用理发椅数减1
cus[n].serve_flag=TRUE; }
void customer_in() //顾客进入理发店 {
totalnum++;
cus[totalnum].NO=totalnum;
cus[totalnum].intime=curtime; //记录顾客进入时间
cus[totalnum].durtime=15+R%50; cus[totalnum].intertime=2+R%10; if(QueueEmpty(W) && chairnum>0)
customer_serve(totalnum); //有空闲位置并无人参与竞争，调用服务函数
7
学 海 无 涯
else {
cus[totalnum].serve_flag=FALSE; //否则入队等待 EnQueue(W,totalnum);
wait_length+=Queue_Length(W); //累计队长 } }
void customer_leave(int n) //顾客离开理发店 {
cus[n].serve_flag=FALSE; chairnum++;
totaltime=curtime-cus[n].intime+totaltime; }
void list() //输出 {
float aver_serve_time,aver_wait_len; //顾客平均等待时间，顾客平均等待长度
aver_serve_time=totaltime/totalnum; aver_wait_len=wait_length/totalnum;
printf(\"一天内顾客在理发馆内的平均逗留时间: %f \\n\
8
学 海 无 涯
printf(\"顾客排队等候理发的队列长度平均值: %f \\n\
printf(\"营业时间到点后仍需完成服务的收尾工作时间: %d \\n\
printf(\"一天内的营业额为: %d \\n\}
void main() {
int i,N,T,max;
curtime=0,totaltime=0,totalnum=0,wait_length=0; printf(\"理发店的椅子数: \"); scanf(\"%d\ chairnum=N;
printf(\"请输入营业时间(分钟): \"); scanf(\"%d\ InitQueue(W); customer_in();
while(curtime++for(i=1;i<=totalnum;i++){ //判断有没有人离开
9
学 海 无 涯
if((cus[i].serve_flag==TRUE)&&(cus[i].leavetime==curtime)) customer_leave(i); }
while(chairnum>0 && !QueueEmpty(W)) //让等待队列中的人去理发
customer_serve(DeQueue(W));
if((cus[totalnum].intime+cus[totalnum].intertime)==curtime)
customer_in(); //判断是否有人符合要进的条件 }
while(!QueueEmpty(W)) {
curtime++;
for(i=1;i<=totalnum;i++)
{ //判断有没有人离开
if((cus[i].serve_flag==TRUE)&&(cus[i].leavetime==curtime)) customer_leave(i); }
while(chairnum>0 && !QueueEmpty(W)) //让等待队列中的人去理发
10
学 海 无 涯
customer_serve(DeQueue(W)); }
max=cus[1].leavetime; //求出最后离开的顾客的离开时间 for(i=2;i<=totalnum;i++)
max = max < cus[i].leavetime ? cus[i].leavetime : max; while(curtime++for(i=1;i<=totalnum;i++){
if((cus[i].serve_flag==TRUE)&&(cus[i].starttime+cus[i].durtime==curtime))
customer_leave(i); } }
addtime=max-T; list(); getch(); }
11
学 海 无 涯
12
