山东理工大学计算机学院课程设计（数据结构）班级计升1001班姓名学号1022051029指导教师二○一一年一月二十日课程设计任务书及成绩评定课题名称银行业务模拟系统Ⅰ、题目的目的和要求：1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。

（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。

（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

2、设计题目要求：1. 客户业务分为两种：第一种是申请从银行得到一笔资金，即取款或借款；第二种是向银行投入一笔资金，即存款或还款。

2. 银行有两个服务窗口，相应地有两个队列。

客户到达银行后先排第一个队。

处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足时，则立即排入第二个队等候，直至满足时才离开银行，否则业务处理完后立即离开银行。

3. 每接待完一个第二种业务的客户，则顺序检查和处理第二个队列中的客户,对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。

4.假设检查不需要时间,在此检查过程中,一旦银行资金总额少于或等于刚才第一个队列中最后一个客户(第二种业务)被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查（因为此时已不可能还有满足者）,转而继续接待第一个队列的客户。

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

通过模拟方法求出客户在银行内逗留的平均时间。

Ⅱ、设计进度及完成情况Ⅲ、主要参考文献及资料[1] 严蔚敏数据结构（C语言版）清华大学出版社 1999[2] 严蔚敏数据结构题集（C语言版）清华大学出版社 1999[3] 谭浩强 C语言程序设计清华大学出版社[4] 与所用编程环境相配套的C语言或C++相关的资料Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○一一年一月二十一日目录第一章概述 (1)第二章系统分析 (2)第三章概要设计………………………………………………………第四章详细设计………………………………………………………第五章运行与测试……………………………………………………第六章总结与心得……………………………………………………参考文献………………………………………………………………第一章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。

课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。

《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。

数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。

同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

在这次的课程设计中我选择的题目是银行业务模拟系统。

一般某个银行在某个地区营业前，都要进行市场调查与分析。

通过调查，分析开多少个窗口使效率最高，而且不会产生较大的冗余。

做此项调查通常要花费大量的人力物力，因此我借助计算机系统产生的随机数（时间间隔，每个客户办理的款数以及处理时间）对银行客户的离散事件进行预测，通过银行业务模拟系统计算出客户在银行逗留的总时间并计算出客户在银行的平均逗留时间。

通过计算机模拟的方法减少实际调查的劳动量，资金及时间耗费，轻松的得到高效的方法。

第二章系统分析1．银行业务模拟程序的主要处理对象是“事件”，事件的主要信息是事件的类型和事件的发生时刻。

算法中处理的事件有两类：一类是客户到达事件；另一类是客户离开事件。

前一类事件发生的时刻随客户的到来自然形成；后一类事件发生的时刻由客户办理业务所需时间和等待时间而定。

由于程序驱动是按事件发生时刻的先后顺序进行的，所以事件表应是有序表，其主要操作是插入和删除事件，用一个单链表表示。

2．银行业务模拟程序中需要的另一数据结构是表示客户排队的队列，由于假设银行有2个窗口，因此程序中需要2个队列，队列中有关客户的信息是客户到达的时间和客户办理业务所需要的时间。

队列中的队头客户即为正在窗口办理事务的客户，他办完业务离开队列的时刻影响着即将发生的客户离开事件的时刻，这就是说，对每个队头客户都存在一个将要驱动的客户离开事件。

因此在任何时刻即将发生的事伯只有4种可能：1）新的客户到达；2）队列1队头客户办完业务离开；3）队列1取款客户由于得不到满足而转至队列2；4）队列2队头客户办完业务离开；3. 为了使编写的程序具有通用性，在编程序时将银行的营业时间、初始存款客户办理业务的最长时间及两个客户到达的最大时间间隔都设置成程序运行时动态输入，但是客户办理业务的时间和两个客户到达的时间间隔用随机函数产生的随机数表示。

这样可以对程序进行理性的分析，从而实现真正的模拟。

4. 测试数据。

第三章概要设计1、银行业务模拟程序流程图2、本程序包含三个模块①主程序模块：void main(){输出主界面；选择操作：进入银行业务模拟系统／退出程序；While(进入银行业务模拟窗口)｛OpenForDay();进行初始化操作；输出格式控制；{ 银行业务模拟：while(有要处理的事件时) //有事件可处理{DeQueue1(); //队列1出队列,并用en返回值 if(客户到达)CustomerArrived(); //处理客户到达事件elseCustomerDeparture(); //处理客户离开事件 }计算出客户的平均逗留时间并输出}返回主界面：选择操作：继续进行业务模拟／退出程序；If(选择的是退出)退出程序；｝}②客户到达事件处理模块――实现客户信息队列的抽象数据类型．③客户离开事件处理模块――实现有序事件链表的抽象数据类型3、函数调用关系如图所示：4、设定客户信息队列的抽象数据类型定义:ADT LinkQueue {数据对象: D={ai|ai∈QueueElem,i=1,2,•••,n, n≥0}数据关系: R1={<ai-1,ai>|ai-1,ai∈QueueElem ,i=2,3, •••,n } 基本操作:InitQueue(&Q)操作结果：构造一个空队列。

destroyqueue(&Q)初始条件：队列已存在。

操作结果：销毁队列，此队列不再存在。

EnQueue(&Q,en )初始条件：队列已存在。

操作结果：新元素en入队列。

DeQueue(&Q,&en)初始条件：队列已存在。

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

QueueLength(Q)初始条件：队列已存在。

操作结果：返回队列中元素的个数，即队列长度。

} ADT LinkQueue第四章详细设计#include<stdio.h>#include<stdlib.h>#include <time.h>#include<iostream.h>#define MONEY 5000 //个人业务值,交易额上限#define OK 1#define ERROR 0#define OVERFLOW -2typedef int status;typedef struct{int arrivetime; //到达时间int OccurTime; //事件发生时间int NType; //事件类型，0表示到达事件，1表示离开事件。

同时用1表示存款，2表示取款。

int duration; //办理业务时间long int money;//交易金额}Event,ElemType1;typedef struct{ //等待队列元素 int arrivetime; //到达时间int duration; //办理业务时间 long int money; //交易金额}wait,ElemType2;typedef struct QNode1{ElemType1 data;struct QNode1 *next;}QNode1,*Queue1;typedef struct QNode2{ElemType2 data;struct QNode2 *next;}QNode2,*Queue2;typedef struct{Queue1 front;Queue1 rear;}LinkQueue1;typedef struct{Queue2 front;Queue2 rear;}LinkQueue2;//全局变量long int total_money; //银行现存资金总额int total_time; //客户逗留总时间int use_time;//每个顾客所用时间int money;//每个顾客办理的款数int closetime;//银行营业时间int INTERTIME; //下一用户到达的时间间隔int DURATION; //办理业务所需时间int number; //办理业务的次序int time1; //系统现在时间LinkQueue1 Q1;LinkQueue2 Q2;Event en; //事件wait en1; //列表2元素//初始化队列1status InitQueue1(){Q1.front=Q1.rear=(Queue1)malloc(sizeof(QNode1)); if(!Q1.front)exit(OVERFLOW);Q1.front->next=NULL;return OK;}//初始化队列2status InitQueue2(){Q2.front=Q2.rear=(Queue2)malloc(sizeof(QNode2)); if(!Q2.front)exit(OVERFLOW);Q2.front->next=NULL;return OK;}//销毁队列1status destroyqueue1(){while(Q1.front){Q1.rear=Q1.front->next;free(Q1.front);Q1.front=Q1.rear;}return OK;}//销毁队列2status destroyqueue2(){while(Q2.front){Q2.rear=Q2.front->next;free(Q2.front);Q2.front=Q2.rear;}return OK;}//队列1入队列status EnQueue1(){ Queue1 p,r,r1;p=(Queue1)malloc(sizeof(QNode1));if(!p)exit(OVERFLOW);p->data.arrivetime=en.arrivetime;p->data.OccurTime=en.OccurTime;p->data.NType=en.NType;p->data.duration=en.duration;p->data.money=en.money;r=Q1.front->next;while(r){if(p->data.arrivetime < r->data.arrivetime) { if(r==Q1.front->next){p->next=r;Q1.front->next=p;}else{r1->next=p;p->next=r;}}r1=r;r=r->next;}if(!r){ if(Q1.front->next==NULL) {Q1.front->next=p;Q1.rear=p;Q1.rear->next=NULL;}else{p->next=NULL;Q1.rear->next=p;Q1.rear=p;}}return OK;}//队列2入队列status EnQueue2(){Queue2 p;p=(Queue2)malloc(sizeof(QNode2));if(!p)exit(OVERFLOW);p->data.arrivetime=en1.arrivetime;p->data.duration=en1.duration;p->data.money=en1.money;p->next=NULL;Q2.rear->next=p;Q2.rear=p;return OK;}//若队列1不空，则删除Q1的队头元素，并用en返回其值status DeQueue1(){ Queue1 p;if(Q1.front==Q1.rear) return ERROR;p=Q1.front->next;en.arrivetime=p->data.arrivetime;en.OccurTime=p->data.OccurTime;en.NType=p->data.NType;en.duration=p->data.duration;en.money=p->data.money;Q1.front->next=p->next;if(Q1.rear==p) Q1.rear=Q1.front; //只有一个人时 free(p);return OK;}//若队列2不空，则删除Q2的队头元素，并用en1返回其值status DeQueue2(){ Queue2 p;if(Q2.front==Q2.rear)return ERROR;p=Q2.front->next;en1.arrivetime=p->data.arrivetime;en1.duration=p->data.duration;en1.money=p->data.money;Q2.front->next=p->next;if(Q2.rear==p) Q2.rear=Q2.front; //只有一个人时free(p);return OK;}//营业时间结束，全部客户离开银行void free_system(){destroyqueue1();destroyqueue2();}//产生随机数status rand_ar(int *intertime,long int *money, int *duration,int*NType){*intertime=rand()%INTERTIME+1; //下个客户到达的时间间隔，不大于INTERTIME*money=rand()%MONEY+1; //每个顾客办理的款数，不大于MONEY *duration=rand()%DURATION+1; //客户办理业务所要时间，不大于DURATION*NType=rand()%2; //事件类型分为0和1两种return OK;}void OpenForDay(){ //初始化操作printf(" 请输入银行的初始存款：");scanf("%d",&total_money);printf(" 请输入银行的营业时间（分钟）：");scanf("%d",&closetime);printf(" 请输入最大到达时间间隔（分钟）：");scanf("%d",&INTERTIME);printf(" 请输入最大的处理时间（分钟）：");scanf("%d",&DURATION);total_time=0; //客户逗留总时间（初始值）number=0; //办理业务的次序（初始值）InitQueue1(); //初始化队列1InitQueue2(); //初始化队列2en.arrivetime=0; //到达时间en.OccurTime=0; //事件发生时间en.NType=0; //事件类型，暂时值en.money=0; //交易金额，暂时值en.duration=0; //办理业务时间，暂时值EnQueue1(); //事件进队列}//查找上一离开事件的发生时间int find_leave(){ Queue1 p;int i=0;p=Q1.front->next;while(p!=NULL){if(p->data.NType!=0)i=p->data.OccurTime;p=p->next;}return i;}void CustomerArrived(){int intertime;int i;time1=en.OccurTime;rand_ar(&intertime,&(en.money), &(en.duration),&(en.NType));//设置一离开事件插入事件表en.NType++; //0变1，1变2i=find_leave(); //查找上一离开事件的发生时间if(i==0) //第一位顾客en.OccurTime=en.arrivetime+en.duration;elseif(i>=en.arrivetime)//本事件到达时上一事件还未离开en.OccurTime=i+en.duration; //则此事件的离开时间=上一事件的离开时间+本事件处理时间else //上一事件离开之后，本事件才到达en.OccurTime=en.arrivetime+en.duration;//则此事件的离开时间=本事件到达时间+本事件处理时间EnQueue1();//设置下一用户到达事件插入队列1en.arrivetime=en.arrivetime+intertime; //下一客户到达时间 en.OccurTime=en.arrivetime;en.NType=0; //暂时值en.money=0; //暂时值en.duration=0; //暂时值EnQueue1();}//返回队列2的长度int getlong_q2(){int i=0;Queue2 p;p=Q2.front->next;while(p){i++;p=p->next;}return i;}//顺序检查队列2是否有满足条件者status check_q2(){int i,j,z=0;i=getlong_q2(); //用i返回队列2长度for(j=1;j<=i;j++){DeQueue2(); //队列2出队，用en1返回其值if(en1.money<=total_money) //若队列2出队元素的要交易的金额<=银行现存金额，则可以办理{ if(time1>closetime){printf("--\t\t%d\t\t%d\t\t%d\t\t%d\t%d\n",z,use_time,number,z,( en1.arrivetime),en1.money);}else{time1=time1+en1.duration; //更新系统当前时间 use_time=time1-en1.arrivetime;total_time+=use_time; //更新逗留时间total_money-=en1.money; //更新资金总额number++; //更新实现交易的客户数printf("%ld\t\t%d\t\t%d\t\t%d\t\t%d\t-%d\n",total_money,use_time ,number,time1,(en1.arrivetime),(en1.money));}}else { //若队列2出队元素的要交易的金额>银行现存金额，不能办理if(time1>closetime){printf("--\t\t%d\t\t%d\t\t%d\t\t%d\t%d\n",z,use_time,number,z,( en1.arrivetime),en1.money);}else{EnQueue2(); //继续插入队列2的队尾，继续等待}}}return OK;//队列1离开事件减duration（办理业务时间）int cut_duration(int e) //e即形参办理业务的时间{Queue1 p,q,r;ElemType1 en;p=Q1.front->next;r=Q1.front;if(p){if(p->data.NType!=0){q=p->next;r->next=q; //删除结点en.arrivetime=p->data.arrivetime; //到达时间en.OccurTime=p->data.OccurTime-e; //事件发生时间 en.NType=p->data.NType; //事件类型en.duration=p->data.duration; //办理业务时间en.money=p->data.money; //数额free(p);EnQueue1();}}return OK;void CustomerDeparture(){ int i;i=en.NType; //业务类型，1表示存款，2表示取款time1=en.OccurTime-en.duration;if(i==OK) //是否是办理存款{ if(en.OccurTime>closetime) //营业结束,全部客户离开银行 free_system();else //营业时间没有结束，继续办理{use_time=en.OccurTime-en.arrivetime;total_time+=use_time; //更新逗留的总时间total_money=total_money+en.money; //更新资金总额 number++; //更新服务的客户数time1=en.OccurTime; //更新系统当前时间printf("%ld\t\t%d\t\t%d\t\t%d\t\t%d\t%d\n",total_money,use_time, number,en.OccurTime,en.arrivetime,en.money);check_q2(); //检查队列2是否有满足条件者}}else //办理取款{if(en.money>total_money) //办理取款，当申请金额不能满足时，离开队列1进入队列2等待{ cut_duration(en.duration);//从队列1中删除该结点 en1.arrivetime=en.arrivetime;en1.duration=en.duration;en1.money=en.money;EnQueue2(); //进入队列2继续等待}else //办理取款,当能满足所申请金额时进行队列1{if(en.OccurTime>closetime)//营业结束,全部客户离开银行free_system();else{use_time=en.OccurTime-en.arrivetime;//顾客所用时间=事件发生时间-事件到达时间total_time+=use_time;//更新逗留的总时间 total_money-=en.money; //更新资金总额 time1=en.OccurTime; //更新系统当前时间 number++; //更新客户总数printf("%ld\t\t%d\t\t%d\t\t%d\t\t%d\t-%d\n",total_money,use_time ,number,en.OccurTime,en.arrivetime,en.money);}}}}void main(){cout<<"============================================="<<endl;cout<<" 欢迎使用银行业务模拟系统 \n";cout<<"---------------------------------------------"<<endl;cout<<" 姓名：王宁 "<<endl;cout<<" 学号: 1022051029 "<<endl;cout<<" 班级：计升1班 "<<endl;cout<<"============================================"<<endl;cout<<"请选择开始或退出:"<<endl;cout<<"1.进入银行业务模拟系统"<<endl;cout<<"0.退出程序"<<endl;int n;cin>>n;while(n==1){OpenForDay(); //初始化操作cout<<"---------------------------------------------"<<endl;cout<<"Total_money\tuse_time\tnumber\ten.OccurTime\ten.arrivetime\tmoney"<<endl;{while(Q1.front){DeQueue1(); //队列1出队列,并用en返回值 if(en.NType==0)//en.NType等于0表示客户到达，1表示客户离开CustomerArrived(); //处理客户到达事件elseCustomerDeparture(); //处理客户离开事件，业务类型en.NType等于1表示存款，2表示取款}printf("1.营业结束后银行现存资金总额（元）: %ld\n",total_money) ; printf("2.营业时间内实现交易的客户数（人）: %d\n",number);printf("3.客户在银行逗留的总时间（分钟）: %d\n",total_time); printf("4.客户在银行的平均逗留时间（分钟）:%f\n",(float)total_time/(float)number);cout<<"--------------------------------------"<<endl<<endl;}cout<<"以上为模拟结果!请继续选择继续或退出:"<<endl;cout<<"1.继续模拟"<<endl;cout<<"0.退出程序"<<endl;int n;cin>>n;if(n==0){ cout<<" 谢谢使用本系统，再见!"<<endl; break; } }}第五章运行与测试1、在调试程序的过程中遇到什么问题，是如何解决的？2、设计了那些测试数据？测试结果是什么？1.调试程序过程遇到的问题及解决的方法首先是对指针初始化的问题，一些指针如果不先申请一个新变量就会报错，即使是直接把这个指针赋值为空也要现为其申请一个新的空间。