【酷文博分享】大学数据结构上机实习实验报告.doc

班级：0361001学号：2010211686指导老师：刘友军姓名：周承强我的博客：酷文博，好玩的资料，互相交流 数 据 结 构 上 机 实 习 报 告一 实习题目：银行离散事件模拟二 需求分析：为了计算所有客户在银行的平均逗留时间，需要掌握每个客户到达银行和离开银行的时间，后者减去前者即为每个客户在银行的逗留时间。用当天的客户数去除以所有客户的逗留时间之和便是所求的平均逗留时间。三概要设计：数据结构，使用到带头结点链表EvevtList，结点是LNode，提供的操作有：InitList，DelFirst，GetCurElem，GetHead，OrderInsert，此链表用于存放客户的进入或者离开的事件，存放数据包括进入的时间，处理的时间，离开的时间使用一个队列Queue，节点是QNode，队列的数据元素类型为QElemType，提供的主要操作有：InitQueue，QueueEmpty，QueueLength，GetHead，EnQueue，DeQueue，此队列用于模拟进入银行后等待办理业务的客户排队情况。其存储的数据有时间到达的时间和处理事物所需的时间。层次调用关系，包括三个文件：Main.cpp,Queue.h和LinkList.h，后两个用于数据结构的定义，主要的程序在Main.cpp中，从main()进入调用Bank_Simulation(),Bank_Simulation()调用到OpenForDay（），CustomerArrived（）和CustomerDeparture（），CustomerArrived（）调用Random（）和Minimum（）；1. 事件链表的设计typedef struct int OccurTime; int NType; Event,ElemType; typedef struct LNode / 结点类型 ElemType data; LNode *next; *Link,*Position; struct LinkList / 链表类型 Link head,tail; / 分别指向线性链表中的头结点和最后一个结点 int len; / 指示线性链表中数据元素的个数 ;typedef LinkList EventList;2. 队列的设计typedef struct int ArrivalTime; / 到达时刻 int Duration; / 办理事务所需时间 QElemType; / 定义队列的数据元素类型QElemType为结构体类型 typedef struct QNode QElemType data; QNode *next; *QueuePtr; struct LinkQueue QueuePtr front,rear; / 队头、队尾指针 ;3. 主要过程void Bank_Simulation() / 银行业务模拟函数 开门营业； while(有客户进入或者等待办理) / 事件表ev不空 判断应该进行何种操作 若是客户到达 CustomerArrived(); / 处理客户到达事件 若是客户处理结束离开银行 CustomerDeparture(); / 处理客户离开事件 计算平均使用时间输出相关数据 四详细设计：北京信息科技大学 计算机学院 0615233 刘大伟LinkList.h#define Qu 2#define jg 5#define doing 30 #include #include #include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int Status; typedef int Boolean; typedef struct int OccurTime; int NType; Event,ElemType; typedef struct LNode ElemType data; LNode *next; *Link,*Position; struct LinkList Link head,tail; int len; ; typedef LinkList EventList; EventList ev; Event en,et; void InitList(LinkList &L) Link p; p=(Link)malloc(sizeof(LNode); if(p) p-next=NULL; L.head=L.tail=p; L.len=0; else exit(ERROR); Status DelFirst(LinkList &L,Link h,Link &q) 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) return p-data; Status ListEmpty(LinkList L) if(L.len) return FALSE; else return TRUE; Position GetHead(LinkList L) return L.head; void OrderInsert(LinkList &L,ElemType e,int (*comp)(ElemType,ElemType) 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+; if(!p) L.tail=o; Queue.htypedef struct int ArrivalTime; int Duration; QElemType; typedef struct QNode QElemType data; QNode *next; *QueuePtr; struct LinkQueue QueuePtr front,rear; ; void InitQueue(LinkQueue &Q) if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode) exit(OVERFLOW); Q.front-next=NULL; void DestroyQueue(LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; Status QueueEmpty(LinkQueue Q) if(Q.front-next=NULL) return TRUE; else return FALSE; int QueueLength(LinkQueue Q) int i=0; QueuePtr p; p=Q.front; while(Q.rear!=p) i+; p=p-next; return i; Status GetHead(LinkQueue Q,QElemType &e) QueuePtr p; if(Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; return OK; void EnQueue(LinkQueue &Q,QElemType e) QueuePtr p; if(!(p=(QueuePtr)malloc(sizeof(QNode) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; Status DeQueue(LinkQueue &Q,QElemType &e) QueuePtr p; if(Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return OK; Main.cpp#includeLinkList.h#includeQueue.h long int ZongShiJian=0; int CloseTime,YongHuShu=0; LinkQueue qQu;QElemType customer; int cmp(Event a,Event b) 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()%doing+1; i=rand()%(jg+1); int Minimum(LinkQueue Q) int lQu; int i,k=0; for(i=0;iQu;i+) li=QueueLength(Qi); for(i=1;iQu;i+) if(lil0) l0=li; k=i; return k; void CustomerArrived() QElemType f; int durtime,intertime,i; +YongHuShu; Random(durtime,intertime); et.OccurTime=en.OccurTime+intertime; et.NType=Qu; i=Minimum(q); if(et.OccurTimeCloseTime) OrderInsert(ev,et,cmp); 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); void CustomerDeparture() int i; i=en.NType; DeQueue(qi,customer); ZongShiJian+=en.OccurTime-customer.ArrivalTime; if(!QueueEmpty(qi) 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,ev.head,p); en.OccurTime=GetCurElem(p).OccurTime; en.NType=GetCurElem(p).NType; if(en.NType=Qu) CustomerArrived(); else CustomerDeparture(); printf(【该窗口数为】: %d 【两相邻到达客户的时间间隔】: 0%d分钟 【每个客户业务办理时间】: 1%d分钟n,Qu,jg,doing); printf(【客户总数】:%dn,YongHuShu); printf(【所有客户共耗时】:%ld分钟n,ZongShiJian); printf(【平均每人耗时】:%d分钟n,ZongShiJian/YongHuShu); void main() printf( _ 请您输入银行营业【时间长度】(单位:分钟)，确认请按Enter: