数据结构课程设计1

石家庄经济学院石家庄经济学院 本科生课程设计报告书本科生课程设计报告书 题题 目目 一个银行业务模拟的程序一个银行业务模拟的程序 姓姓 名名 李桂芳李桂芳 学学 号号 407109070617407109070617 学学 院院 信息工程学院信息工程学院 专专 业业 计算机计算机 指导教师指导教师 完成日期 完成日期 2009 6 25 银行业务模拟 一 需求分析 1 程序问题描写 本程序为银行客户业务模拟 其业务模拟分为两种 第一功能是申请从银行得到一 笔资金 即取款或借款 第二功能是向银行投入一笔资金 即存款或还款 银行有两个 服务窗口 相应地有两个队列 2 程序具体实现的功能 1 第一功能 客户到达银行后先排第一个队 处理每个客户业务时 且申请额超出银 行现存资金总额而得不到满足 则立刻排入第二个队等候 直至满足时才离开银行 否 则业务处理完后立刻离开银行 每接待完一个第二种业务的客户 则顺序检查和处理 如 果可能 第二个队列中的客户 对能满足的申请者予以满足 不能满足者重新排到第二个 队列的队尾 2 第二种功能 如果在此检查过程中 一旦银行资金总额小于或等于刚才第一个队列 中最后一个客户 第二种业务 被接待之前的数额 或者本次已将第二个队列检查或处理 了一遍 就停止检查 因为此时已不可能还有能满足者 转而继续接待第一个队列的客户 任何时刻都只开一个窗口 假设检查不需要时间 营业时间结束时所有客户立即离开银 行 3 该程序要求实现银行业务的事件驱动模拟系统 通过模拟方法求出客户在银行内逗 留的平均时间 3 演示程序以用户与计算机交互方式执行 即在计算机终端上显示 提示信息 之后 由用户在键盘上输入演示程序中规定的运算命令 相应的输入数据 滤去输入中的 非法字符 和运算结果显示在其后 4 数据测试 一天营业开始时银行拥有的款额为 10000 元 营业时间为 600 分钟 其他模拟参 量自定 注意测定两种极端的情况 一是两个到达事件之间的间隔时间很短 而客 户的交易时间很长 另一个恰好相反 设置两个到达事件的间隔时间很长 而客户的交 易时间很短 注 测试数据均由程序随机产生 运行数据将在后面使用说明中给出 二 概要设计 1 基本要求 用动态存储结构以及队列来实现 2 所需的数据类型 为实现上述程序功能 应以需要定义单链表的抽象数据类型以及队列集合并还需要 用到结构体 为此 需要两个抽象数据类型 单链表和队列还有结构体声明 1 单链表的抽象数据类型定义为 关于线性表的链表存储结构的本质是 在逻辑上相邻的两个数据元素 ai 1 ai 在 存储地址中可以不相邻 既地址不连续 不同的教材的表示基本是一致的 typedef struct LNode ElemType data 数据子域 struct LNode next 指针子域 LNode 结点结构类型 2 队列的抽象数据类型定义为 用单链表表示的队列 typedef struct QNode QElemType data struct QNode next QNode QueuePtr typedef struct QueuePtr front 头指针 QueuePtr rear 尾指针 LinkQueue InitQueue LinkQueue 2 动态存储模块 外部变量 int close time 600 营业结束时间 主函数模块 函数模块 动态存储结构模块 int totle time 客户呆在银行的总时间 int totle money 0 初始时银行资金总额 int arrivetime 两个事件到达的时间间隔上限 int dealtime 10 客户之间交易时间的上限 int slovetime 交易解决的时间 int currentTime 0 当前时间 int clientnum 0 客户序列号 int totle people 客户总数 int currenttime 处理当前时间 客户变量 struct clientdeal char name 50 客户名 double deposit 存取款金额 int sloveTime 处理需要的时间 int arriveTime 到达时间 距开业的分钟数 int grap 与前一个客户的间隔时间 int waitTime 总的等待时间 int num 用户号 typedef struct Node 建立单链表 clientdeal data Node next LinkNode LinkList typedef struct 单链表表示的队列 Node front 队头 Node rear 队尾 LinkQueue Queue 3 函数模块 各种函数源代码 void InitList LinkList L 建立单链表连 分配空间 int InitQueue LinkQueue Q 初始化队列 int Empty LinkQueue Q 判断队列是否为空 为空返回 1 不为空返回 0 int EnterQueue LinkQueue Q clientdeal x 将客户进行入队 clientdeal DeleteQueue LinkQueue Q 出队函数 LinkList input 输入事件表信息 LinkNode Find LinkList head char name 寻找 定位客户在事件表中的 位置 void Queuetwo LinkList L LinkQueue Q int money 对第二个队的客户 进行业务处理 void dealwith LinkNode L LinkQueue P LinkQueue Q 交易处理 void output LinkList L 输出最后结果 函数模块 建 立 单 链 表 void InitList LinkList L 建立单链表连 分配空间 L LinkList malloc sizeof Node L next 0 队列初始化函数 int InitQueue LinkQueue Q 初始化队列 Q front LinkNode malloc sizeof LinkNode if Q front NULL Q rear Q front Q front next NULL return 1 else return 0 判空函数 int Empty LinkQueue Q 判断队列是否为空 为空返回 1 不为空返回 0 if Q front Q rear return 1 else return 0 入队函数 int EnterQueue LinkQueue Q clientdeal x 将客户进行入队 将数据元素 x 插入到队列 Q 中 Node NewNode NewNode LinkNode malloc sizeof LinkNode 申请新结点 if NewNode NULL NewNode data x NewNode next NULL Q rear next NewNode Q rear NewNode return 1 else return 0 溢出 出队函数 clientdeal DeleteQueue LinkQueue Q 出队函数 将队列 Q 的队头元素出队 并存放到 x 所指的存储空间中 Node p clientdeal M if Q front Q rear return M p Q front next Q front next p next 队头元素 p 出队 if Q rear p 如果队中只有一个元素 p 则 p 出队后成为空队 Q rear Q front M p data free p 释放存储空间 return M 输入事件表信息函数 LinkList input 输入事件表信息 cout 建立事件表 n n n int i 定义 i currenttime 0 当前时间初始值为 0 LinkList head 建立头指针 clientdeal temp 声名客户信息 LinkNode p 建立链表 LinkNode rear 建立队尾指针 InitList 建立队列 rear head 队空 cout 客户之间交易时间的上限 dealtime 分钟 endl cout 早上六点开业 n system pause 任意键开始 srand unsigned time NULL 产生随机时间种子 for i 0 i cout n 产生事件间隔 arrivetime rand max arrivetime 随机两个事件到达的时间间隔上限 currenttime arrivetime 两个事件到达的时间间隔上限给当前时间 if currenttime close time temp grap arrivetime temp arriveTime currentTime clientnum i 1 客户序列号 cout 过了 arrivetime 分钟 endl cout 开业后 currenttime 分钟 第 clientnum 客户到达 endl 产生业务解决所需时间 slovetime rand dealtime temp sloveTime slovetime cout 处理该客户业务需要 slovetime 分钟 endl 输入用户名 cout 请输入该客户的其他信息 endl cout temp name if strcmp temp name exit 0 break 产生存取款金额 并输出 double money cout 输入钱数 money 产生用户所要办理的钱 temp deposit money cout 需要办理的业务 0 cout temp name 请求办理存款 money 元 endl 如果钱数大于 0 则请求办理存款 否则请求办理取款 else cout temp name 请求办理取款 fabs money 元 data temp p next NULL rear next p rear p system pause else cout n cout 时间已到停止办理 endl cout n cout n cout 一天的办理客户业务记录表 endl cout next while p NULL if strcmp p data name name 0 return p 返回值为指向该客户地址 的指针 p p next return NULL 如果没有找到 返回空 第二队业务处理 void Queuetwo LinkList L LinkQueue Q int money 对第二个队的客户进 行业务处理 clientdeal M LinkList s while Empty Q s Find L M name 定位该客户在事件表中的位置 if M arriveTime currentTime s data arriveTime currentTime s data waitTime M sloveTime 计算客户在银行内的停留时间和当前时间 currentTime M arriveTime M sloveTime cout n cout 第 M num 客户 endl cout 用户名为 M name endl cout 到达 data arriveTime 分钟 endl cout 停留 data waitTime 分钟 endl cout currentTime 分钟离开 endl cout data arriveTime currentTime s data waitTime currentTime M arriveTime M sloveTime currentTime currentTime M sloveTime cout n cout 第 M num 客户 endl cout 用户名为 M name endl cout 到达 data arriveTime 分钟 endl cout 停留 data waitTime 分钟 endl cout currentTime 分钟离开 endl cout n else EnterQueue Q M 若钱仍不够该客户需求 则该客户继续留在第二队 cout 第 clientnum 客户 继续留在第二队 next NULL totle people EnterQueue P s next data 统计事件表内的信息 并且将它们 入第一队 s s next s L n s next while Empty P totle money M deposit s Find L M name 找到元素在事件表中的位置 if M arriveTime currentTime 计算等待时间以及当前时间 s data arriveTime currentTime s data waitTime M sloveTime currentTime M arriveTime M sloveTime cout n cout 第 clientnum 客户 到达 data arriveTime 分钟 endl cout 第 clientnum 客户 停留 data waitTime 分 钟 endl cout currentTime 分钟离开 bank endl cout data arriveTime currentTime s data waitTime currentTime M arriveTime M sloveTime currentTime currentTime M sloveTime cout n cout 第 clientnum 客户 到达 data arriveTime 分钟 endl cout 第 clientnum 客户 停留 data waitTime 分 钟 endl cout currentTime 分钟离开 bank endl cout n if Empty Q cout 准备处理第二队中人的业务 fabs M deposit 看钱是否够取走 够则取 不够则入第二队 totle money M deposit s Find L M name s data waitTime M sloveTime currentTime M arriveTime M sloveTime cout n cout 第 clientnum 客户 到达 data arriveTime 分钟 endl cout 第 clientnum 客户 停留 data waitTime 分 钟 endl cout currentTime 分钟离开 endl cout n else M num clientnum EnterQueue Q M 所取的钱数太多 不够取出 入第二队 cout 第 clientnum 客户 继续留在第二队 next 0 计算客户在银行内呆的总时间 totle time s next data waitTime s s next float m static cast totle time static cast totle people 数值类型 转换 cout 一天之内的营业信息如下 endl cout 顾客呆的总时间为 totle time endl cout 一天之内来的总顾客人数为 totle people endl cout 顾客呆的平均时间为 m endl 4 主函数 include bank h 所需要头文件 include 所需要 C 头文件 include stdio h using namespace std main 函数 void main printf n printf 欢迎进入银行模拟系统 n printf n printf 1 开始模拟 0 退出 n int n scanf d while n 1 cout 开始进行业务办理 endl 程序开始 cout 银行每天营业初始资金为 10000 元 每日营业时间为 600 分钟 endl LinkList L LinkQueue P Q P 为第一个队列 Q 为第二个队列 InitQueue 队列初始化 cout After Init P endl InitQueue 队列初始化 cout After Init Q endl L input 建成事件表 函数返回值为事件表的首地址 dealwith L 处理客户请求 首先将客户排入第一队 output L 2 各程序之间调用关系如下 主函数 dealwith Queuetwo output input input 四 调试分析 1 由于对队列以及单链表的算法推敲不足 导致一些小错误出现以及对题目不太理 解导致算法错误和调试结果的不正确 经过老师的帮助和不断阅读题目 最后设计出正 确的代码 2 刚开始时曾忽略了一些变量参数的标识 使调试程序时费时不少 今后应多 注意确定参数的变量和外部变量属性的区分和标识 3 程序的模块划分比较合理 且尽可能将指针的操作封装在动态存储和函数的两个 模块中 致使主函数模块的调试比较顺利 反之 如此划分的模块并非完全合理 因为 在实现队列操作的编码中仍然需要判别指针是否为空 4 算法的时空分析 1 由于程序采用单链表建立队列 并增设头指针和尾指针两个标识 各种操作的算 法时间复杂度比较合理 InitList InitQueue Empty EnterQueue 和 clientdeal DeleteQueue 算法的时间复杂度是 O l input output Queuetwo 和 LinkNode Find 定位客户在事件表中的位置则是 O n 的 dealwith 交易处理函数为 O n n n 为链表长 度 注 各种函数 void InitList LinkList L 建立单链表连 分配空间 int InitQueue LinkQueue Q 初始化队列 int Empty LinkQueue Q 判断队列是否为空 为空返回 1 不为空返回 0 int EnterQueue LinkQueue Q clientdeal x 将客户进行入队 clientdeal DeleteQueue LinkQueue Q 出队函数 LinkList input 输入事件表信息 LinkNode Find LinkList head char name 寻找 定位客户在事件表中 的位置 void Queuetwo LinkList L LinkQueue Q int money 对第二个队的客户进行 业务处理 void dealwith LinkNode L LinkQueue P LinkQueue Q 交易处理 void output LinkList L 输出最后结果 2 表实现的队列各种操作的时间复杂度分析如下 Empty DeleteQueu e EnterQueue Find InitQueue InitList 1 建立单链表连 InitList 函数由于申请空间时一个一个申请不需要太多的时间 因此时间复杂度为 O 1 空间复杂度为 S 1 同理 InitQueue 初始化队列的时间复杂度 为 O 1 空间复杂度为 S 1 2 入队 EnterQueue 函数和 clientdeal DeleteQueue 出队函数由于队列特点为先进 先出 有因为在队尾进 队头出所以时间复杂度为 O 1 空间复杂度为 S 0 判断队 列是否为空 Empty 时间复杂度为 O 1 空间复杂度为 S 0 3 输入事件表信息 input 函数虽然用建立单链表连方法建立事件表 但又利用 FOR 语句实现操作 所以由分析可得时间复杂度为 O n 空间复杂度为 S n 对于 output Queuetwo 和 LinkNode Find 定位客户在事件表中的位置的函数由于都需要先一 个一个判断是否满足函数所规定的要求 应用 WHILE 语句因此需要一个一个判断所以时 间复杂度为 O n 空间复杂度为 S 0 4 dealwith 交易处理函数先要一个一个处理 同时有调用 LinkNode Find 函数以及 Queuetwo 函数又要逐步判断是否为空队 空间复杂度较为复杂 经过分析时间复杂度为 O n n 空间复杂度为 S n n 5 本实习作业采用数据抽象 c 的程序设计方法 将程序划分为三个层次结构 主程序模块 动态存储结构模块 函数模块 使得设计时思路清晰 实现时调试顺利 各模块具有较好的可重用性 经过本次实验充分得到了一次良好的程序设计训练 而且 获得到学多知识例如 srand unsigned time 以及 system 含义以及用法等等也进一步掌握了队列和链表的应用 五 用户手册 1 本程序的运行环绕为 XP 下的程序名为 bank cpp 运行环境为 Microsoft Visual 6 0 C 2 进入演示程序后即显示的用户界面 欢迎进入银行模拟系统 1 开始模拟 0 退出 1 开始进行业务办理 银行每天营业初始资金为 10000 元 每日营业时间为 600 分钟 建立事件表 客户之间交易时间的上限为 10 分钟 交易资金上限为 3000 元 早上六点开业 请按任意键继续 3 按回车键即刻系统时间将随机产生第一个客户到达的时间 以及处理该客户业务 需要时间 再按回车键输入客户名则随机产生需要办理的业务 依次重复操作 4 接受其他命令后即执行相应运算和显示相应结果 六 测试结果 欢迎进入银行模拟系统 1 开始模拟 0 退出 1 开始进行业务办理 银行每天营