链表的维护与文件形式的保存

东华理工大学 软件学院 软件工程系1 数据结构与算法课程设计任务书 使用时间 使用时间 2011 2012 学年第学年第 2 学期学期 一 课程设计目的一 课程设计目的 本课程设计的目的就是要达到理论与实际应用相结合 使同学们能够根据数据对象的 特性 学会数据组织的方法 能把现实世界中的实际问题在计算机内部表示出来 并培养 基本的 良好的程序设计技能 二 课程设计题目二 课程设计题目 共 10 题 每个学生一题 单独完成 选法为根据学生所在班级名册的自然顺序 第 1 12 名同学分别做第 1 到第 12 题 然后循环 第 13 24 名同学分别做第 1 到第 12 题 依 次类推 1 银行业务活动的模拟银行业务活动的模拟 任务 假设某银行有 4 个窗口对外接待客户 从早晨银行开门起不断有客户进入银行 由 于每个窗口在某个时刻只能接待一个客户 因此在客户人数众多时需要在每个窗口前顺次 排队 对于刚进入银行的客户 如果某个窗口的业务员正空闲 则可上前输业务 反之 若个窗口均有客户所占 他便会排在为数最少的队伍后面 编制一个程序模拟银行的这种 业务活动并计算一天中客户在银行的平均逗留时间 功能要求 1 实现数据的输入 2 各个窗口数据的访问和输出 3 当前窗口的人员分布情况动态显示 界面要求 有合理的提示 每个功能可以设立菜单 根据提示 可以完成相关的功能要求 存储结构 学生自己根据系统功能要求自己设计 请在最后的上交资料中指明你用到的存 储结构 测试数据 要求使用 1 全部合法数据 2 整体非法数据 3 局部非法数据 进行程序 测试 以保证程序的稳定 测试数据及测试结果请在上交的资料中写明 2 航班订票系统航班订票系统 任务 通过此系统可以实现如下功能 1 录入 可以录入航班情况 数据可以存储在一个数据文件中 数据结构 具体数据自定 2 查询 可以查询某个航线的情况 如 输入航班号 查询起降时间 起飞抵达城市 航班票价 票价折扣 确定航班是否满仓 可以输入起飞抵达城市 查询飞机航班情况 3 订票 订票情况可以存在一个数据文件中 结构自己设定 可以订票 如果该航班已经无票 可以提供相关可选择航班 4 退票 可退票 退票后修改相关数据文件 客户资料有姓名 证件号 订票数量及航班情况 订单要有编号 东华理工大学 软件学院 软件工程系2 5 修改航班信息 当航班信息改变可以修改航班数据文件 要求 根据以上功能说明 设计航班信息 订票信息的存储结构 设计程序完成功能 界面要求 有合理的提示 每个功能可以设立菜单 根据提示 可以完成相关的功能要求 存储结构 学生自己根据系统功能要求自己设计 请在最后的上交资料中指明你用到的存 储结构 测试数据 要求使用 1 全部合法数据 2 整体非法数据 3 局部非法数据 进行程序 测试 以保证程序的稳定 测试数据及测试结果请在上交的资料中写明 3 迷宫问题非递归求解迷宫问题非递归求解 任务 可以输入一个任意大小的迷宫数据 用非递归的方法求出一条走出迷宫的路径 并 将路径输出 要求 在上交资料中请写明 存储结构 基本算法 可以使用程序流程图 源程序 测试 数据和结果 算法的时间复杂度 另外可以提出算法的改进方法 4 链表的维护与文件形式的保存 链表的维护与文件形式的保存 用链表结构的有序表表示某商场家电的库存模型 当有提货或进货时需要对该链表进 行维护 每个工作日结束之后 将该链表中的数据以文件形式保存 每日开始营业之前 需将以文件形式保存的数据恢复成链表结构的有序表 链表结点的数据域包括家电名称 品牌 单价和数量 以单价的升序体现链表的有序 性 程序功能包括 创建表 营业开始 读入文件恢复链表数据 进货 插入 提货 更新或删除 查询信息 更新信息 营业结束 链表数据存入文件 等 5 各种内部排序性能比较各种内部排序性能比较 任务 用程序实现插入法排序 起泡法 选择法 快速法 合并法排序 输入的数据形式为任何一个正整数 大小不限 输出的形式 数字大小逐个递增的数列 功能要求 给出多组不同元素个数的输入数据 可考虑用随机函数生成整数 而不用人工输 入 并用列表打印出每种排序下的各趟排序结果 每个排序法结束时应打印出其元素比较 的次数和交换的次数 此程序需将结果用列表列表打印 一定要将其打印结果排列好 6 基于医院分诊系统的排队策略 基于医院分诊系统的排队策略 1 问题的提出 近年来 随着医疗事业的发展 医院的规模不断扩大 科室门类划分的也越来越 细 随之而来的是病人排队挂号和看病变的繁琐 等待时间变长 为此 需要制定一 种良好的排队策略 减少病人的等待时间 提高医院的服务质量 2 问题的假设 1 我们假设医院实行八小时工作制 一天工作八小时 即 480 分钟 2 医院门诊分为普通号和专家号 普通号一个可是有数为医生 专家号一个可 是仅有一个医生 并且将普通好和专家号相互独立 以方便模拟 3 我们将病人分为 A 类和 B 类 对于 A 类病人 我们仅进行一次诊断 即用户 挂号后进入队列 在进行一次诊断后即完成诊治 B 类病人需要进行两次诊 断和一次检查 在完成一次诊断后 医生开出检查意见 病人进行检查 完 成后病人需返回科室进行第二次诊断 在第二次完成后即完成诊治 4 虽然实际中在一定时间内病人的产生应该按照泊松分布 由于参数设定的困 难 我们将病人的产生使用一般的随机数生成 同理 病人的诊治时间也使 东华理工大学 软件学院 软件工程系3 用确定的时间 5 实际中 每位医生每天接诊的人数是有一定限制的 尤其是专家门诊 但考 虑病人来源的数据无论自实际数据库 还是来自根据实际情况的随机模拟数 据 各类病人的数量都对应了实际的各科室接诊病人的限制 6 对于由于到达时间过晚 部分病人将无法完成诊断 我们将忽略这部分病人 3 两种策略的制定 一级分诊队列模式 每个诊室队列只对应一个诊区候诊队列 我们将之记作 Q 一般排队规则是 刚完成挂号的病人 添加在 Q 的末尾 按医嘱完成体检的病人 直接插入在 Q 的首部 这种排队规则广泛应用于中小医院 二级分诊队列模式 每个诊室队列对应一个诊区候诊队列和一个候诊厅候诊队列 我们将前者记作 Q1 后者记作 Q2 一般情况下 因为诊区空间限制 Q1 的人数限制 在 2 3 人左右 而候诊厅空间较大 所以对 Q2 的人数不作限制 一般排队规则是 刚完成挂号的病人 添加在 Q2 的末尾 按医嘱完成体检的病人 直接插入在 Q2 的首部 医师始终对 Q1 中的首位病人诊治 每位病人诊治结束时 若 Q2 不空 则 Q2 的首位病人脱离 Q2 进入 Q1 的尾部 这种排队规则广泛应用于大中型医院 7 题目 压缩软件的实现 题目 压缩软件的实现 采用哈夫曼编码技术采用哈夫曼编码技术 准备一个文件 统计该文件中各种字符的频率 对各字符进行 Huffman 编码 将该文 件翻译成 Huffman 编码文件 再将 Huffman 编码文件翻译成源文件 8 题目 散列表的设计与实现 题目 散列表的设计与实现 问题描述 设计散列表实现电话号码查找系统 基本要求 1 设每个记录有下列数据项 电话号码 用户名 地址 2 从键盘输入各记录 分别以电话号码和用户名为关键字建立散列表 3 采用一定的方法解决冲突 4 查找并显示给定电话号码的记录 5 查找并显示给定用户名的记录 进一步完成内容 1 系统功能的完善 2 设计不同的散列函数 比较冲突率 3 在散列函数确定的前提下 尝试各种不同类型处理冲突的方法 考察平均查找长度的 变化 9 利用栈求表达式的值 可供小学生作业 并能给出分数 利用栈求表达式的值 可供小学生作业 并能给出分数 要求 建立试题库文件 随机产生 n 个题目 题目涉及加减乘除 带括弧的混合运算 随 时可以退出 保留历史分数 能回顾历史 给出与历史分数比较后的评价 10 学校超市选址问题 带权有向图的中心点 学校超市选址问题 带权有向图的中心点 设计要求 对于某一学校超市 其他各单位到其的距离不同 同时各单位人员去超市的频 度也不同 请为超市选址 要求实现总体最优 11 管道铺设施工的最佳方案选择 管道铺设施工的最佳方案选择 N N 10 个居民之间需要铺设煤气管道 假设任意两个居民之间都可以铺设煤气管道 但代价不同 事先将任意两个居民之间铺设煤气管道的代价存入磁盘文件中 设计一个最 佳方案使得这 N 个居民之间铺设煤气管道所需代价最少 并希望以图形方式在屏幕上输出 结果 东华理工大学 软件学院 软件工程系4 12 利用哈希技术统计 利用哈希技术统计 C 源程序关键字出现频度源程序关键字出现频度 1 题目内容 利用 Hash 技术统计某个 C 源程序中的关键字出现的频度 2 基本要求 扫描一个 C 源程序 用 Hash 表存储该程序中出现的关键字 并统计该程序中的关键字 出现的频度 用线性探测法解决 Hash 冲突 设 Hash 函数为 Hash key key 的第一个字母序号 100 key 的最后一个字母序号 MOD 41 三 课程设计要求 三 课程设计要求 1 1 人一题 且需独立完成 2 每人的设计程序必须为可执行的 exe 文件 且需指导教师验收合格 学生程序必须在课 程设计的最后一天交由指导教师验收合格 过期不再验收程序 如程序验收不合格或在规 定时间内未经指导教师验收 则视为该生程序没有完成 3 每人必须在规定时间内到机房做程序 指导老师将严格考勤 上机期间严禁做与课程设 计无关的事情 指导教师将随时抽查 4 每人必须撰写课程设计报告并上交纸质稿 格式附后 并上交报告电子稿和程序代码 电子稿 每位同学先建立一个文件夹 取名规则为 学号姓名 文件夹里存放上交电子内 容 分别是 学号姓名报告 和 学号姓名程序 每班取一文件夹名 取名规则为班级 号 内放该班同学上交内容 每班学习委员统一收齐后拷贝给指导老师 特别注意 上交 的程序必须是在相应的编程环境下存在的文件 不能是 txt 或 doc 文件等 四 课程设计评分标准 四 课程设计评分标准 1 程序设计质量 占 40 2 课程设计报告质量 占 40 3 平时表现 占 20 附 课程设计报告格式 附 课程设计报告格式 1 需求分析说明 说明为何做该题目 程序最终需要完成的功能 从其需求上说明 2 总体设计 从总体上说明该题目的框架 用文字和图表说明 3 详细设计 对数据结构进行详细的描述 设计好相应数据结构以及其操作功能 要求用 C 设计成类 用文字详细描述每个功能实现的算法及思路 4 实现部分 主要描述程序调试过程 报