数据结构课程设计银行业务模拟.doc

数据结构 课程设计报告 班级：191113 学号：20111000611 姓名：黄建钊 指导老师：朱晓莲 日期：2013年3月1. 银行业务模拟1. 需求分析客户的业务分为两种：第一种是申请从银行得到一笔资金，即取款或借款；第二种是向银行中投入一笔资金，即存款或还款。银行有两个服务窗口，相应地有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立刻排入第二个队等候，直至满足时才离开银行；否则业务处理完后立刻离开银行。每接待完一个第二种业务的客户，则顺序检查和处理（如果可能）第二个队列中的客户，对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户（第二种业务）被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查（因为此时已不可能还有能满足者）转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时所有客户立刻离开银行。要求：写一个上述银行业务的事件驱动模拟系统，模拟出并输出系统处理所有客户的流程，并计算出所有客户在银行内逗留的平均时间。2.设计2.1设计思想 本问题主要需要处理两个交易队列（fq，sq）和一个事件队列（eq）。当有客户来交易时，让客户先进队列一fq，然后让事件队列eq记下客户随机产生的到达时间，如果客户办理存款，则更新银行的资金并且记下客户随机产生的逗留时间，办理完后让事件队列记录客户的离开时间，然后从队列一中删除该客户的结点；如果客户办理取款，当银行此刻的金额可以满足该客户，则更新银行的资金并且记下客户随机产生的逗留时间，办理完后让事件队列记录客户的离开时间，然后从队列一中删除该客户的结点，当银行此刻的金额不能够满足该客户，则将该客户转移到队列二等待，直到下一个办理存款的客户办理完存款后，从队列二的头结点开始搜索，看看有没有可以满足其取款的客户，如果队列二的头结点客户能满足，则为其办理取款，然后从队列二中删除该节点，并让事件队列记录该客户的离开时间，如果队列二的头结点客户仍然不能满足，则搜索下一个客户直到将队列二搜索完。等到银行的营业时间到了后，输出事件队列，需要办理两种业务的顾客数，已成功办理两种业务的顾客数，两种业务的成功办理率，客户在银行内的平均逗留时间和下班时银行所剩余的资金总额。实现：输入：用户需要在程序运行开始时输入以下数据：银行初始资金total；银行营业时间closetime；客户交易时间上下界dealmaxtime和dealmintime，用于给随机数产生函数传递参数，产生一个介于这两个值之间的值；客户到达时间间隔上界arrivemaxtime arrivemintime，用于给随机数产生函数传递参数，产生一个介于这两个值之间的值；交易额的最大上限dealMaxMoney.用于给随机函产生函数参数，产生一个介于-dealMaxMoney和dealMaxMoney之间的值，作为顾客到银行办理业务的交易额，。输出：本程序用dos界面模拟输出整个银行业务办理及排队的结果，最后给出一下数据：分别列出需要办理两种业务的顾客数；分别列出已成功办理两种业务的顾客数；分别列出两种业务的成功办理率；客户在银行内的平均逗留时间；下班时银行所剩余的资金总额。（1） 数据结构设计：结构体的定义如下：struct serviceint num; /客户号string type; /到达或离开int beginTime;/到达时间int endTime;/离开时间int money; /正数为存款，负数为取款service* next;/指针域;队列的抽象数据类型定义如下：ADT Queue 数据对象：D ai | aiElemSet, i=1,2,.,n, n0 数据关系：R1 |ai-1, aiD, i=2,.,n 基本操作：void init_Q(Queue &Q);操作结果：构造空队列Qint Q_empty(Queue Q);初始条件：队列Q存在操作结果：若Q为空队列，则返回TRUE,否则FALSEint Q_length(Queue Q);初始条件：队列Q存在操作结果：返回队列Q的元素个数，即队列长度int gethead_Q(Queue Q);初始条件：队列Q存在操作结果：返回队列Q的队头元素void en_Q(Queue &Q,int e);初始条件：队列Q存在操作结果：插入元素e为Q的新的队尾元素。void de_Q(Queue &Q,int &e);初始条件：队列Q存在操作结果：删除Q的队头元素。ADT Queue(2) 算法设计队列类型typedef struct QNode/队列节点类型 int data;struct QNode *next;QNode,*PQNode;typedef struct PQNode front;/队头指针PQNode rear;/队尾指针Queue;队列的基本操作设置如下：void init_Q(Queue &Q);/初始化，构造空队列Q（Q.front=Q.rear）int Q_empty(Queue Q);/若队列Q存在/若Q为空队列，则返回TRUE,否则FALSEint Q_length(Queue Q);/若队列Q存在/返回队列Q的元素个数，即队列长度int gethead_Q(Queue Q);/若队列Q存在/返回队列Q的队头元素void en_Q(Queue &Q,int e);/若队列Q存在/插入元素e为Q的新的队尾元素。void de_Q(Queue &Q,int &e);/若队列Q存在/删除Q的队头元素。其中操作算法：void init_Q(Queue &Q)/初始化，构造空队列Q（Q.front=Q.rear）Q.front=Q.rear=(PQNode)malloc(sizeof(QNode);if(!Q.front)exit(-1); int Q_empty(Queue Q)/若队列Q存在/若Q为空队列，则返回TRUE,否则FALSEif(Q.front=Q.rear)return 1;else return 0;int gethead_Q(Queue Q)/若队列Q存在/返回队列Q的队头元素if(!Q_empty(Q)return Q.front-next-data;else return 0;int Q_length(Queue Q)/若队列Q存在/返回队列Q的元素个数，即队列长度int count=0;PQNode p=Q.front;while(p!=Q.rear)count+;p=p-next;return count;void en_Q(Queue &Q,int e)/若队列Q存在/插入元素e为Q的新的队尾元素。PQNode p=(PQNode)malloc(sizeof(QNode);if(!p)exit(-1);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;void de_Q(Queue &Q,int &e)/若队列Q存在/删除Q的队头元素PQNode p;if(Q.front=Q.rear)return ;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);队列扫描算法伪代码：if(！empry（fq）& fq.head-money0)/如果队列一不空，而且队头客户办理第二种业务/1.可以办,完成离开(即银行现金足够取)/2.不可以办，排队2等候else /存款 ,第一种业务 if(!empty(fq) & temped= searchAndDel(sq,total)/当交易时间到/办理该业务，并开始扫描第二队列，看是否能满足/第二队列需要 if(currentime=next_arrtime )/当当前时间等于即将到来的顾客到来时间，初始化/该顾客节点，并设置下一顾客到达时间其他函数算法int rand_num(int max,int min)/随机数生成/根据传进的max和min，生成介于max和min的一个/整数 randomize(); RandSeed=Now();return ( random(100000) % (max - min + 1) +min ); 2.2设计表示函数调用关系图 Main（） Arrive（） putMoney（） getMoney（） searchAndDeal（） findAndDeal（）详细设计int main()/主函数 printf( *n); printf( *n); printf( *n); printf( * 学院：计算机学院 *n); printf( * *n); printf( * 专业：计算机科学与技术 *n); printf( * *n); printf( * 班级191113 *n); printf( * *n); printf( * 姓名：黄建钊 *n); printf( * *n); printf( * 学号：20111000611 *n); printf( * *n); printf( * *n); printf( * 欢迎进入银行业务模拟系统 *n); printf( * *n); printf( *n); printf( *n); printf( *n); printf(n); printf(n); printf(n); printf(请按任意键继续.n); getch(); int i; for(i=0;ibeginTime = currentTime;/当前时间为客户的到达时间 back(fq)-num = number;/客户号为客户序列号 push(eq,(back(fq)-money); /将产生事件加入事件队列 back(eq)-beginTime = currentTime; back(eq)-type = 到达; back(eq)-num = number; +number;void putMoney()/存款函数 total += front(fq)-money; /更新资金总额 push(eq,front(fq)-money); /加入事件队列 back(eq)-type = 离开; back(eq)-num = front(fq)-num; back(eq)-endTime = (front(fq)-beginTime + rand()%(dealMaxTime-dealMinTime +1)+dealMinTime);/离开时间为到达时间加上随机产生的介于最大处理时间和最小处理时间的处理时间 +counter; /更新客户总数 totalTime += (back(eq)-endTime - front(fq)-beginTime); /更新逗留时间 pop(fq); /删除第一队列第一个业务 currentTimeOfDeal = back(eq)-endTime;/交易时间为客户的离开时间 state =0;/窗口没有交易需要处理void getMoney()/取款函数if( (-fq.head-money) total )/资金短缺 加入第二队列 push( sq,front(fq)-money ); back(sq)-beginTime = front(fq)-beginTime; back(sq)-num = front(fq)-num; pop(fq); elsetotal += back(fq)-money;/更新资金总额 push(eq,front(fq)-money); /加入事件队列 back(eq)-type = 离开; back(eq)-num = front(fq)-num; back(eq)-endTime = (front(fq)-beginTime +rand()%(dealMaxTime-dealMinTime +1)+dealMinTime);/客户的离开时间为客户的到达时间加上随机产生的介于最大处理时间和最小处理时间的处理时间 back(eq)-beginTime = 0; currentTimeOfDeal = back(eq)-endTime;/交易时间为客户的离开时间 +counter; /更新客户总数 totalTime += ( back(eq)-endTime - back(fq)-beginTime ); /更新逗留时间 pop(fq); /删除第一队列第一个业务 state =0;/窗口没有交易需要处理service* searchAndDeal(queue &q,int m)/搜索函数，在对列中寻找可处理元素service* sign = q. head; /标记头节点 service* temp; while(q. head!=NULL )if(-(q. head-money) next; / 首节点后移一位,返回原首节点 return temp;else/队首元首不能被处理if(q. head = q. rear) else/首节点移到队列尾部q. rear-next = q. head; q. rear = q. rear-next; q. head =q. head-next; q. rear-next = NULL;if(q. head = sign)/队列循环一周时停止 return NULL;return NULL;service* temped ;int randomTemp;/void findAndDeal()/处理函数，在对列中寻找可处理元素，对其进行处理while( (temped= searchAndDeal(sq,total)&temped!=NULL ) /查找可处理取款total += temped-money; /更新资金总额 push(eq,temped-money); /加入事件队列 back(eq)-type = 离开; back(eq)-num = temped-num; randomTemp = rand()%(dealMaxTime-dealMinTime +1)+dealMinTime;/处理时间为随机产生的介于最大处理时间和最小处理时间之间的处理时间 back(eq)-endTime = currentTime + randomTemp ;/客户离开时间为当前时间加上处理时间 currentTimeOfDeal += randomTemp;/更新交易时间 +counter; /更新客户总数 totalTime += ( back(eq)-endTime - temped-beginTime ); /更新逗留时间 delete temped; /删除节点 temped = NULL;state = 0;3. 调试分析1.在处理顾客的第一种业务（从银行取出一笔钱）时，我没有特殊处理，仅是和处理第二种一样，即是等到该顾客交易时间结束时才开始判断，如果不够取进入第二队列等候。但题目中有“如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立刻排入第2个队等候，直至满足时才离开银行，否则业务处理完后立刻离开银行”。想想这也是符合实际。于是改算法的判断为以下算法：伪代码：if(！empry（fq）& fq.head-money0)/如果队列一不空，而且队头客户办理第二种业务/1.可以办,完成离开(即银行现金足够取)/2.不可以办，排队2等候else /存款 ,第一种业务 if(!empty(fq) & temped= searchAndDel(sq,total)/当交易时间到/办理该业务，并开始扫描第二队列，看是否能满足/第二队列需要 if(currentime=next_arrtime )/当当前时间等于即将到来的顾客到来时间，初始化/该顾客节点，并设置下一顾客到达时间2. 对于计算客户在银行内的平均逗留时间，一直不成功，后经老师指导，平均逗留时间算法思想如下：已成功交易的客户，逗留时间为他的离开时间和到达时间之差，直到银行营业结束，没有成功交易的客户的逗留时间不算入内，总的逗留时间为每个成功交易的客户的逗留时间之和，平均逗留时间为总的逗留时间除以成功交易的客户数。4. 用户手册用户按任意键继续，则会出现如下主界面：用户选择1开始模拟。按提示输入相应的数据设置，就能得到想要的模拟结果。退出选择0.对用户输入要求如下：1 银行开始的资金总额应该大于零。2 银行开始的资金总额应该大于零。3 银行的营业时间必须小于1440分钟（24小时）。4 最大到达时间间隔必须小于营业时间。5 最小到达时间间隔必须介于零和最大到达时间之间。6 最大处理时间必须小于营业时间。7 最小处理时间必须介于零和最大处理时间之间。8 最大交易额应该小于银行开始时的资金总额且小于程序设置的50000。 如果输入不符合上述要求，程序会提示用户哪里输入出错，可以再次输入。每个输入数据都有3次机会。当三次输入都错的时候，程序停止运行，按任意键退出。现给出最小处理时间出错时的三种提示截图：5.测试数据及测试结果正确输入并开始模拟运行：输入一般数据：a. 银行初始资金total5000b. 银行营业时间closetime50c. 客户到达时间间隔上界arrivemaxtime5和arrivemintime=3客户交易时间上界dealmaxtime8和dealmintime=46. 源程序清单/银行业务模拟系统#include #include #include #include using namespace std;struct serviceint num; /客户号 string type; /到达或离开 int beginTime;/到达时间 int endTime;/离开时间 int money; /正数为存款，负数为取款 service* next;/指针域;struct queue /队列service* head;/队列头指针 service* rear;/队列尾指针;int total; /初始时银行现存资金总额int closeTime; /营业结束时间int arriveMaxTime; /两个到达事件之间的间隔上限int arriveMinTime; /两个到达事件之间的间隔下限int dealMaxTime; /客户之间交易的时间上限int dealMinTime; /客户之间交易的时间下限int dealMaxMoney ; /交易额上限int ndn=0;/需要存款的人数int nwn=0;/需要取款的人数int sdn=0;/成功存款的人数int swn=0;/成功取款的人数int currentTime = 0; /当前时间int totalTime = 0; /客户逗留总时间int counter = 0; /客户总数int number = 1; /初始客户序列号bool state =1; /用于判断是否有窗口在处理int currentTimeOfDeal = 0;/交易时间int thearriveMaxTime = 0;/最大到达时间queue eq; /事件队列queue fq; /队列一queue sq; /对列二/初始化三个队列service* front(queue &q)/返回队首元素return q. head;service* back(queue &q)/返回队尾元素return q. rear;void push(queue &q,int d)/入队列函数，插入元素d为队列q的新的队尾元素service* temp = new service; temp-money = d; temp-next = NULL; if(q.head=NULL)/队列为空，初始化q. head = temp; q. rear = temp; else/队列不为空，插入元素dq. rear-next = temp; q. rear = q.rear-next;void pop(queue &q)/ 若队列不空,出对列函数service* temp; temp = q. head; if(q. head-next=NULL )/对列只有一个元素 q.head = q. rear =NULL; else q. head=q. head-next; delete temp;void arrive()/到达函数，随机产生顾客，进入队列一产生到达事件 进入事件队列push(fq,(rand()% (2*dealMaxMoney) -dealMaxMoney); /随机产生顾客加入第一队列 back(fq)-beginTime = currentTime;/当前时间为客户的到达时间 back(fq)-num = number;/客户号为客户序列号 push(eq,(back(fq)-money); /将产生事件加入事件队列 back(eq)-beginTime = currentTime; back(eq)-type = 到达; back(eq)-num = number; +number;void putMoney()/存款函数 total += front(fq)-money; /更新资金总额 push(eq,front(fq)-money); /加入事件队列 back(eq)-type = 离开; back(eq)-num = front(fq)-num; back(eq)-endTime = (front(fq)-beginTime + rand()%(dealMaxTime-dealMinTime +1)+dealMinTime);/离开时间为到达时间加上随机产生的介于最大处理时间和最小处理时间的处理时间 +counter; /更新客户总数 totalTime += (back(eq)-endTime - front(fq)-beginTime); /更新逗留时间 pop(fq); /删除第一队列第一个业务 currentTimeOfDeal = back(eq)-endTime;/交易时间为客户的离开时间 state =0;/窗口没有交易需要处理void getMoney()/取款函数if( (-fq.head-money) total )/资金短缺 加入第二队列 push( sq,front(fq)-money ); back(sq)-beginTime = front(fq)-beginTime; back(sq)-num = front(fq)-num; pop(fq); elsetotal += back(fq)-money;/更新资金总额 push(eq,front(fq)-money); /加入事件队列 back(eq)-type = 离开; back(eq)-num = front(fq)-num; back(eq)-endTime = (front(fq)-beginTime +rand()%(dealMaxTime-dealMinTime +1)+dealMinTime);/客户的离开时间为客户的到达时间加上随机产生的介于最大处理时间和最小处理时间的处理时间 back(eq)-beginTime = 0; currentTimeOfDeal = back(eq)-endTime;/交易时间为客户的离开时间 +counter; /更新客户总数 totalTime += ( back(eq)-endTime - back(fq)-beginTime ); /更新逗留时间 pop(fq); /删除第一队列第一个业务 state =0;/窗口没有交易需要处理service* searchAndDeal(queue &q,int m)/搜索函数，在对列中寻找可处理元素service* sign = q. head; /标记头节点 service* temp; while(q. head!=NULL )if(-(q. head-money) next; / 首节点后移一位,返回原首节点 return temp;else/队首元首不能被处理if(q. head = q. rear) else/首节点移到队列尾部q. rear-next = q. head; q. rear = q. rear-next; q. head =q. head-next; q. rear-next = NULL;if(q. head = sign)/队列循环一周时停止 return NULL;return NULL;service* temped ;int randomTemp;/void findAndDeal()/处理函数，在对列中寻找可处理元素，对其进行处理while( (temped= searchAndDeal(sq,total)&temped!=NULL ) /查找可处理取款total += temped-money; /更新资金总额 push(eq,temped-money); /加入事件队列 back(eq)-type = 离开; back(eq)-num = temped-num; randomTemp = rand()%(dealMaxTime-dealMinTime +1)+dealMinTime;/处理时间为随机产生的介于最大处理时间和最小