数据结构实验报告银行模拟系统实验代码.doc

四、实验步骤（包括主要步骤、代码分析等）l 主要步骤（模块化编程）（1）初始化操作void OpenForDay() int i; InitList(ev); / 初始化事件链表为空 en.OccurTime=0; / 设定第一个客户到达事件 en.NType=Qu; / 到达 OrderInsert(ev,en,cmp); / 插入事件表 for(i=0;iQu;+i) / 置空队列 InitQueue(qi); （2）产生随机数的函数 void Random(int &d,int &i) d=rand()%Blsj+1; / 1到Blsj之间的随机数 i=rand()%Khjg+1; / 1到Khjg之间的随机数 （3）求最短队列的函数 int Minimum(LinkQueue Q) / 返回最短队列的序号 int lQu; int i,k; for(i=0;iQu;i+) li=QueueLength(Qi); k=0; for(i=1;iQu;i+) if(lil0) l0=li; k=i; return k; （4）处理客户到达事件。包括客户数目的累加、生成两个随机数并导出下一个客户到达事件、按升序将下一个客户到达事件插入事件表中、将当前客户插入队列中。 void CustomerArrived() / 处理客户到达事件，en.NType=Qu QElemType f; int durtime,intertime,i; +CustomerNum; Random(durtime,intertime); / 生成随机数 et.OccurTime=en.OccurTime+intertime; / 下一客户到达时刻 et.NType=Qu; / 队列中只有一个客户到达事件 if(et.OccurTimeCloseTime) / 银行尚未关门，插入事件表 OrderInsert(ev,et,cmp); i=Minimum(q); / 求长度最短队列的序号,等长为最小的序号 f.ArrivalTime=en.OccurTime; f.Duration=durtime; EnQueue(qi,f); if(QueueLength(qi)=1) et.OccurTime=en.OccurTime+durtime; et.NType=i; OrderInsert(ev,et,cmp); / 设定第i队列的一个离开事件并插入事件表 （5）处理客户离开事件。主要操作有确定离开事件发生的队列序号、删除队列的排头客户（若删除后队列不空，启动下一个离开事件并插入事件表中）、累加客户的逗留时间。 void CustomerDeparture() / 处理客户离开事件，en.NTyPeQu int i; i=en.NType; DeQueue(qi,customer); / 删除第i队列的排头客户 TotalTime+=en.OccurTime-customer.ArrivalTime; / 累计客户逗留时间 if(!QueueEmpty(qi) / 设定第i队列的一个离开事件并插入事件表 GetHead(qi,customer); et.OccurTime=en.OccurTime+customer.Duration; et.NType=i; OrderInsert(ev,et,cmp); （6）总调试函数和主函数 void Bank_Simulation() Link p; OpenForDay(); / 初始化 while(!ListEmpty(ev) DelFirst(ev,GetHead(ev),p); en.OccurTime=GetCurElem(p).OccurTime; en.NType=GetCurElem(p).NType; if(en.NType=Qu) CustomerArrived(); / 处理客户到达事件 else CustomerDeparture(); / 处理客户离开事件 / 计算并输出平均逗留时间 printf(顾客总数：%d，所有顾客共耗时：%d分钟，平均每人耗时：%d分钟n,CustomerNum,TotalTime,TotalTime/CustomerNum); void main() printf(请输入银行营业时间长度n); scanf(%d,&CloseTime); Bank_Simulation(); l 代码分析/ BankSimulation.cpp 银行业务模拟。 #define Qu 4 / 客户队列数 #define Khjg 5 / 两相邻到达的客户的时间间隔最大值 #define Blsj 30 / 每个客户办理业务的时间最大值 #includeBankSimulation.h#includeLinkList.cpp / 使用已有的链表基本操作#includeLinkQueue.cpp / 使用已有的队列基本操作 typedef struct / 定义ElemType为结构体类型 int OccurTime; / 事件发生时刻 int NType; / 事件类型，Qu表示到达事件,0至Qu-1表示Qu个窗口的离开事件 Event,ElemType; / 事件类型，有序链表LinkList的数据元素类型typedef LinkList EventList; / 事件链表类型，定义为有序链表 typedef struct int ArrivalTime; / 到达时刻 int Duration; / 办理事务所需时间 QElemType; / 定义QElemType(队列的数据元素类型)为结构体类型; / 程序中用到的主要变量(全局)。 EventList ev; / 事件表 Event en; / 事件 Event et; / 临时变量 LinkQueue qQu; / Qu个客户队列 QElemType customer; / 客户记录 int TotalTime=0,CustomerNum=0; / 累计客户逗留时间,客户数(初值为0) int CloseTime; / 银行营业时间(单位是分) int cmp(Event a,Event b) / 依事件a的发生时刻事件b的发生时刻分别返回-1、0或1 if(a.OccurTime=b.OccurTime) return 0; else return (a.OccurTime-b.OccurTime)/abs(a.OccurTime-b.OccurTime); void OpenForDay() / 初始化操作 int i; InitList(ev); / 初始化事件链表为空 en.OccurTime=0; / 设定第一个客户到达事件 en.NType=Qu; / 到达 OrderInsert(ev,en,cmp); / 插入事件表 for(i=0;iQu;+i) / 置空队列 InitQueue(qi); void Random(int &d,int &i) d=rand()%Blsj+1; / 1到Blsj之间的随机数 i=rand()%Khjg+1; / 1到Khjg之间的随机数 int Minimum(LinkQueue Q) / 返回最短队列的序号 int lQu; int i,k; for(i=0;iQu;i+) li=QueueLength(Qi); k=0; for(i=1;iQu;i+) if(lil0) l0=li; k=i; return k; void CustomerArrived() / 处理客户到达事件，en.NType=Qu QElemType f; int durtime,intertime,i; +CustomerNum; Random(durtime,intertime); / 生成随机数 et.OccurTime=en.OccurTime+intertime; / 下一客户到达时刻 et.NType=Qu; / 队列中只有一个客户到达事件 if(et.OccurTimeCloseTime) / 银行尚未关门，插入事件表 OrderInsert(ev,et,cmp); i=Minimum(q); / 求长度最短队列的序号,等长为最小的序号 f.ArrivalTime=en.OccurTime; f.Duration=durtime; EnQueue(qi,f); if(QueueLength(qi)=1) et.OccurTime=en.OccurTime+durtime; et.NType=i; OrderInsert(ev,et,cmp); / 设定第i队列的一个离开事件并插入事件表 void CustomerDeparture() / 处理客户离开事件，en.NTyPeQu int i; i=en.NType; DeQueue(qi,customer); / 删除第i队列的排头客户 TotalTime+=en.OccurTime-customer.ArrivalTime; / 累计客户逗留时间 if(!QueueEmpty(qi) / 设定第i队列的一个离开事件并插入事件表 GetHead(qi,customer); et.OccurTime=en.OccurTime+customer.Duration; et.NType=i; OrderInsert(ev,et,cmp); void Bank_Simulation() Link p; OpenForDay(); / 初始化 while(!ListEmpty(ev) DelFirst(ev,GetHead(ev),p); en.OccurTime=GetCurElem(p).OccurTime; en.NType=GetCurElem(p).NType; if(en.NType=Qu) CustomerArrived(); / 处理客户到达事件 else CustomerDeparture(); / 处理客户离开事件 / 计算并输出平均逗留时间 printf(顾客总数：%d，所有顾客共耗时：%d分钟，平均每人耗时：%d分钟n,CustomerNum,TotalTime,TotalTime/CustomerNum); void main() printf(请输入银行营业时间长度n); scanf(%d,&CloseTime); Bank_Simulation(); 辅助程序代码/ BankSimulation.h (程序名) #include / malloc()等 #include #include / EOF(=Z或F6),NULL #include / atoi() #include / exit()#include / INT_MAX等 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALSE / 带头结点的线性链表类型 typedef struct LNode / 结点类型 ElemType data; LNode *next; *Link,*Position;struct LinkList / 链表类型 Link head,tail; / 分别指向线性链表中的头结点和最后一个结点 int len; / 指示线性链表中数据元素的个数 ; / 单链队列队列的链式存储结构 typedef struct QNode QElemType data; QNode *next; *QueuePtr; struct LinkQueue QueuePtr front,rear; / 队头、队尾指针 ;/Linklist.cppStatus InitList(LinkList &L) / 构造一个空的线性链表 Link p; p=(Link)malloc(sizeof(LNode); / 生成头结点 if(p) p-next=NULL; L.head=L.tail=p; L.len=0; return OK; else return ERROR; Status OrderInsert(LinkList &L,ElemType e,int (*comp)(ElemType,ElemType) / 已知L为有序线性链表，将元素e按非降序插入在L中。（用于一元多项式） Link o,p,q; q=L.head; p=q-next; while(p!=NULL&comp(p-data,e)next; o=(Link)malloc(sizeof(LNode); / 生成结点 o-data=e; / 赋值 q-next=o; / 插入 o-next=p; L.len+; / 表长加1 if(!p) / 插在表尾 L.tail=o; / 修改尾结点 return OK; Status ListEmpty(LinkList L) / 若线性链表L为空表，则返回TRUE，否则返回FALSE if(L.len) return FALSE; else return TRUE; Status DelFirst(LinkList &L,Link h,Link &q) / 形参增加L,因为需修改L / h指向L的一个结点，把h当做头结点，删除链表中的第一个结点并以q返回。 / 若链表为空(h指向尾结点)，q=NULL，返回FALSE q=h-next; if(q) / 链表非空 h-next=q-next; if(!h-next) / 删除尾结点 L.tail=h; / 修改尾指针 L.len-; return OK; else return FALSE; / 链表空 ElemType GetCurElem(Link p) / 已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值 return p-data; Position GetHead(LinkList L) / 返回线性链表L中头结点的位置 return L.head; /LinkQueue.cppStatus InitQueue(LinkQueue &Q) / 构造一个空队列Q if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode) exit(OVERFLOW); Q.front-next=NULL; return OK; int QueueLength(LinkQueue Q) / 求队列的长度 int i=0; QueuePtr p; p=Q.front; while(Q.rear!=p) i+; p=p-next; return i; Status