数据结构指导老师：陈桂玲罗开华 | 193132班 | 201310018422015年1月5日题号：1 题目：银行业务活动的模拟1.需求分析1.客户的业务分为两种：第一种是申请从银行得到一笔资金，即取款或借款；2.第二种是向银行中投入一笔资金，即存款或还款。
银行有两个服务窗口，相应地有两个队列。
客户到达银行后先排第一个队。
3.处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立刻排入第二个队等候，直至满足时才离开银行；否则业务处理完后立刻离开银行。
每接待完一个第二种业务的客户，则顺序检查和处理（如果可能）第二个队列中的客户，对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。
4.注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户（第二种业务）被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查（因为此时已不可能还有能满足者）转而继续接待第一个队列的客户。
任何时刻都只开一个窗口。
假设检查不需要时间。
营业时间结束时所有客户立刻离开银行。
5.要求：模拟银行业务活动，按时间顺序输出业务活动的事件，并求出客户在银行内逗留的平均时间。
2.设计2.1设计思想（1）数据结构设计（采用的结构及原因）本题我采用的是用队列来储存客户数据，用rand函数来提取随值。
（2）算法设计（函数模块及功能，可画流程图）2.2设计表示 （1）关系调用图（2）函数接口规格说明函数调用1.主函数 main2.进栈函数push3.出栈函数pop4.查找和处理函数service* searchAndDel5.到达函数arrive6.存款函数putMoney7.群款函数getMoney8.随机函数rand2.3详细设计（伪码，注释）ADT Queue{数据对象：D={ai∈Elemset i=1,2,…,n,n≥0}数据关系：R1={<ai-1 ai> ai-1 ai∈D,i=2, …,n}约定其中a1端为队列头，an端为队列尾.基本操作：Init Queue(&Q)操作结果：构造一个空队列QQueueEmpty（Q）操作结果：若Q为空队列，则返回TRUE，否则FALSE GetHead(Q &q) EnQueue（&Q q）操作结果：插入元素q为Q的新的队尾素DeQueue(&Q &q);操作结果删除Q的队头元素,并用q返回其值。
3调试分析（时间空间复杂度）银行业务模拟程序，在编译的时候，由于对话框之间的衔接不太懂，所以并没有实现应有的结果。
但后来还是通过学生，上网查询等多种方法，终于弄清了对话框之间的衔接和一些基本算法。
最终也运行出来了。
4.用户手册本程序是在visual sdudio 2012上编译测试的。
5.测试数据及测试结果测试数据：存款10000，时间480，最大时间间隔30，最大处理时间5存款30000，时间360，最大时间间隔10，最大处理时间106.源程序清单#include<iostream>#include<string>using namespace std;int total;int closeTime;int arriveTime;int dealTime;int dealMoney = 5000;int currentTime = 0;int totalTime = 0;int counter = 0;int number = 1; +struct service{int num;string type;int beginTime;int endTime;int money;service* next;};struct queue{service* head;service* rear;};void push(queue &q,int d){service* temp = new service; temp->money = d;temp->next = NULL;if(NULL == q.head){q. head = temp;q. rear = temp;}else{q. rear->next = temp;q. rear = q.rear->next;}}void pop(queue &q){service* temp;temp = q. head;if(NULL ==q. head->next)q.head = q. rear =NULL;elseq. head=q. head->next;delete temp;}service* front(queue &q){return q. head;}service* back(queue &q){return q. rear;}service* searchAndDel(queue &q,int m){service* sign = q. head;service* temp;while(NULL != q. head){if((-(q. head->money)) <m){if(q. head==q.rear){temp = q. head;q. head = q. rear = NULL;return temp;}else{temp = q. head;q. head = q. head->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;}bool state =1;int currentTimeOfDeal = 0;int theArriveTime = 0;queue eq;queue fq;queue sq;void arrive(){push(fq,(rand()% (2*dealMoney) -dealMoney)); 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()%dealTime +1);++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);}else{total += back(fq)->money;push(eq,front(fq)->money);back(eq)->type = "离开";back(eq)->num = front(fq)->num;back(eq)->endTime = (front(fq)->beginTime + rand()%dealTime +1);back(eq)->beginTime = 0;currentTimeOfDeal = back(eq)->endTime;++counter;totalTime += ( back(eq)->endTime - back(fq)->beginTime );pop(fq);state =0;}}service* temped ;int randomTemp;void findAndDeal(){while( (temped= searchAndDel(sq,total))&&NULL != temped ){total += temped->money;push(eq,temped->money);back(eq)->type = "离开";back(eq)->num = temped->num;randomTemp = rand()%dealTime +1;back(eq)->endTime = currentTime + randomTemp ;currentTimeOfDeal += randomTemp;++counter;totalTime += ( back(eq)->endTime - temped->beginTime );delete temped;temped = NULL;}state = 0;}int main(){printf(" ********************************************\n");printf(" * *\n");printf(" * 欢迎进入银行模拟系统 *\n");printf(" * *\n");printf(" ********************************************\n");printf("1.开始模拟 0.退出\n");int n;scanf("%d",&n);while(n==1){srand(NULL);printf("输入银行的初始存款：\n");scanf("%d",&total);printf("输入银行的营业时间：\n");scanf("%d",&closeTime);printf("输入最大到达时间间隔：\n");scanf("%d",&arriveTime);printf("输入最大的处理时间：\n");scanf("%d",&dealTime);theArriveTime +=rand()%arriveTime + 1;while(currentTime < closeTime){++currentTime;if( currentTimeOfDeal < currentTime ) currentTimeOfDeal = currentTime ;if( currentTimeOfDeal == currentTime ) state = 1;if( currentTime == theArriveTime ){arrive();theArriveTime +=rand()%arriveTime +1;}//ifif( 1 == state && NULL != fq.head){if(fq.head->money >= 0){putMoney();findAndDeal();}//ifelsegetMoney();}//if}cout <<endl<< "客户序列"<<"\t" <<"事件类型"<<"\t\t"<<" 时间"<<"\t"<<" 处理金额"<<endl;while( NULL != eq.head){if(eq.head->type=="离开")cout << eq.head->num<<"\t\t"<<eq.head->type<<"\t\t"<<"\t\t"<<eq.head->endTime<<"\t\t"<<eq.head->money<<endl;if(eq.head->type=="到达")cout << eq.head->num<<"\t\t"<<eq.head->type<<"\t\t"<<"\t\t"<<eq.head->beginTime<<"\t\t"<<eq.head->money<<endl;pop(eq);}cout << "未处理客户:" <<""<<endl;while( NULL != fq.head){totalTime += ( closeTime - fq.head->beginTime );cout <<fq.head->num <<" "<<endl ;++counter;pop(fq);}cout <<"客户逗留平均时间为: " << totalTime/counter <<endl;cout<<"银行当前余额："<<total<<endl;break;}return 0;}。