数据结构A课程设计指导书-改后.doc

数据结构数据结构 A 课程设计指导书课程设计指导书 计算机与信息工程学院计算机与信息工程学院 一 设计目的一 设计目的 熟悉各种数据结构和运算 会使用数据结构的基本操作解决一些实际问题 二 设计要求二 设计要求 在本课程设计过程中要求学生 1 重视课程设计环节 用严谨 科学和踏实的工作态度对待课程设计的每一项任务 2 按照课程设计的题目要求 独立地完成各项任务 严禁抄袭 凡发现抄袭 抄袭 者与被抄袭者皆以零分计入本课程设计成绩 凡发现实验报告或源程序雷同 涉及的 全部人员皆以零分计入本课程设计成绩 3 认真编写课程设计报告 课程设计报告的书写格式及要求见附录 2 三 设计步骤三 设计步骤 1 问题分析和任务定义 2 数据类型和系统设计 3 编码实现和静态检查 4 上机调试 5 总结和整理课程设计说明书 四 考核方式和成绩评定四 考核方式和成绩评定 考核分为两个部分 程序运行情况 按规定时间到机房运行程序 由教师检查运行情况 针对自己的 程序 学生能熟练清楚地回答教师的问题 课程设计说明书 是否按规定书写课程设计说明书的各项内容 课程设计成绩采用五级分制五级分制 100 程序运行情况 60 课程设计说明书 40 五 上交相关内容要求五 上交相关内容要求 上交时间 最后一次课 验收程序时 纸质版 课程设计说明书 内容与电子版完全一致 具体要求见电子版说明 电子版 压缩包上传到 ftp 命名 学号姓名 必须由以下部分组成 缺一不可 1 源程序 学生按照课程设计的具体要求所开发的所有源程序 放到一个文件夹中 2 说明文件 保存在 doc 中 在说明文档中应该写明上交程序所在的目录 上交程 序的主程序文件名 如果需要安装 要有程序的安装使用说明 3 课程设计说明书 保存在 word 文档中 文件名要求 按照 学号 姓名 课程设计 说明书 命名 如文件名为 101 张三 课程设计说明书 doc 根据 附录 1 数据结构课程 设计的具体内容 的题目要求 完成课程设计说明书 内容按照如下几个方面展开 格式 见 附录 2 课程设计说明书规范 1 需求分析 需求分析 1 程序的功能 2 输入输出的要求 3 测试数据 2 概要设计 概要设计 包括程序设计组成框图 程序中使用的存储结构设计说明 如果指定存储结构请 写出该存储结构的定义 3 详细设计 详细设计 包括模块功能说明 如函数功能 入口及出口参数说明 函数调用关系描述等 每个模块的算法设计说明 可以是描述算法的流程图 4 调试分析 调试分析 测试数据 测试输出的结果 分析时间复杂度 思考每个模块在设计和调试时存 在的问题及解决方案 问题是哪些 问题如何解决 算法的改进设想 5 核心源程序清单和执行结果 核心源程序清单和执行结果 源程序要按照写程序的规则来编写 要结构清晰 重点函数的重点变量 重点功 能部分要加上清晰的程序注释 程序清单中应有足够的注释描述问题和功能设计 通过一系列的程序执行结果截图 展示程序的所有功能 附录 1 数据结构课程设计的具体内容 本次课程设计完成如下模块 共 15 个模块 见题目分配表 确定自己题目 1 信号放大器信号放大器 1 问题描述问题描述 天然气经过管道网络从其生产基地输送到消耗地 在传输过程中 其性能的某一个或 几个方面可能会有所衰减 例如气压 为了保证信号衰减不超过容忍值 应在网络中的合 适位置放置放大器以增加信号 例如电压 使其与源端相同 设计算法确定把信号放大器 放在何处 能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值 2 基本要求基本要求 1 建立模型 设计数据结构 2 设计算法完成放大器的放置 3 分析算法的时间复杂度 3 设计思想设计思想 为了简化问题 假设分布网络是二叉树二叉树结构 源端是树的根结点 信号从一个结点流 向其孩子结点 树中的每一结点 除了根 表示一个可以用来放置放大器的位置 图5是一 个网络示意图 边上标出的是从父结点到子结点的信号衰减量 对于网络中任一结点 i 设 d i 表示结点 i 与其父结点间的衰减量 D i 为从结点 i 到 结点 i 的子树中任一叶子结点的衰减量的最大值 并有如下递推公式 在此公式中 要计算某结点的 D 值 必须先计算其孩子结点的 D 值 因而必须后序遍后序遍 历二叉树历二叉树 当访问一个结点时 计算其 D 值 例如 D B max D D d D D E d E 4 若容忍值为 3 则在 B 点或其祖先 的任意一点放置放大器 并不能减少 B 与其后代的衰减量 必须在 D 点放置一个放大器或 在其孩子结点放置一个或多个放大器 若在结点 D 处放置一个放大器 则 D B 2 根据上述分析 设计如下存储结构 A B C DE FG HI JK 1 3 12 22 21 22 图 5 网络分布示意图 D i 0 若 i 为叶子结点 D i max D j d j 若 i 不是叶子结点且 j 是 i 的孩子 struct element int D 该结点的衰减量 int d 父结点的衰减量 bool boost 当且仅当本处设置放大器 则boost为true struct BiNode element data BiNode lchild rchild 计算并放置放大器的伪代码为 计算并放置放大器的伪代码为 1 D i 0 2 for i 的每个孩子 j 2 1 如果 D j d j 容忍值 则在 j 处放置放大器 2 2 否则 D i max D i D j d j 思考题思考题 本题假设分布网络是一棵二叉树结构 如果是树结构应如何设计算法 2 迷宫问题 迷宫问题 迷宫求解是实验心理学中的一个经典问题 心理学家把一只老鼠从一个无顶盖的大盒 子的入口处赶进迷宫 迷宫中设置很多隔壁 对前进方向形成了多处障碍 心理学家在迷 宫的唯一出口处放置了一块奶酪 吸引老鼠在迷宫中寻找通路以到达出口 例如 图 2 所 示为一个迷宫示意图 其中双边矩形表示迷宫 1 代表有障碍 0 代表无障碍 2 基本要求基本要求 1 设计数据结构存储迷宫 0123456789 01111111111 11011101111 21101011111 31010000011 41011101111 51100110001 61011001101 71111111111 入口 1 1 出口 6 8 图 2 迷宫示意图 其中 1 代表有障碍 0 代表无障碍 前进的方向有八个 分别是上 下 左 右 左上 左下 右上 右下 2 设计存储结构保存从入口到出口的通路 3 设计算法完成迷宫问题的求解 4 分析算法的时间复杂度 3 设计思想设计思想 可以采用回溯法回溯法实现该问题的求解 回溯法是一种不断试探及时纠正错误的搜索方法 从入口出发 按某一方向向前探索 若能走通 未走过的 即某处可以到达 则到达新点 否则试探下一方向 若所有的方向均没有通路 则沿原路返回前一点 换下一个方向再继 续试探 直到所有可能的通路都搜索到 或找到一条通路 或无路可走又返回到入口点 在求解过程中 为了保证在任何位置上都能沿原路退回 需要一个后进先出的栈栈来保 存从入口到当前位置的路径 可以将迷宫定义成一个二维数组二维数组 则每个点有 8 个试探方向 如当前点的坐标是 x y 与其相邻的 8 个点的坐标都可根据与该点的相邻方位而得到 规定试探顺序为顺时针方向 将这 8 个方向的坐标增量放在一个结构数组 move 8 中 在 move 数组中 每个元素由两个 域组成 x 表示横坐标增量 y 表示纵坐标增量 这样会很方便地求出从某点 x y 按某一 方向 v 0 v 7 到达新点 i j 的坐标 i x move v x j y move v y 算法用伪代码描述如下 1 栈初始化 2 将入口点坐标 x y 及该点的方向 d 设为 1 入栈 3 当栈不空时循环执行下述操作 3 1 x y d 栈顶元素出栈 3 2 求出下一个要试探的方向 d 3 3 沿顺时针试探每一个方向 执行下述操作 3 3 1 如果方向 d 可走 则 3 3 1 1 将 x y d 入栈 3 3 1 2 求新点坐标 i j 3 3 1 3 将新点 i j 切换为当前点 x y 3 3 1 4 若 x y 是终点 则算法结束 否则 重置 d 0 3 3 2 否则 试探下一个方向 d 3 TSP 问题问题 1 问题描述问题描述 所谓 TSP 问题是指旅行家要旅行 n 个城市 要求各个城市经历且仅经历一次 并要求 所走的路程最短 该问题又称为货郎担问题 邮递员问题 售货员问题 是图问题中最广 为人知的问题 2 基本要求基本要求 1 上网查找 TSP 问题的应用实例 2 分析求 TSP 问题的全局最优解的时间复杂度 3 设计一个求近似解的算法 4 分析算法的时间复杂度 3 设计思想设计思想 对于 TSP 问题 一种最容易想到的也肯定能得到最佳解的算法是穷举法 即考虑所有 可能的旅行路线 从中选择最佳的一条 但是用穷举法求解 TSP 问题的时间复杂度为 n 当 n 大到一定程度后是不可解的 本实验只要求近似解求近似解 可以采用贪心法求解 任意选择某个城市作为出发点 然后前 往最近的未访问的城市 直到所有的城市都被访问并且仅被访问一次 最后返回到出发点 为便于查找离某顶点最近的邻接点 可以采用邻接矩阵邻接矩阵存储该图 算法用伪代码描述 如下 1 任意选择某个顶点 v 作为出发点 2 执行下述过程 直到所有顶点都被访问 2 1 v 最后一个被访问的顶点 2 2 在顶点 v 的邻接点中查找距离顶点 v 最近的未被访问的邻接点 j 2 2 访问顶点 j 3 从最后一个访问的顶点直接回到出发点 v 4 医院选址问题 医院选址问题 1 问题描述问题描述 n 个村庄之间的交通图可以用有向网图来表示 图中边上的权值表示从村庄 i 到 村庄 j 的道路长度 现在要从这 n 个村庄中选择一个村庄新建一所医院 问这所医院应建 在哪个村庄 才能使所有的村庄离医院都比较近 2 基本要求基本要求 1 建立模型 设计存储结构 2 设计算法完成问题求解 3 分析算法的时间复杂度 3 设计思想设计思想 医院选址问题实际是求有向图中心点有向图中心点的问题 首先定义顶点的偏心度 设图 G V E 对任一顶点 k 称 E k max d i k i V 为顶点 k 的偏心度 显然 偏心度最小的顶点即为图 G 的中心点 如图 7 a 所示是一个带权有向图 其各顶点的偏心度如图 b 所示 医院选址问题的算法用伪代码描述如下 1 对加权有向图 调用 Floyd 算法算法 求每对顶点间最短路径长度的矩阵 2 对最短路径长度矩阵的每列求大值 即得到各顶点的偏心度 3 具有最小偏心度的顶点即为所求 思考题思考题 图的存储结构和算法的设计需要一定的灵活性和技巧 从医院选址问题的 求解过程 你有什么感想 5 机器调度问题 机器调度问题 1 问题描述问题描述 机器调度是指有 m 台机器需要处理 n 个作业 设作业 i 的处理时间为 ti 则对 n 个作 业进行机器分配 使得 1 一台机器在同一时间内只能处理一个作业 2 一个作业不能同时在两台机器上处理 3 作业 i 一旦运行 则需要 ti个连续时间单位 设计算法进行合理调度 使得在 m 台机器上处理 n 个作业所需要的处理时间最短 2 基本要求基本要求 1 建立问题模型 设计数据结构 2 设计调度算法 为每个作业分配一台可用机器 3 给出分配方案 3 设计思想设计思想 假设有七个作业 所需时间分别为 2 14 4 16 6 5 3 有三台机器 编号分别为 m1 m2和 m3 这七个作业在三台机器上进行调度的情形如图 9 所示 阴影区代表作业的 运行区间 作业 4 在 0 到 16 时间被调度到机器 1 上运行 在这 16 个时间单位中 机器 1 完成了对作业 4 的处理 作业 2 在 0 到 14 时间被调度到机器 2 上处理 之后机器 2 在 14 到 17 时间处理作业 7 在机器 3 上 作业 5 在 0 6 时间完成 作业 6 在 6 11 时间完成 作业 3 在 11 15 时间完成 作业 1 在 15 17 时间完成 注意到作业 i 只能在一台机器上 从 si时刻到 si ti时间完成且任何机器在同一时刻仅能处理一个作业 因此最短调度长度为 ab c d e 1 2 5 32 1 4 顶点偏心度 a b 6 c 8 d 5 e 7 a b 图 7 带权有向图及各顶点的偏心度 17 在上述处理中 采用了最长时间优先 最长时间优先 LPT 的简单调度策略 的简单调度策略 在 LPT 算法中 作业 按其所需时间的递减顺序排列递减顺序排列 在分配一个作业时 将其分配给最先变为空闲的机器 下面设计完成下面设计完成 LPT 算法的存储结构 算法的存储结构 为每个机器设计数据类型 struct MachineNode int ID 机器号 int avail 机器可用时刻 为每个作业设计数据类型 struct JobNode int ID 作业号 int time 处理时间 LPT 算法用伪代码描述如下 1 如果作业数 n 机器数 m 则 1 1 将作业 i 分配到机器 i 上 1 2 最短调度长度等于 n 个作业中处理时间最大值 2 否则 重复执行以下操作 直到 n 个作业都被分配 2 1 将 n 个作业按处理时间建成一个大根堆 H1 2 2 将 m 个机器按可用时刻建立一个小根堆 H2 2 3 将堆 H1 的堆顶作业分配给堆 H2 的堆顶机器 2 4 将 H2 的堆顶机器加上 H1 的堆顶作业的处理时间重新插入 H2 中 m1 m2 m3 时间 分配 作业作业 5作业作业 6 作业作业 3 作业作业 1 作业作业 2 作业作业 7 作业作业 4 17 16 图 9 三台机器的调度示例 654 2 5 将堆 H1 的堆顶元素删除 3 堆 H2 的堆顶元素就是最短调度时间 6 运动会分数统计 运动会分数统计 1 问题描述问题描述 参加运动会有 n 个学校 学校编号为 1 n 比赛分成 m 个男子项目 和 w 个女子项 目 项目编号为男子 1 m 女子 m 1 m w 不同的项目取前五名或前三名积分 取前 五名的积分分别为 7 5 3 2 1 前三名的积分分别为 5 3 2 哪些取前五名或前 三名由学生自己设定 n 20 m w 20 2 2 基本要求基本要求 1 可以输入各个项目的前三名或前五名的成绩 2 能统计各学校总分 3 可以按学校编号 学校总分 男女团体总分排序输出 4 可以按学校编号查询学校某个项目的情况 可以按项目编号查询取得前三或前五名 的学校 规定 输入数据形式和范围 20 以内的整数 如果做得更好可以输入学校的名称 运 动项目的名称 输出形式 有中文提示 各学校分数为整型 界面要求 有合理提示 每个功能可以设立菜单 根据提示 可以完成相关的功能要 求 存储结构存储结构 学生自己根据系统功能要求自己设计 但是要求运动会的相关数据要存储 在数据文件数据文件中 数据文件的数据读写方法等相关内容在 c 语言程序设计的书上 请自 学解决 请在最后的上交资料中指明你用到的存储结构 测试数据 要求使用 1 全部合法数据 2 全部非法数据 3 局部非法数据 进行 程序测试 以保证程序的稳定 测试数据及测试结果请在上交的资料中写明 7 模拟网上模拟网上订票系统订票系统 1 问题描述问题描述 通过此系统可以实现如下功能 1 录入 可以录入航班情况 数据存储能在一个数据文件数据文件中 数据结构 具体数据自定 2 查询 可以查询某个航线的情况 可以输入航班号 查询起降时间 起飞抵达城市 航班票价 票价折扣 确定航班是 否满仓 可以输入起飞抵达城市 查询飞机航班情况 3 订票 订票情况能存在一个数据文件中 结构自己设定 可以按航班号订票 如果该航班已经无票 可以提供相关可选择航班 可以按起飞抵达城市订票 订票信息包含订单编号 客户姓名 证件号 航班情况 4 退票 可退票 退票后修改相关数据文件 5 修改航班信息 当航班信息改变可以修改航班数据文件 2 基本要求基本要求 根据以上功能说明 设计航班信息 订票信息的存储结构 设计程序完成功能 8 停车场管理 停车场管理 1 问题描述问题描述 设停车场内只有一个可停放 n 辆汽车的狭长通道 且只有一个大门可供汽车进出 汽 车在停车场内按车辆到达时间的先后顺序 依次由北向南排列 大门在最南端 最先到达 的第一辆车停放在车场的最北端 若车场内已停满 n 辆汽车 则后来的汽车只能在门外 的便道上等候 一旦有车开走 则排在便道上的第一辆车即可开入 当停车场内某辆车要 离开时 在它之后开入的车辆必须先退出车场为它让路 待该辆车开出大门外 其它车辆 再按原次序进入车场 每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交 纳费用 试为停车场编制按上述要求进行管理的模拟程序 2 基本要求基本要求 以栈栈模拟停车场 以队列队列模拟车场外的便道 按照从终端读入的输入数据序列进行模 拟管理 每一组输入数据包括三个数据项 汽车 到达 或 离去 信息 汽车牌照号码 及到达或离去的时刻 对每一组输入数据进行操作后的输出数据为 若是车辆到达 则输 出汽车在停车场内或便道上的停车位置 若是车离去 则输出汽车在停车场内停留的时间 和应交纳的费用 在便道上停留的时间不收费 栈以顺序结构顺序结构实现 队列以链表链表实现 3 测试数据测试数据 设 n 2 输入数据为 A 1 5 A 2 10 D 1 15 A 3 20 A 4 25 A 5 30 D 2 35 D 4 40 E 0 0 每一组输入数据包括三个数据项 汽车 到达 或 离去 信息 汽车牌照号码及到达或离去的时刻 其中 A 表示到达 D 表示离 去 E 表示输入结束 4 实现提示实现提示 需另设一个栈栈 临时停放为给要离去的汽车让路而从停车场退出来的汽车 也用顺序 存储结构实现 输入数据按到达或离去的时刻有序 栈中每个元素表示一辆汽车 包含两 个数据项 汽车的牌照号码和进入停车场的时刻 5 选作内容选作内容 1 两个栈共享空间 思考应开辟数组的空间是多少 2 汽车可有不同种类 则它们的占地面积不同 收费标准也不同 如 1 辆客车和 1 5 辆小汽车的占地面积相同 1 辆十轮卡车占地面积相当于 3 辆小汽车的占地面积 3 汽车可以直接从便道上开走 此时排在它前面的汽车要先开走让路 然后再依 次排到队尾 4 停放在便道上的汽车也收费 收费标准比停放在停车场的车低 请思考如何修 改结构以满足这种要求 9 简单行编辑程序 简单行编辑程序 1 问题描述问题描述 文本编辑程序是利用计算机进行文字加工的基本软件工具 实现对文本文件的插入 删除等修改操作 限制这些操作以行为单位以行为单位进行的编辑程序称为行编辑程序 被编辑的文本文件文本文件可能很大 全部读入编辑程序的数据空间 内存 的做法既不经济 也不总能实现 一种解决方法是逐段地编辑 任何时刻只把待编辑文件的一段放在内存 称为活区 试按照这种方法实现一个简单的行编辑程序 设文件每行最多含 320 个字符 实际含量很少超过 80 字符 2 基本要求基本要求 实现以下 4 条基本编辑命令 1 行插入 格式 i 将插入活区中第行之后 2 行删除 格式 d 删除活区中第行 到第行 两种格式的例子是 d10 和 d10 14 3 活区切换 格式 n 将活区写入输出文件 并从输入文件中读入下一段 作为新的活区 4 活区显示 格式 p 逐页地 每页 20 行 显示活区内容 每显示一页之后请用户决定是否继续显示以后 各页 如果存在 打印出的每一行要前置行号和一个空格符 行号固定占 4 位 增量为 1 各条命令中的行号均须在活区中各行行号范围之内 只有插入命令的行号可以等于活 区第一行行号减 1 表示插入当前屏幕中第一行之前 否则命令参数非法 3 测试数据测试数据 由学生依据软件工程的测试技术自己确定 注意测试边界数据 如首行 尾行 4 实现提示实现提示 1 设活区的大小用行数 activemaxlen 可设为 100 来描述 考虑到文本文件行 长通常为正态分布 且峰值在 60 到 70 之间 用 320 activemaxlen 大小的字符数组字符数组实现 存储将造成大量浪费 可以以标准行块为单位为各行分配存储 每个标准行块含 81 个字符 这些行块可以组成一个数组 也可以利用动态链表连接起来 一行文字可能占多个行块 行尾可用一个特殊的 ASCII 字符 如 012 8 标识 此外 还应记住活区起始行号 行插 入将引起随后各行行号的顺序下推 2 初始化过程包括 请用户提供输入文件名 空串表示无输入文件 和输出文件 名 两者不能相同 然后尽可能多地从输入文件中读入各行 但不超过 activemaxlen x x 的值可以自定 例如 20 3 在执行行插入命令的过程中 每接收到一行时都要检查活区大小是否已达 activemaxlen 如果是 则为了在插入这一行之后仍保持活区大小不超过 activemaxlen 应将插入点之前的活区部分中第一行输出到输出文件中 若插入点为第一行之前 则只得 将新插入的这一行输出 4 若输入文件尚未读完 活区切换命令可将原活区中最后几行留在活区顶部 以 保持阅读连续性 否则 它意味着结束编辑或开始编辑另一个文件 5 可令前三条命令执行后自动调用活区显示 5 选作内容选作内容 1 对于命令格式非法等一切错误作严格检查和适当处理 2 加入更复杂的编辑操作 如对某行进行串替换 在活区内进行模式匹配模式匹配等 格 式可以为 S 和 m 10 哈希表设计 哈希表设计 1 问题描述问题描述 针对某个集体中人名设计一个哈希表 使得平均查找长度不超过 R 并完成相应的建 表和查表程序 2 基本要求基本要求 假设人名为中国人姓名的汉语拼音形式 待填入哈希表的人名共有 30 个 取平均查找 长度的上限为 2 用除留余数法设计哈希函数 分别用两种方法处理冲突 线性探测法和 拉链法 构造两个散列表 并给出两个散列表的平均查找长度 3 测试数据测试数据 取读者周围较熟悉的 30 个人名 4 选作内容选作内容 1 从教材上介绍的几种哈希函数构造方法中选出适用者并设计几个不同的哈希函 数 比较他们的地址冲突率 可以用更大的名字集合作实验 2 研究这 30 个人名的特点 努力找一个哈希函数 使得对于不同的拼音名一定不 发生地址冲突 3 在哈希函数确定的前提下尝试各种不同处理冲突的方法 考察平均查找长度的 变化和造好的哈希表中关键字的聚集性 11 校园导游程序 校园导游程序 1 问题描述问题描述 用无向网无向网表示你所在学校的校园景点平面图 图中顶点表示主要景点 存放景点的编 号 名称 简介等信息 图中的边表示景点间的道路 存放路径长度等信息 要求能够回 答有关景点介绍 游览路径等问题 2 基本要求基本要求 1 查询各景点的相关信息 2 查询图中任意两个景点间的最短路径最短路径 3 查询图中任意两个景点间的所有路径 4 增加 删除 更新有关景点和道路的信息 3 选作内容选作内容 1 求多个景点的最佳 最短 游览路径 2 区分机动车道和人行道 3 实现导游图的仿真界面 12 排序系统设计 排序系统设计 1 问题描述问题描述 设编号为 1 2 3 n 的 n n 0 个人按顺时针方向围坐一圈 每个人持有一个正 整数密码 开始时任选一个正整数作为报数上限 m 从第一个人开始顺时针方向自 1 起顺 序报数 报到 m 时停止报数 报 m 的人出列 将他的密码作为新的 m 值 从他的下一个 人开始重新从 1 报数 如此下去 直到所有人全部出列为止 令 n 最大值取 30 要求设计 一个程序模拟此过程 求出列编号序列 2 基本要求基本要求 1 初步完成总体设计 搭好框架 确定人机对话的界面 确定函数个数 2 完成最低要求 建立一个系统 包括 5 个人的情况 13 某机场的某机场的机票管理系统机票管理系统 1 问题描述问题描述 一机场每天有 n 个航班 每个班次都有一班次号 1 2 3 n 固定的起飞时间 固 定的路线 起始站 终点站 大致的飞行车时间 固定的额定载客量 如 班次 起飞时间 起点站 终点站 飞行时间 额定载量 已定票人数 1 8 00 天津 广汉 2 145 130 2 6 30 天津 成都 0 5 140 140 3 7 00 天津 成都 0 5 140 120 4 10 00 天津 成都 0 5 140 120 试设计一个机票管理系统 对机场的售票情况进行管理 2 基本要求基本要求 1 录入班次信息 信息用文件保存 可不定时地增加班次数据 2 浏览班次信息 可显示出所有班次当前状况 如果当前系统时间超过了某班次的起飞时 间 则显示 此班已发出 的提示信息 3 查询路线 可按班次号查询 可按终点站查询 4 售票和退票功能 信息用文件保存 A 当查询出已定票人数小于额定载量且当前系统时间小于起飞时间时才能售票 自动 更新已售票人数 B 退票时 输入退票的班次 当本航班飞机未发出时才能退票 自动更新已售票人数 14 集合运算 集合运算 1 问题描述问题描述 使用链表链表来表示集合 完成集合的合并 求交集等操作 2 基本要求基本要求 1 用链表表示两个集合 2 对两个集合分别从小到大排序 3 两个集合合并成另一个新集合 如数值相同 合并为一个数据项 4 求出两个集合的交集建立一个新的集合 15 二叉排序树的遍历 二叉排序树的遍历 用递归或非递归方法都可以 1 问题描述问题描述 输入树的各个结点 建立二叉排序树 对建立的二叉排序树进行层序 先序 中序和 后序遍历并统计该二叉树中叶子结点的数目 以及该二叉树的平均查找长度 2 基本要求基本要求 1 用菜单实现 2 能够输入树的各个结点 并能够输出用不同方法遍历的遍历序列和叶子结点的数目 以及该二叉树的平均查找长度 附录 2 课程设计说明书规范 一 课程设计说明书规范 课程设计说明书是课程设计主要成果之一 对于设计类 应包括图纸 程序 实物成 果等 1 说明书基本格式 说明书打印 正文采用 5 号宋体 A4 纸 页边距均为 20mm 行间距采用 18 磅 文 中标题采用宋体加粗 2 说明书结构及要求 1 封面 见附录见附录 3 包括 题目 系别 班级 完成日期 成绩及指导教师 签字 学生姓名等项 2 课程设计任务书 格式见附录见附录 4 3 目录 自动生成目