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

数据结构课程设计报告数据结构课程设计报告 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 选择操作 进入业务模拟窗口 退出程序 选择操作 进入业务模拟窗口 退出程序 进入业务模拟窗口 进入业务模拟窗口 输出业务模拟窗口输出业务模拟窗口 选择操作 银行业务模拟 返回主界面 退出程序 选择操作 银行业务模拟 返回主界面 退出程序 银行业务模拟 银行业务模拟 输入模拟参数 输入模拟参数 输出业务模拟结果窗口输出业务模拟结果窗口 返回主界面 返回主界面 退出程序 退出程序 退出程序 退出程序 客户到达事件处理模块客户到达事件处理模块 实现客户信息队列的抽象数据类型 实现客户信息队列的抽象数据类型 客户离开事件处理模块客户离开事件处理模块 实现有序事件链表的抽象数据类型实现有序事件链表的抽象数据类型 三三 详细设计详细设计 1 有序事件链表类型有序事件链表类型 struct Event 驱动事件驱动事件 int Occurtime 事件发生时间事件发生时间 int NType 事件类型事件类型 Event next typedef Event EventList void InitEVList EventList 事件初始化函数事件初始化函数 int EmptyEV EventList 判断有序链表是否为空判断有序链表是否为空 int cmp Event a Event b 事件发生时间比较函数事件发生时间比较函数 Void OrderInsert EventList 驱动事件按时间有序插入事件链表函数驱动事件按时间有序插入事件链表函数 void DelFirstEV EventList 取出并删除事件链表中的第一个结点取出并删除事件链表中的第一个结点 客户信息队列类型 客户信息队列类型 struct QueueElem 客户信息客户信息 int Arrtime 客户到达时间客户到达时间 int Duration 客户交易时间客户交易时间 int Amount 客户交易金额客户交易金额 QueueElem next struct QueueList 交易客户队列交易客户队列 QueueElem front 队头队头 QueueElem rear 队尾队尾 int Count typedef QueueList QuListArray void InitQuList QueueList 初始化队列函数初始化队列函数 int EmptyQueue QueueList 判断队列是否为空判断队列是否为空 int GetHead QueueList Queue QueueElem 获得队头元素函数获得队头元素函数 void EnQueue QueueList 入队列函数入队列函数 void DelQueue QueueList 出队列函数出队列函数 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 初始化队列函数初始化队列函数 int GetHead QueueList Queue QueueElem 获得队头元素函数获得队头元素函数 void EnQueue QueueList 入队列函数入队列函数 void DelQueue QueueList 出队列函数出队列函数 void InitEVList EventList 事件初始化函数事件初始化函数 int cmp Event a Event b 事件发生时间比较函数事件发生时间比较函数 void OrderInsert EventList 驱动事件按时间有序插入事件链表函数驱动事件按时间有序插入事件链表函数 void OpenForDay EventList 营业模拟初始化函数营业模拟初始化函数 int EmptyQueue QueueList 判断队列是否为空判断队列是否为空 void NextLeaver EventList 确定下一个驱动事件函数确定下一个驱动事件函数 void CustomerArrived EventList 客户到达事件处理函数客户到达事件处理函数 void Min amount QueueList Q 获得等候队列中的客户的最低交易额获得等候队列中的客户的最低交易额 int EmptyEV EventList 判断有序链表是否为空判断有序链表是否为空 void DelFirstEV EventList 取出并删除事件链表中的第一个结点取出并删除事件链表中的第一个结点 void CustomerDeparture EventList 客户离开事件处理函数客户离开事件处理函数 void Leave QuListArray 营业时间结束后全部客户出队列函数营业时间结束后全部客户出队列函数 int PrintMainScreen 输出主界面窗口输出主界面窗口 void PrintMoodScreen 输出业务模拟窗口输出业务模拟窗口 int Output 输出业务模拟结果窗口输出业务模拟结果窗口 部分核心算法的实现 部分核心算法的实现 营业模拟初始化 营业模拟初始化 void OpenForDay EventList 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 Counter i InitQuList q i TotalTime 0 CustomerNum 0 确定下一个驱动事件确定下一个驱动事件 void NextLeaver EventList if Min TotalAmount GetHead q 2 customer while customer Amount TotalAmount 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 EnQueue q 2 customer Min Min CloseTime Tag Event temp CloseTime 1 null OrderInsert EV temp cmp else Event temp en Occurtime customer Duration 1 null OrderInsert EV temp cmp 驱动事件按时间有序插入事件链表驱动事件按时间有序插入事件链表 void OrderInsert EventList 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 Temp next P Q next Temp return Q next Temp Temp next P return else Q next Temp Temp next null return 客户到达事件处理 客户到达事件处理 void CustomerArrived EventList 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 t0 LargeAmount amount else LargeAmount amount if q 1 Count 1 NextLeaver EV en q 客户离开事件处理客户离开事件处理 void CustomerDeparture EventList 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 营业时间结束后全部客户离开银行 营业时间结束后全部客户离开银行 void Leave QuListArray QueueElem customer for i 1 i0 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 且每次从第一队中离开一个客户 第 且每次从第一队中离开一个客户 第 二二 个队列中的客户都要进出队列一次 则个队列中的客户都要进出队列一次 则