间（表示不同顾客的不同发式要求）。队列类型的定义为： ADT Linkqueue{
数据对象：D={ai| ai∈ElemSet,i=1,2,??，n.n≥0} 其中ElemSet的元素为一时间二元（Arrivaltime,Duration）, 包括顾客到达时间和预期所需的理发持续时间。
数据关系： R1={〈ai-1,ai〉| ai-1，ai∈D,i=2,??n}约定其中ai为队列头，an端为队列尾。 数据操作：（具体见本书4.3.1节） }ADT LinkQueue
(2)链表抽象数据类型的作用是登录顾客进门或出门的时 间，表中每一项包括事件型（进门或出门）和事件发生的时刻。为了便于按事件的先后次序顺序进行处理，事件表元素应按“时刻”有序。事件链表的抽象数据类型与有序链表基本相同，差别是节点的数据类型。定义为： ADT LinkList {
数据对象：D={ai | ai ElemType i=1,2,?.,n,n≥0}其中ElemType 的元素为一事件2 元组（OccurTime,Ntype）,包括事件发生的时间和事件类型，依事件发生时间OccurTime递增有序。
}ADT LinkList
2．(主程序流程及模块调用关系，包括主函数及各调用子函数流程图)
本程序包含4个模块： 1．主程序模块；
2．实现队抽象数据类型的链表模块；
3．实现理发馆事件抽象数据类型的理发馆事件模块。 4．各模块之间的调用关系如下图所示。
3．(核心的粗线条伪码算法) Simulation {
设定事件表中的第一元素； 置空队；
While(事件表不空){
从事件表中删除发生时刻最早的元素； if (事件类型=0){
//处理顾客进门事件 累计顾客人数；
if(下一顾客到达时刻﹤关门时刻)进门事件插入
事件表；
if（有空闲理发椅）{
新出门事件插入事件表； 累计顾客逗留时间；
}
else {
当前顾客插入队尾；
累计队列长度； } }//if else {
//事件类型=1，处理顾客离开事件 if (队不空){ //删除队头元素；
//记录顾客离开的最晚时间； //新的出门事件插入事件表； //累计顾客逗留时间
}//if
}//else
}//while //计算平均队长； //计算平均逗留时间； //计算收尾工作的时间； }//Simulation
四、详细设计
1．(实现概要设计的数据类型,重点语句加注释)
1、主程序中需要的全程量和数据类型说明： （1）主程序中需要的全程量 EventList ev; //事件表
Event en; //事件
LinkQueue Q; //等候理发的顾客队列 QElemType customer; //顾客记录 int t2,t1;
int Totaltime; //累计时间 int CustomerNum; //累计顾客数
int CloseTime; //关门时机(关门后还要为已进门的顾客理发）
int CurrentChair; //当前空闲的理发椅数 int k;
float Totallength; //累计的顾客排队长度 （2）链表类型： typedef struct{
int OccurTime; //事件发生时刻 int NType; }ElemType,Event;
typedef struct LNode{ //链表结点类型 ElemType data; struct LNode *next; }*Link,*Position; typedef struct { Link head,tail;
int len; Link current; }LinkList;
在事件链表的各种操作中，大部分与一般链表雷同。除一般的链表操作外，有两个特殊的操作，即取事件链表第一结点的数据并删除该结点的算法和按事件发生时间的有序性往事件链表中插入节点的算法。这里仅给出这两个操作实现的算法，其余操作的实现算法见软盘的源程序，此处从略。
void DelFirst(LinkList &L,ElemType &e)
{ //若链表不空，则删除链表的第一个元素并以e带回，且返回OK，否则返回ERROR.
Link p;
if(L.head->next==NULL) return ERROR; //表为空 P=L.head->next; //指针指向表的第一个元素 e.OccurTime=p->data.OccurTime; e.NType=p->data.NType; L.head->next=p->next;
if(L.current==p) L.current=L.head->next; if(L.tail==p) L.tail=L.head; delete p; //删除头元素 L.len--; //表长减1 return OK;
