数据结构课程设计报告(1)

    题   目:     银行业务模拟系统

                    姓      名:             丘  锋    伟

                    学      号:            2003040140224

    班      级: 计算机科学与技术03级(2)班

                    指导老师:             吴  伟  民

                   完成日期:         2005年6月26日

一.需求分析

1.银行营业初拥有资本为:TotalAmount(元),营业时间为:CloseTime(分钟),这两个模拟参数由测试用户设定.

2.客户业务分为两种: 第一种是申请从银行得到一笔资金,即取款或贷款;第二种是向银行投入一笔资金,即存款或还款.

3.银行有两个服务窗口,相应地有两个队列.客户到达银行先排第一个队.处理每个客户业务时,如果属于第一种,且申请额超出银行现存资金总额而得不到满足时,则立刻排入第二个队等候,直至满足时才离开银行; 否则业务处理完后立刻离开银行.

4.每接待完一个第一种业务的客户,则顺序检查和处理(如果可能)第二个队列中的客户,对能满足的申请者予以满足,不能满足者重新排到第二个队列的队尾.假设检查不需要时间,在此检查过程中,一旦银行资金总额少于或等于刚才第一个队列中最后一个客户(第二种业务)被接待前的数额,或者本次已将第二个队列检查或处理了一遍就停止检查,转而继续接待第一个队列的客户. 

5.任何时刻都只开一个窗口,营业时间结束时所有客户立即离开银行.

二.概要设计

1.设定有序事件链表的抽象数据类型定义:

ADT  EventList {

数据对象: D={ai|ai∈Event,i=1,2,···,n, n≥0}

数据关系: R1={|ai-1,ai∈Event ,ai-1＜ai,i=2,3, ···,n }

基本操作:

        InitEVList(&EV)

        　操作结果：构造一个空的有序事件链表ＥＶ．

EmptyEV(&EV)

初始条件：有序事件链表ＥＶ已存在．

操作结果：若ＥＶ为空，返回１；否则返回０．

cmp(a, b)

        　初始条件：事件a和b已存在．

        　操作结果：若a先发生，返回１；若同时发生，返回０否则返回－１；

OrderInsert(&EV, &en,cmp())

    　初始条件：有序事件链表ＥＶ已存在，en为驱动事件．

    　操作结果：驱动事件按时间有序插入事件链表中．

DelFirstEV(&EV, &en)

初始条件：有序事件链表ＥＶ已存在，en为驱动事件变量．

操作结果：删除ＥＶ中的第一个结点并以en返回其值．

} ADT  EventList

2.设定客户信息队列的抽象数据类型定义:

ADT  QueueList {

数据对象: D={ai|ai∈QueueElem,i=1,2,···,n, n≥0}

数据关系: R1={|ai-1,ai∈QueueElem ,i=2,3, ···,n }

基本操作:

InitQuList(&Queue)

        操作结果：构造一个空队列．

EmptyQueue(&Queue)

    初始条件：队列已存在．

    操作结果：若队列为空，返回１；否则返回０．

GetHead(Queue, &customer)

    初始条件：队列已存在．

    操作结果：若队列不空，则以customer返回队头元素．

EnQueue(&Queue, customer)

    初始条件：队列已存在．

    操作结果：新元素customer入队列．

DelQueue(&Queue, &customer)

    初始条件：队列已存在．

    操作结果：队头元素出队列，并以customer返回其值．

} ADT  QueueList

3.本程序包含三个模块

1主程序模块：

void main()

{  

输出主界面;

选择操作：进入业务模拟窗口／退出程序；

进入业务模拟窗口：

｛

输出业务模拟窗口;

选择操作：银行业务模拟／返回主界面／退出程序；

银行业务模拟：

    ｛

        输入模拟参数；

            输出业务模拟结果窗口;

    　｝

返回主界面：

退出程序：

｝

        退出程序：

｝

②客户到达事件处理模块――实现客户信息队列的抽象数据类型．

③客户离开事件处理模块――实现有序事件链表的抽象数据类型.

三.详细设计

1. 有序事件链表类型

struct Event    //驱动事件

{

       int Occurtime;    //事件发生时间

        int NType;        //事件类型

        Event *next;

};

    typedef Event* EventList;

    void InitEVList(EventList &EV);

//事件初始化函数

int EmptyEV(EventList &EV);

//判断有序链表是否为空

int cmp(Event a,Event b);

//事件发生时间比较函数

Void OrderInsert( EventList &EV, Event &en, int(*cmp) (Event,Event));    

//驱动事件按时间有序插入事件链表函数

void DelFirstEV(EventList &EV,Event &en);

//取出并删除事件链表中的第一个结点

２．客户信息队列类型

struct QueueElem    //客户信息

{

        int Arrtime;    //客户到达时间

        int Duration;    //客户交易时间

        int Amount;    //客户交易金额

        QueueElem *next;

};

struct QueueList    //交易客户队列

{

        QueueElem *front;    //队头

        QueueElem *rear;    //队尾

        int Count;

};

typedef QueueList* QuListArray;

void InitQuList(QueueList &Queue);

//初始化队列函数

int EmptyQueue(QueueList &Queue);

//判断队列是否为空

int GetHead(QueueList Queue,QueueElem &customer);

//获得队头元素函数

void EnQueue(QueueList &Queue,QueueElem customer);

//入队列函数

void DelQueue(QueueList &Queue,QueueElem &customer);

//出队列函数

3．三个宏定义：

    #define Counter 3    

//队列数组的最大值,其中数组[0]置空

#define Max 10000000000        

//设定一个用于比较的最大值

#define null 0

４．定义全局变量：

int CloseTime,TotalAmount0,TotalAmount;    

//银行的营业时间和营业总资本

int TotalTime,CustomerNum0,CustomerNum;    

//客户们在银行花费的累计时间和客户总数

int LargeAmount=0,int DealAmount=0,int UndealAmount1=0,int UndealAmount2=0;

//交易额的最大规模,已处理的交易额规模和队列1,队列2未处理的交易额规模

int DealCustomerNum=0, UndealCustomerNum1=0,int UndealCustomerNum2=0;

//已处理的客户数目和队列1,队列2未处理的客户数目

int Min=Max,Tag=0;    

//等候客户中要交易的最低金额和营业结束标志

５．声明全部函数：　

    void InitQuList(QueueList &Queue);

//初始化队列函数

int GetHead(QueueList Queue,QueueElem &customer);

//获得队头元素函数

void EnQueue(QueueList &Queue,QueueElem customer);

//入队列函数

void DelQueue(QueueList &Queue,QueueElem &customer);

//出队列函数

void InitEVList(EventList &EV);

//事件初始化函数

int cmp(Event a,Event b);

//事件发生时间比较函数

void OrderInsert(EventList &EV,Event &en,int(*cmp)(Event,Event));

//驱动事件按时间有序插入事件链表函数

void OpenForDay(EventList &EV,Event &en,QuListArray &q);

//营业模拟初始化函数

int EmptyQueue(QueueList &Queue);

//判断队列是否为空

void NextLeaver(EventList &EV,Event &en,QuListArray &q);

//确定下一个驱动事件函数

void CustomerArrived(EventList &EV,Event &en,QuListArray &q);

//客户到达事件处理函数

void Min_amount(QueueList Q);

//获得等候队列中的客户的最低交易额

int EmptyEV(EventList &EV);

//判断有序链表是否为空

void DelFirstEV(EventList &EV,Event &en);

//取出并删除事件链表中的第一个结点

void CustomerDeparture(EventList &EV,Event &en,QuListArray &q);

//客户离开事件处理函数

void Leave(QuListArray &q);

//营业时间结束后全部客户出队列函数

int PrintMainScreen();

//输出主界面窗口

void PrintMoodScreen();

//输出业务模拟窗口

int Output();

//输出业务模拟结果窗口

６．部分核心算法的实现：

①    营业模拟初始化：

void OpenForDay(EventList &EV,Event &en,QuListArray &q)

{

    Event *temp;

    temp=new Event;

temp->NType=0;

temp->Occurtime=0;

temp->next=null;

    en=*temp;

    InitEVList(EV);    

    OrderInsert(EV,en,cmp);

for(int i=1;i    TotalTime=0;

    CustomerNum=0;

}

2确定下一个驱动事件

void NextLeaver(EventList &EV,Event &en,QuListArray &q)

{    

    QueueElem customer;

if(Min<=TotalAmount)

        {

            GetHead(q[2],customer);

         while(customer.Amount+TotalAmount<0)

            {

                DelQueue(q[2],customer);

                EnQueue(q[2],customer);

                GetHead(q[2],customer);

            }

         if(en.Occurtime+customer.Duration>=CloseTime)

            {

                Tag++;

                Event temp={CloseTime,2,null};

                OrderInsert(EV,temp,cmp);

            }

            else

            {

                Event temp={en.Occurtime+customer.Duration,2,null};

                OrderInsert(EV,temp,cmp);

            }

        }

    else

        {

            if(GetHead(q[1],customer))//

            {

             while(!EmptyQueue(q[1])&&customer.Amount<0

&&customer.Amount+TotalAmount<0)

                {

                    DelQueue(q[1],customer);

                    EnQueue(q[2],customer);

                 Min=Min<-customer.Amount?Min:-customer.Amount;

                    GetHead(q[1],customer);

                }

                if(!EmptyQueue(q[1]))

                {

                 if(en.Occurtime+customer.Duration>=CloseTime)

                    {

                        Tag++;

                        Event temp={CloseTime,1,null};

                        OrderInsert(EV,temp,cmp);

                    }

                    else

                    {

                        Event temp={en.Occurtime+customer.Duration,1,null};

                        OrderInsert(EV,temp,cmp);

                    }

                }

            }

        }

}

3驱动事件按时间有序插入事件链表

void OrderInsert(EventList &EV,Event &en,int(*cmp)(Event,Event))

{

    Event *P,*Q;

    Event *Temp=new Event;

    *Temp=en;

    P=Q=EV;

P=P->next;

    if(P!=null)

    {

        while(P!=null)

        {

            if(cmp(*P,en)==-1)

            {

P=P->next;

Q=Q->next;

            }

            else if(cmp(*P,en)==1)

            {

Temp->next=P;

Q->next=Temp;

                return;

            }

            else if(cmp(*P,en)==0)

            {

                do

                {

                 P=P->next;

                 Q=Q->next;

                }while(P&&!(cmp(*Q,*P)==-1));

             Temp->next=P;

             Q->next=Temp; //

                return;

            }

        }

Q->next=Temp;

Temp->next=P;

        return;

    }

    else

    {

Q->next=Temp;

Temp->next=null;

        return;

    }

}

4客户到达事件处理： 

void CustomerArrived(EventList &EV,Event &en,QuListArray &q)

{   

    int intertime,durtime,amount,t,a,b;

    srand(time(NULL));

    intertime=1+rand()%30; //下个客户到达的时间间隔，不大于30分钟

dur:

    durtime=1+rand()%30;//客户办理业务所要时间，不大于30分钟

    if(intertime==durtime)goto dur;

    a=rand()%2;

    b=1+rand()%1000;

    amount=a*b+(a-1)*b; //客户的存取金额,不大于1000元

    t=en.Occurtime+intertime;

    Event Temp={t,0,null};

if(t    {

        CustomerNum++;

        OrderInsert(EV,Temp,cmp);

    }

    QueueElem customer={en.Occurtime,durtime,amount,null};

    EnQueue(q[1],customer);

if(amount>0)            //

    {

        LargeAmount+=amount;

    }

    else LargeAmount-=amount;

    if(q[1].Count==1)NextLeaver(EV,en,q);

}

5客户离开事件处理:

void CustomerDeparture(EventList &EV,Event &en,QuListArray &q)

{

    int i=en.NType;

    QueueElem customer;

    DelQueue(q[i],customer);

    TotalTime+=en.Occurtime-customer.Arrtime;

    TotalAmount+=customer.Amount;

if(customer.Amount>0)

    {

        DealAmount+=customer.Amount;

    }

    else DealAmount-=customer.Amount;//

    DealCustomerNum++;

    if(Tag==0)

    {

        if(i==2)Min_amount(q[i]);

        NextLeaver(EV,en,q);

    }

}

6营业时间结束后全部客户离开银行：

void Leave(QuListArray &q)

{

    int i;

    QueueElem customer;

for(i=1;i    {

        while(!EmptyQueue(q[i]))

        {

            DelQueue(q[i],customer);

            TotalTime+=CloseTime-customer.Arrtime;

            if(i==1)

            {

                UndealCustomerNum1++;

             if(customer.Amount>0)

                {

                    UndealAmount1+=customer.Amount;

                }

                else UndealAmount1-=customer.Amount;

            }

            if(i==2)

            {

                UndealCustomerNum2++;

             if(customer.Amount>0)

                {

                    UndealAmount2+=customer.Amount;

                }

                else UndealAmount2-=customer.Amount;

            }

        }

    }

}

７．主函数的实现：

    void main()

{   

loopa:

        if(PrintMainScreen()==1)

        {

loopb:    PrintMoodScreen();

            int i;

            Event en;

            EventList EV;

            QueueList q[Counter];

            QuListArray QuPoint;

            QuPoint=q;

            LargeAmount=0,DealAmount=0,UndealAmount1=0,UndealAmount2=0;

            DealCustomerNum=0,UndealCustomerNum1=0,UndealCustomerNum2=0;

            Min=Max,Tag=0;

            OpenForDay(EV,en,QuPoint);   

            while(!EmptyEV(EV))

            {

                DelFirstEV(EV,en);

                if(en.NType==0)

                {

                    CustomerArrived(EV,en,QuPoint);

                }

                else

                {

                    CustomerDeparture(EV,en,QuPoint);

                }

               }

            Leave(QuPoint);

            i=Output();

            if(i==1)goto loopa;

            if(i==2)goto loopb;

        }

}

四.调试分析

１．调试过程中对部分模拟量作了如下规定：

①客户的存取金额,不大于1000元

②客户办理业务所要时间，不大于30分钟

③下个客户到达的时间间隔，不大于30分钟

当然，系统的模拟性能完全不受这些规定的，用户完全可以根据实际需要作简单的修改和调整．而且以上各模拟量均由随机函数给出，符合离散事件要求．　　

２．算法的时空分析：

    ①基于有序链表的时空分析：

时间复杂度：由于对有序链表操作的主要时间在于插入操作的查找部分，而删除操作不需查找，只是删除第一个结点，故有：Ｔ1(n)=O(n*n).(其中n为进入银行的客户总数.)

空间复杂度：因为每个客户只能产生两个事件:到达事件和离开事件，所以有序链表的总长度不可能超过客户总数的两倍，故有：Ｓ1(n)=O(n). (其中n为进入银行的客户总数.)

    ②基于用户信息队列的时空分析：

时间复杂度：因为每个客户都要且只要进入第一个队列一次，而是否进入第二个队列或是离开则是随机的．作最坏情况打算，设n1为直接离开的客户数，n2为进入第二个队列的客户数，则当n1＝n2＝n/2，且每次从第一队中离开一个客户，第二

个队列中的客户都要进出队列一次，则(n1*n2)|max=n*n/4 ,故有：T2(n)=O(n*n).

    空间复杂度：作最坏打算，假设每个客户都要分别进入第一和第

    　　第二个队列，则两个队列元素的最大个数为客户数量的两倍．故有：S2(n)=O(n).

    ③总的时空分析：

    总的时间复杂度：Ｔ(n)=max(T1(n),T2(n))=O(n*n).

    总的空间复杂度:  S(n)=S1(n)+S2(n).

五.用户手册

1．本程序的运行环境为ＤＯＳ操作系统，执行文件为aaa.exe.

2．进入演示程序后，即显示文本方式的主界面窗口：

3．进入银行业务模拟系统后，显示如下界面窗口：

4．输入模拟参数后，显示如下模拟结果输出界面：

六.测试结果

测试的主要指标包括：

1．银行对客户要求的交易资金的满足率．

2．银行对要求交易的客户的满足率．

3．银行服务对客户平均时间利用率的影响．

下面是以连续模拟时间为480分钟(即８小时)的几个模拟结果：

模拟结果１：(银行营业资本为1000元)

模拟结果２：(银行营业资本为10000元)

模拟结果３：(银行营业资本为100000元)

七.附录

源程序包含的头文件清单：

    #include "iostream.h"

#include "stdlib.h"

#include "time.h"