第三章:6.栈和队列 -- 离散事件模拟

发布时间:2017-3-28 14:16:28 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"第三章:6.栈和队列 -- 离散事件模拟 ",主要涉及到第三章:6.栈和队列 -- 离散事件模拟 方面的内容,对于第三章:6.栈和队列 -- 离散事件模拟 感兴趣的同学可以参考一下。

前言:

  本节讲述,队列的入队 和 离队行为,由事件决定情况下,是如何实现的。

目录:

  离散事件模拟

正文:

  问题:假设某银行有4个窗口对外接待客户,从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户,因此在客户人数众多时需在每个窗口前顺次排队,对于刚进入银行的客户,如果某个窗口的业务员正空闲,则可上前办理业务,反之,若4个窗口均有客户所占,他便会排在人数最少的队伍后面。现在需要编制一个程序以模拟银行这种业务活动并计算一天中客户在银行逗留的平均时间。

  解题关键:掌握每个客户到达银行和离开银行这两个时刻,两者相减即为客户逗留时间。将逗留时间累加 除以 客户总数量 即为平均逗留时间。

  设:     在这里,每天银行开门的时间点 为 0 ,数字1代表1分钟,每天八小时 即CloseTime 为480, 客户逗留时间 为30分钟以内。两个客户到达 时间间隔 在5分钟以内。

  事件:  模拟程序中,共分为5种事件,1.客户到达事件,2-5.客户分别从四个窗口的离开时间。

  事件结点:

      typedef struct{
          int OccurTime;    //事件发生时间
          int NType;      //事件类型,0:客户到达,i (1-4):客户离开第 i 个窗口
      }Event

  客户节点:

      typedef struct{    
          int OccurTime;            //到达时间
          int Duration;            //办理事务所需时间
      }CustomerNode;

实现代码:

  由于CloseTime = 480 数据量较大,代码运行选取了CloseTime =30 作为示例。

#include<stdio.h>#include<stdlib.h>#include<time.h> #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2//Status是函数的类型,其值是函数结果状态码typedef int Status;//=================================  排队队列定义开始================================typedef struct{        int OccurTime;            //到达时间    int Duration;            //办理事务所需时间}CustomerNode;typedef CustomerNode ElemType;//结点定义typedef struct QNode{    ElemType data;                //数据节点;    struct QNode *next;            //结点的指针域}QNode;//队列链定义typedef struct{    QNode *front;                //队头指针    QNode *rare;                //队尾指针}LinkQueue;//初始化一个空队列Status InitQueue(LinkQueue &Q){    Q.front=Q.rare=(QNode *)malloc(sizeof(QNode));    if(!Q.front) exit(OVERFLOW);    Q.front->next=NULL;    return OK;}//判断是否为空队列Status QueueEmpty(LinkQueue &Q){    if(Q.front==Q.rare)        return TRUE;    return FALSE;} //判断长度Status QueueLength(LinkQueue &Q){    if(Q.front==Q.rare)        return 0;    int i=0;    QNode *q=Q.front;    while(q->next){        q=q->next;        i++;    }    return i;}//向队列尾部插入元素eStatus EnQueue(LinkQueue &Q,ElemType e){    //生成 结点    QNode *q;                        //指向新生成的结点    q=(QNode *)malloc(sizeof(QNode));    if(!q) exit(OVERFLOW);    q->data=e;    q->next=NULL;    Q.rare->next=q;    Q.rare=q;    return OK;}//删除队列头部元素并返回Status DeQueue(LinkQueue &Q,ElemType &e){    if(Q.front==Q.rare) return ERROR;    QNode *q=Q.front->next;    e=Q.front->next->data;    Q.front->next=Q.front->next->next;    if(!Q.front->next)        Q.rare=Q.front;    free(q);    return OK;}void printV(LinkQueue &Q){    if(Q.front==Q.rare)         printf("%s\n","空队列");    QNode *q=Q.front;    while(q->next){        printf("地址:%p",q->next);        printf("值:%d\n",q->next->data);        q=q->next;    }}//=================================  排队队列定义结束 ================================//=================================  事件链表定义开始 ================================typedef struct{    int OccurTime;    int NType;    int dur;}Event,EvElemType;typedef struct LNode{    EvElemType data;                //单链表中结点的数据域    struct LNode *next;                //结点的指针域}LNode,*LinkList;typedef LinkList EventList;void InitList(LinkList &L){    L=(LinkList)malloc(sizeof(LNode));    //生成新节点        if(!L) exit(OVERFLOW);    L->next=NULL;}//在单链表中,取得第i个位置的值必须从头开始找起,因为每个结点元素的位置信息只能通过其直接前继结点确定//获取L 中第i个元素的值,并用 e 返回。Status GetElem_L(LinkList &L,int i,EvElemType &e){    //此处L为带有头结点的单链表    LNode * q;    q=L->next;                    //p指向第一个结点    int j=1;    while(q&&j<i){        //移动指针的错误写法:q++; 因为在链式存储结构中存储地址不一定是连续的        q=q->next;        j++;    }        if(j!=i)        return ERROR;    e=q->data;    return OK;}//时间复杂度为 O(n)//插入元素,在L中第i个位置之前插入数据 eStatus ListInsert_L(LinkList &L,int i,EvElemType e){    //1.找到指向 第 i-1 处元素的指针    LNode * q;    q=L;                                //    q指向头结点    int j=0;    while(q&&j<(i-1)){        q=q->next;                        //后移结点        j++;    }        //正确j的可能值:0,(i-1),      if(!q||i<1)                        //1.q为NULL(i大于表长+1)  2.i不能小于1        return ERROR;    LNode * s;    s=(LinkList)malloc(sizeof(LNode));    //生成新节点            s->data=e;                            //新结点数据域inti    s->next=q->next; q->next=s;            //插入新结点        return OK;}//时间复杂度为 O(n)//按照事件发生的时间点顺序,将事件结点插入事件链表 时间点从小到大排序Status OrderInsert(LinkList &L,EvElemType e){    LNode * q;    q=L;                                //    q指向头结点    if(!q->next){        ListInsert_L(L,1,e);    }else{        while(q->next&&e.OccurTime>=q->next->data.OccurTime){            q=q->next;                        //后移指针        }        LNode * s;        s=(LinkList)malloc(sizeof(LNode));    //生成新节点                s->data=e;                            //新结点数据域inti        s->next=q->next; q->next=s;            //插入新结点                }        return OK;}//删除元素,在L中删除位置为i的元素,并用将返回值存储在e中。Status ListDelete_L(LinkList &L,int i,EvElemType &e){    //1.找到指向 第 i-1 处元素的指针    LNode * q;    q=L;                                //    q指向头结点    int j=0;    while(q&&j<(i-1)){        q=q->next;                        //后移指针        j++;    }    if(!(q->next)||i<1)                        //1.q->next不能为NULL(i位置不存在)  2.i不能小于1        return ERROR;    e=q->next->data;                    //将被删除的值保存在e中    LNode * tem=q->next;                //保存 将被删除元素的坐在位置    q->next=q->next->next;                //删除元素    free(tem);                            //释放被删除元素占用的内存空间    return OK;}//时间复杂度为 O(n)Status ListEmpty(LinkList &L){    if(!L->next)        return OK;    return ERROR;}void printAllValues(LinkList &L){    if(!L->next)        printf("%s\n","此表为空但链表");    LNode *q;    q=L;    while(q->next){        q=q->next;                        //指针后移        printf("地址:%p,",q);        printf("OccurTime:%d,",q->data.OccurTime);        printf("NType:%d\n",q->data.NType);    }}//时间复杂度为 O(n)//=================================  事件链表定义结束 ================================//=================================  银行排队业务模拟程序定义开始 ================================EventList ev;                                //事件链表Event en;                                    //事件结点CustomerNode cn;                                //客户节点LinkQueue q[5];                                //客户队列int CloseTime;                                //银行结束时间int TotalTime,CustomerNum;                    //累计逗留时间 ,累计客户数量void OpenDay(){    TotalTime=0;    CustomerNum=0;    InitList(ev);                            //初始化事件链表    en.OccurTime=0;                            //设置第一个客户到达事件    en.NType=0;    //插入事件    OrderInsert(ev,en);        int i=1;    //初始化任务队列    for(i=1;i<5;i++){        InitQueue(q[i]);    }    }//寻找队伍人数最少的队列。int MinQueue(){    int len=QueueLength(q[1]);    int cur=1;    for(int i=2;i<5;i++){        if(len>QueueLength(q[i])){            len=QueueLength(q[i]);            cur=i;        }    }    return cur;}//客户到达void CustomerArrived(){    ++CustomerNum;                                //增加客户数量    int durTime=rand()%31;                        //产生0-30 间的随机整数,为到达客户等待的时间。    int interTime=rand()%6;                        //产生0-5 间的随机整数,为与下一客户到达时间的时间间隔。        int depT=en.OccurTime+durTime;    int arrT=en.OccurTime+interTime;        //开始排队,找到最短队伍,并加入队伍。    int i=MinQueue();    cn.OccurTime=en.OccurTime;    cn.Duration=durTime;        EnQueue(q[i],cn);    //把当前客户离开事件,加入事件列表    en.OccurTime=depT;    en.NType=i;    en.dur=durTime;    OrderInsert(ev,en);    //下一客户到达事件,加入事件列表。    en.OccurTime=arrT;    en.NType=0;    en.dur=0;    if(en.OccurTime<CloseTime)        OrderInsert(ev,en);        }//客户离开void CustomerDepature(){        int i=en.NType;    CustomerNode c;    DeQueue(q[i],c);                                //删除队列元素(客户离开)    TotalTime+=c.Duration;                            //累加客户业务等待时间}//计算平均逗留时间void CloseDay(){    printf("\n总时间:%d\n",TotalTime);    printf("客户总数量:%d\n",CustomerNum);    printf("平均逗留时间:%d\n",TotalTime/CustomerNum);}                                            //银行排队模拟程序void Bank_Simulation(int CloseTime){    OpenDay();        while(!ListEmpty(ev)){                ListDelete_L(ev,1,en);                        if(en.NType==0){            printf("时间点:%d,客户到达\n",en.OccurTime);                CustomerArrived();                    //客户到来        }else{            printf("时间点:%d,客户离开,",en.OccurTime);                printf("窗口:%d,",en.NType);                printf("等待时间:%d\n",en.dur);            CustomerDepature();                    //客户离开        }            }    CloseDay();                                            //计算平均逗留时间}//=================================  银行排队业务模拟程序定义结束 ================================void main(){    CloseTime=30;    srand((int)time(NULL));    Bank_Simulation(CloseTime);    }

运行结果:

   

上一篇:PMON failed to acquire latch, see PMON dump
下一篇:如何一步一步用DDD设计一个电商网站(九)—— 小心陷入值对象持久化的坑

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款