数据结构课程设计指导2012.doc

数据结构课程设计指导数据结构课程设计指导 电子与信息工程系电子与信息工程系 一 设计目的一 设计目的 熟悉各种数据结构和运算 会使用数据结构的基本操作解决一些实际问题 二 设计要求二 设计要求 在本课程设计过程中要求学生 1 重视课程设计环节 用严谨 科学和踏实的工作态度对待课程设计的每一项任务 2 按照课程设计的题目要求 独立地完成各项任务 严禁抄袭 凡发现抄袭 抄袭 者与被抄袭者皆以零分计入本课程设计成绩 凡发现实验报告或源程序雷同 涉及的 全部人员皆以零分计入本课程设计成绩 3 认真编写课程设计报告 课程设计报告的书写格式及要求见附录 2 三 设计步骤三 设计步骤 1 问题分析和任务定义 2 数据结构和算法的设计 3 编码实现和静态检查 4 上机调试 5 总结和整理课程设计报告 四 时间和机房安排四 时间和机房安排 18 周星期时间机房 一8 15 11 301 楼 1 号机房 一14 00 15 301 楼 3 号机房 三8 15 11 301 楼 1 号机房 三14 00 15 301 楼 2 号机房 五 考核方式和成绩评定五 考核方式和成绩评定 考核分为两个部分 验收 按规定时间到机房运行程序 由老师检查运行情况 学生能对自己的程序 面对教师提问并能熟练地解释清楚 要求验收时需要数据文件的程序提前建好数 据文件 无数据文件要求的把原始数据提前输入 等老师验收 实验报告 是否按规定书写实验报告的各项内容 课程设计成绩采用五级分制 100 上机检查 50 课程设计报告 50 六 上交相关内容要求六 上交相关内容要求 上交的成果的内容必须由以下四个部分组成 缺一不可 1 上交源程序 学生按照课程设计的具体要求所开发的所有源程序 应该放到一个 文件夹中 2 上交程序的说明文件 保存在 doc 中 在说明文档中应该写明上交程序所在的 目录 上交程序的主程序文件名 如果需要安装 要有程序的安装使用说明 3 课程设计报告 保存在 word 文档中 文件名要求 按照 学号 姓名 起名 如文 件名为 09730101 张三 doc 具体要求见后面 附录 1 数据结构课程设计的具体内容 1 一元多项式乘法 一元多项式乘法 1 问题描述问题描述 已知 A x a0 a1x a2x2 anxn和 B x b0 b1x b2x2 bmxm 并且在 A x 和 B x 中 指数相差很多 求 A x A x B x 2 基本要求基本要求 1 设计存储结构表示一元多项式 2 设计算法实现一元多项式乘法 3 分析算法的时间复杂度和空间复杂度 2 迷宫问题迷宫问题 1 问题描述问题描述 迷宫求解是实验心理学中的一个经典问题 心理学家把一只老鼠从一个无顶盖的大盒 子的入口处赶进迷宫 迷宫中设置很多隔壁 对前进方向形成了多处障碍 心理学家在迷 宫的唯一出口处放置了一块奶酪 吸引老鼠在迷宫中寻找通路以到达出口 例如 图 2 所 示为一个迷宫示意图 其中双边矩形表示迷宫 1 代表有障碍 0 代表无障碍 2 基本要求基本要求 1 设计数据结构存储迷宫 2 设计存储结构保存从入口到出口的通路 3 设计算法完成迷宫问题的求解 4 分析算法的时间复杂度 3 设计思想设计思想 可以采用回溯法实现该问题的求解 回溯法是一种不断试探及时纠正错误的搜索方法 从入口出发 按某一方向向前探索 若能走通 未走过的 即某处可以到达 则到达新点 否则试探下一方向 若所有的方向均没有通路 则沿原路返回前一点 换下一个方向再继 续试探 直到所有可能的通路都搜索到 或找到一条通路 或无路可走又返回到入口点 0123456789 01111111111 11011101111 21101011111 31010000011 41011101111 51100110001 61011001101 71111111111 入口 1 1 出口 6 8 图 2 迷宫示意图 其中 1 代表有障碍 0 代表无障碍 前进的方向有八个 分别是上 下 左 右 左上 左下 右上 右下 在求解过程中 为了保证在任何位置上都能沿原路退回 需要一个后进先出的栈来保 存从入口到当前位置的路径 可以将迷宫定义成一个二维数组 则每个点有 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 容忍值 则在 j 处放置放大器 2 2 否则 D i max D i D j d j 4 哈夫曼编码 哈夫曼编码 1 问题描述问题描述 设某编码系统共有 n 个字符 使用频率分别为 w1 w2 wn 设计一个不等长的编码 方案 使得该编码系统的空间效率最好 2 基本要求基本要求 1 设计数据结构 2 设计编码算法 3 分析时间复杂度和空间复杂度 3 设计思想设计思想 利用 Huffman 编码树求得最佳的编码方案 根据哈夫曼算法 建立哈夫曼树时 可以将哈夫曼树定义为一个结构型的一维数组 HuffTree 保存哈夫曼树中各结点的信息 每个结点包括 权值 左孩子 右孩子 双亲 如图 6 所示 由于哈夫曼树中共有 2n 1 个结点 并且进行 n 1 次合并操作 所以该数组的 长度为 2n 1 构造哈夫曼树的伪代码如下 1 数组 huffTree 初始化 所有元素结点的双亲 左右孩子都置为 1 2 数组 huffTree 的前 n 个元素的权值置给定权值 w n 3 进行 n 1 次合并 3 1 在二叉树集合中选取两个权值最小的根结点 其下标分别为 i1 i2 3 2 将二叉树 i1 i2 合并为一棵新的二叉树 k 在哈夫曼树中 设左分支为 0 右分支为 1 从根结点出发 遍历整棵哈夫曼树 求得 各个叶子结点所表示字符的哈夫曼编码 提高 输入一篇英文文章 统计每个字符出现的次数 并以此构造哈夫曼树和输出 每个字符的哈夫曼编码 最后输出这篇文章的编码 5 TSP 问题问题 回溯法求解 回溯法求解 1 问题描述问题描述 所谓 TSP 问题是指旅行家要旅行 n 个城市 要求各个城市经历且仅经历一次 并要求 weight lchild rchild parent 图 6 哈夫曼树的结点结构 所走的路程最短 该问题又称为货郎担问题 邮递员问题 售货员问题 是图问题中最广 为人知的问题 2 基本要求基本要求 1 上网查找 TSP 问题的应用实例 2 分析求 TSP 问题的全局最优解的时间复杂度 3 设计一个求近似解的算法 4 分析算法的时间复杂度 3 设计思想设计思想 对于 TSP 问题 一种最容易想到的也肯定能得到最佳解的算法是穷举法 即考虑所有 可能的旅行路线 从中选择最佳的一条 但是用穷举法求解 TSP 问题的时间复杂度为 n 当 n 大到一定程度后是不可解的 本实验可以采用回溯法求解 使用邻接矩阵存储该图 提示 可参考 计算机算法设计与分析 电子工业出版社 6 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 7 医院选址问题 医院选址问题 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 个 并 充分理解 Floyd 算法 ab c d e 1 2 5 32 1 4 顶点偏心度 a b 6 b 8 d 5 e 7 a b 图 7 带权有向图及各顶点的偏心度 8 简单个人电话号码查询系统简单个人电话号码查询系统 1 问题描述问题描述 人们在日常生活中经常需要查找某个人或某个单位的电话号码 本实验将实现一个简 单的个人电话号码查询系统 根据用户输入的信息 例如姓名等 进行快速查询 2 基本要求基本要求 1 使用文件保存电话号码信息 2 设计数据结构存储电话号码信息 3 提供查询功能 根据姓名实现快速查询 4 提供其他维护功能 例如插入 删除 修改等 5 按电话号码进行排序 3 设计思想设计思想 由于需要管理的电话号码信息较多 而且要在程序运行结束后仍然保存电话号码信息 所以电话号码信息采用文件的形式存放到外存中 在系统运行时 需要将电话号码信息从 文件调入内存来进行查找等操作 为了接收文件中的内容 要有一个数据结构与之对应 可以设计如下结构类型的数组来接收数据 const int max 20 struct TeleNumber string name 姓名 string phoneNumber 固定电话号码 string mobileNumber 移动电话号码 string email 电子邮箱 Tele max 为了实现对电话号码的快速查询 可以将上述结构数组排序 以便应用折半查找 但 是 在数组中实现插入和删除操作的代价较高 如果记录需频繁进行插入或删除操作 可 以考虑采用二叉排序树组织电话号码信息 则查找和维护都能获得较高的时间性能 更复 杂地 需要考虑该二叉排序树是否平衡 如何使之达到平衡 要求 使用实际的电话号码 并不小于 20 个 9 各种排序算法时间性能的比较 各种排序算法时间性能的比较 1 问题描述问题描述 对各种排序方法 直接插入排序 希尔排序 起泡排序 快速排序 直接选择排序 堆排序和归并排序 的时间性能进行比较 2 基本要求基本要求 1 设计并实现上述各种排序算法 2 产生正序和逆序的初始排列分别调用上述排序算法 并比较时间性能 3 产生随机的初始排列分别调用上述排序算法 并比较时间性能 3 设计思想设计思想 上述各种排序方法都是基于比较的内排序 其时间主要消耗在排序过程中进行的记录 的比较次数和移动次数 因此 统计在相同数据状态下不同排序算法的比较次数和移动次 数 即可实现比较各种排序算法的目的 要求 在课程设计报告中对实验结果进行分析 对正序 逆序和随机的初始排列情况下 每种排序算法的时间复杂度进行比较 10 机器调度问题 机器调度问题 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时间完成且任何机器在同一时刻仅能处理一个作业 因此最短调度长度为 17 m1 m2 m3 时间 分配 作业作业 5作业作业 6 作业作业 3 作业作业 1 作业作业 2 作业作业 7 作业作业 4 17 16 图 9 三台机器的调度示例 654 在上述处理中 采用了最长时间优先 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 中 2 5 将堆 H1 的堆顶元素删除 3 堆 H2 的堆顶元素就是最短调度时间 11 运动会分数统计运动会分数统计 1 问题描述问题描述 参加运动会有 n 个学校 学校编号为 1 n 比赛分成 m 个男子项目 和 w 个女子项 目 项目编号为男子 1 m 女子 m 1 m w 不同的项目取前五名或前三名积分 取前 五名的积分分别为 7 5 3 2 1 前三名的积分分别为 5 3 2 哪些取前五名或前 三名由学生自己设定 m 20 n 20 2 2 基本要求基本要求 1 可以输入各个项目的前三名或前五名的成绩 2 能统计各学校总分 3 可以按学校编号 学校总分 男女团体总分排序输出 4 可以按学校编号查询学校某个项目的情况 可以按项目编号查询取得前三或 前五名的学校 规定 输入数据形式和范围 20 以内的整数 如果做得更好可以输入学校的名称 运动项目的名称 输出形式 有中文提示 各学校分数为整型 界面要求 有合理的提示 每个功能可以设立菜单 根据提示 可以完成相关的 功能要求 存储结构 学生自己根据系统功能要求自己设计 但是要求运动会的相关数据要 存储在数据文件中 请在最后的上交资料中指明你用到的存储结构 测试数据 要求使用 1 全部合法数据 2 整体非法数据 3 局部非法数据 进行程序测试 以保证程序的稳定 测试数据及测试结果请在上交的资料中写明 12 订票系统订票系统 1 问题描述问题描述 通过此系统可以实现如下功能 1 录入 可以录入航班情况 数据需存储在一个数据文件中 数据结构 具体数据自定 2 查询 可以查询某个航线的情况 如 输入航班号 查询起降时间 起飞抵达城市 航班票价 票价折扣 确定航班是否满仓 可以输入起飞抵达城市 查询飞机航班情况 3 订票 订票情况可以存在一个数据文件中 结构自己设定 可以订票 如果该航班已经无票 可以提供相关可选择航班 4 退票 可退票 退票后修改相关数据文件 客户资料有姓名 证件号 订票数量及航班情况 订单要有编号 5 修改航班信息 当航班信息改变可以修改航班数据文件 2 基本要求基本要求 根据以上功能说明 设计航班信息 订票信息的存储结构 设计程序完成功能 13 文章编辑文章编辑 1 1 问题描述问题描述 输入一页文字 程序可以统计出文字 数字 空格的个数 2 2 基本要求基本要求 静态存储一页文章 每行最多不超过 80 个字符 共 N 行 要求 1 分别统计出其中 英文字母数和空格数及整篇文章总字数 2 统计某一字符串在文章中出现的次数 并输 出该次数 3 删除某一子串 并将后面的字符前移 存储结构使用线性表 分别用几个子函数实现相应的功能 输入数据的形式和范围 可以输入大写 小写的英文字母 任何数字及标点符号 输出形式 1 分行输出用户输入的各行字符 2 分 4 行输出 全部字母数 数字个数 空格个数 文章总字数 3 输出删除某一字符串后的文章 14 停车场管理 停车场管理 1 1 问题描述问题描述 设停车场内只有一个可停放 n 辆汽车的狭长通道 且只有一个大门可供汽车进出 汽 车在停车场内按车辆到达时间的先后顺序 依次由北向南排列 大门在最南端 最先到达 的第一辆车停放在车场的最北端 若车场内已停满 n 辆汽车 则后来的汽车只能在门外 的便道上等候 一旦有车开走 则排在便道上的第一辆车即可开入 当停车场内某辆车要 离开时 在它之后开入的车辆必须先退出车场为它让路 待该辆车开出大门外 其它车辆 再按原次序进入车场 每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交 纳费用 试为停车场编制按上述要求进行管理的模拟程序 2 2 基本要求基本要求 以栈模拟停车场 以队列模拟车场外的便道 按照从终端读入的输入数据序列进行模 拟管理 每一组输入数据包括三个数据项 汽车 到达 或 离去 信息 汽车牌照号码 及到达或离去的时刻 对每一组输入数据进行操作后的输出数据为 若是车辆到达 则输 出汽车在停车场内或便道上的停车位置 若是车离去 则输出汽车在停车场内停留的时间 和应交纳的费用 在便道上停留的时间不收费 栈以顺序结构实现 队列以链表实现 3 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 4 实现提示实现提示 需另设一个栈 临时停放为给要离去的汽车让路而从停车场退出来的汽车 也用顺序 存储结构实现 输入数据按到达或离去的时刻有序 栈中每个元素表示一辆汽车 包含两 个数据项 汽车的牌照号码和进入停车场的时刻 5 5 选作内容选作内容 1 两个栈共享空间 思考应开辟数组的空间是多少 2 汽车可有不同种类 则它们的占地面积不同 收费标准也不同 如 1 辆客车和 1 5 辆小汽车的占地面积相同 1 辆十轮卡车占地面积相当于 3 辆小汽车的占地面积 3 汽车可以直接从便道上开走 此时排在它前面的汽车要先开走让路 然后再依 次排到队尾 4 停放在便道上的汽车也收费 收费标准比停放在停车场的车低 请思考如何修 改结构以满足这种要求 15 简单行编辑程序 简单行编辑程序 1 1 问题描述问题描述 文本编辑程序是利用计算机进行文字加工的基本软件工具 实现对文本文件的插入 删除等修改操作 限制这些操作以行为单位进行的编辑程序称为行编辑程序 被编辑的文本文件可能很大 全部读入编辑程序的数据空间 内存 的做法既不经济 也不总能实现 一种解决方法是逐段地编辑 任何时刻只把待编辑文件的一段放在内存 称为活区 试按照这种方法实现一个简单的行编辑程序 设文件每行不超过 320 个字符 很少超过 80 字符 2 2 基本要求基本要求 实现以下 4 条基本编辑命令 1 行插入 格式 i 将插入活区中第行之后 2 行删除 格式 d 删除活区中第行 到第行 两种格式的例子是 d10 和 d10 14 3 活区切换 格式 n 将活区写入输出文件 并从输入文件中读入下一段 作为新的活区 4 活区显示 格式 p 逐页地 每页 20 行 显示活区内容 每显示一页之后请用户决定是否继续显示以后 各页 如果存在 印出的每一行要前置以行号和一个空格符 行号固定占 4 位 增量为 1 各条命令中的行号均须在活区中各行行号范围之内 只有插入命令的行号可以等于活 区第一行行号减 1 表示插入当前屏幕中第一行之前 否则命令参数非法 3 3 测试数据测试数据 由学生依据软件工程的测试技术自己确定 注意测试边界数据 如首行 尾行 4 4 实现提示实现提示 1 设活区的大小用行数 activemaxlen 可设为 100 来描述 考虑到文本文件行 长通常为正态分布 且峰值在 60 到 70 之间 用 320 activemaxlen 大小的字符数组实现 存储将造成大量浪费 可以以标准行块为单位为各行分配存储 每个标准行块含 81 个字符 这些行块可以组成一个数组 也可以利用动态链表连接起来 一行文字可能占多个行块 行尾可用一个特殊的 ASCII 字符 如 012 8 标识 此外 还应记住活区起始行号 行插 入将引起随后各行行号的顺序下推 2 初始化过程包括 请用户提供输入文件名 空串表示无输入文件 和输出文件 名 两者不能相同 然后尽可能多地从输入文件中读入各行 但不超过 activemaxlen x x 的值可以自定 例如 20 3 在执行行插入命令的过程中 每接收到一行时到要检查活区大小是否已达 activemaxlen 如果是 则为了在插入这一行之后仍保持活区大小不超过 activemaxlen 应将插入点之前的活区部分中第一行输出到输出文件中 若插入点为第一行之前 则只得 将新插入的这一行输出 4 若输入文件尚未读完 活区切换命令可将原活区中最后几行留在活区顶部 以 保持阅读连续性 否则 它意味着结束编辑或开始编辑另一个文件 5 可令前三条命令执行后自动调用活区显示 5 5 选作内容选作内容 1 对于命令格式非法等一切错误作严格检查和适当处理 2 加入更复杂的编辑操作 如对某行进行串替换 在活区内进行模式匹配等 格 式可以为 S 和 m 16 哈希表设计 哈希表设计 1 1 问题描述问题描述 针对某个集体中人名设计一个哈希表 使得平均查找长度不超过 R 并完成相应的建 表和查表程序 2 2 基本要求基本要求 假设人名为中国人姓名的汉语拼音形式 待填入哈希表的人名共有 30 个 取平均查找 长度的上限为 2 哈希函数用除留余数法构造 用线性探测再散列法或链地址法处理冲突 3 3 测试数据测试数据 取读者周围较熟悉的 30 个人名 4 4 选作内容选作内容 1 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希 函数 比较他们的地址冲突率 可以用更大的名字集合作实验 2 研究这 30 个人名的特点 努力找一个哈希函数 使得对于不同的拼音名一定不 发生地址冲突 3 在哈希函数确定的前提下尝试各种不同处理冲突的方法 考察平均查找长度的 变化和造好的哈希表中关键字的聚集性 17 校园导游程序 校园导游程序 1 1 问题描述问题描述 用无向网表示你所在学校的校园景点平面图 图中顶点表示主要景点 存放景点的编 号 名称 简介等信息 图中的边表示景点间的道路 存放路径长度等信息 要求能够回 答有关景点介绍 游览路径等问题 2 2 基本要求基本要求 1 各景点信息存储在数据文件中 以天津城建学院为例 至少 8 个景点 2 查询各景点的相关信息 3 查询图中任意两个景点间的最短路径 4 查询图中任意两个景点间的所有路径 5 增加 删除 更新有关景点和道路的信息 并存入数据文件中 3 3 选作内容选作内容 1 求多个景点的最佳 最短 游览路径 2 区分机动车道和人行道 3 实现导游图的仿真界面 18 二叉排序树的遍历 二叉排序树的遍历 1 1 问题描述问题描述 输入树的各个结点 建立二叉排序树 对建立的二叉排序树进行层次 先序 中序和 后序遍历并统计该二叉树中叶子结点的数目 2 2 基本要求基本要求 1 用菜单实现 2 输入树的各个结点 建立二叉排序树 并能够输出用不同方法遍历的遍历序列和叶 子结点的数目 提高 实现二叉排序树的插入和删除操作 19 个人帐簿管理系统设计 个人帐簿管理系统设计 1 问题描述问题描述 个人帐簿管理系统记录某人每月的全部收入及各项开支情况 包括食品消费 房租 子女教育费用 水电费 医疗费 储蓄等 进入系统后可以输入和修改某月的收支情况 可以对每月的开支从小到大进行排序 可以根据输入的月份查询每月的收支情况 2 基本要求基本要求 1 初步完成总体设计 搭好框架 确定人机对话的界面 确定函数个数 2 完成最低要求 建立一个文件 包括某人 5 个月的收支情况 能对文件中的信息 进行扩充 追加 修改和删除 3 进一步要求 完成对每月的开支排序 以及完成系统查询功能 有兴趣的同学可 以自己扩充系统功能 20 学分管理程序 学分管理程序 1 问题描述问题描述 请设计一个学生的学分管理程序 假设每位学生必须完成基础课 50 学分 专业课 50 学分 选修课 24 学分 人文类课程 8 学分 实验性课程 20 学分才能够毕业 因此在管理学分时 要考虑每个学分所属于的课 程类别 学分信息应该包括学号 姓名 课程类别 学分等 2 基本要求基本要求 该程序应该具有下列功能 1 通过键盘输入多个学生的学分 存入数据文件中 2 给定学号 显示某位学生的学分完成情况 3 给定某个班级的班号 显示该班所有学生学分完成情况 4 给定某位学生的学号 修改该学生的学分信息 5 按照某类课程的学分高低进行排序 6 提供一些统计各类信息的功能 21 销售管理系统 销售管理系统 1 问题描述问题描述 某公司有四个销售员 编号 1 4 负责销售五种产品 编号 1 5 每个销售员都 将当天出售的每种产品各写一张便条交上来 每张便条包含内容 1 销售员的代号 2 产品的代号 3 这种产品的当天的销售额 每位销售员每天可能上缴 0 5 张便条 假设 收集到了上个月的所有便条 编写一 个处理系统 读取上个月的销售情况 自己设定 进行如下处理 2 基本要求基本要求 1 计算上个月每个人每种产品的销售额 2 按销售额对销售员进行排序 输出排序结果 销售员代号 3 统计每种产品的总销售额 对这些产品按从高到底的顺序 输出排序结果 需输出 产品的代号和销售额 4 每张便条的信息存储在数据文件中 1 问题描述问题描述 试设计一库存管理系统 产品信息包括产品编号 名称 价格 数量等 产品编号不 重复 2 基本要求基本要求 该系统应具有以下功能 1 产品信息录入功能 产品信息用文件保存 输入 2 产品信息浏览功能 输出 3 产品入库 4 产品出库 5 查询和排序功能 1 按价格从大到小排序 2 按名称查询 6 产品信息删除 修改功能 22 学生作业完成情况管理程序 学生作业完成情况管理程序 1 问题描述问题描述 请设计一个学生作业完成情况管理程序 假设某门课程一学期要留 10 次作业 每次老师要进行批改 给出分数后还要进行登记 学期期末要根据每次作业的成绩计算出最终的平时成绩 满分 100 作业登记信息应该包 含 学号 姓名 10 次作业的完成情况 2 基本要求基本要求 该程序应该具有下列功能 1 通过键盘输入某位学生某次作业的分数 2 给定学号 显示某位学生作业完成情况 3 给定某个班级的班号 显示该班所有学生的作业完成情况 4 给定某位学生的学号 修改该学生的作业完成信息 5 给定某位学生的学号 删除该学生的信息 6 按学生的最终平时成绩进行排序 7 输出平均分数 8 用数据文件保存作业登记信息 23 学生籍贯管理系统 学生籍贯管理系统 1 问题描述问题描述 编制一个学生籍贯信息记录簿 每个学生信息包括 学号 姓名 籍贯 通信地址 2 基本要求基本要求 该程序应该具有下列功能 1 输入学生信息并以磁盘文件保存 2 读取磁盘文件并显示输出所有学生的籍贯信息 3 按学号或姓名查询其籍贯 4 按籍贯查询并输出该籍贯的所有学生 5 能添加 删除和修改学生的籍贯信息 6 显示输出天津籍和非天津籍学生的信息并可分别存盘 7 按学号进行排序 24 机票管理系统 机票管理系统 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 退票时 输入退票的班次 当本航班飞机未发出时才能退票 自动更新已售票人数 25 学生成绩系统 学生成绩系统 1 问题描述问题描述 使用下面的数据 设计一个简单的成绩管理系统 实现出最基本的功能 学生基本信息文件 A TXT 及其内容 A TXT 文件不需要编程录入数据 可用文本编辑 工具直接生成 学号 姓名 性别 宿舍号码 电话号码 01 张成成 男 501 87732111 02 李成华 女 101 87723112 03 王成凤 女 101 87723112 04 张明明 男 502 87734333 学生成绩基本信息文件 B TXT 及其内容 学号 课程编号 课程名称 学分 平时成绩 实验成绩 卷面成绩 综合成绩 实得学分 01 A01 大学物理 3 66 78 82 02 B03 高等数学 4 78 1 90 01 B03 高等数学 4 45 1 88 02 C01 VF 3 65 76 66 2 基本要求基本要求 功能要求及说明 1 数据录入功能 对 B TXT 进行数据录入 只录入每个学生的学号 课程编号 课程 名称 学分 平时成绩 实验成绩 卷面成绩共 7 个数据 综合成绩 学分由程序根据条 件自动运算 综合成绩的计算 如果本课程的实验成绩为 1 则表示无实验 综合成绩 平时成绩 30 卷面成绩 70 如果实验成绩不为 1 表示本课程有实验 综合成绩 平时成绩 15 实 验成绩 15 卷面成绩 70 实得学分的计算 采用等级学分制 综合成绩在 90 100 之间 应得学分 学分 100 综合成绩在 70 90 之间 应得学分 学分 80 综合成绩在 60 70 之间 应得学分 学分 65 综合成绩在 60 以下 应得学分 学分 0 2 删除功能 当在 A TXT 中删除一个学生时 自动地在 B TXT 中删除此人所有信息 3 排序功能 能实现选择按综合成绩或实得学分升序或降序排序并显示数据 4 查询功能 分为学生基本情况查询和成绩查询两种 A 学生基本情况查询 A1 输入一个学号或姓名 可实现选择 查出此生的基本信息并显示输出 A2 输入一个宿舍号码 可查询出本室所有的学生的基本信息并显示输出 B 成绩查询 B1 输入一个学号时 查询出此生的所有课程情况 格式如下 学 号 xx 姓 名 xxxxx 课程编号 xxx 课程名称 xxxxx 综合成绩 xxxx 实得学分 xx 课程编号 xxx 课程名称 xxxxx 综合成绩 xxxx 实得学分 xx 课程编号 xxx 课程名称 xxxxx 综合成绩 xxxx 实得学分 xx 共修 xx 科 实得总学分为 xxx 26 单项选择题标准化考试系统 单项选择题标准化考试系统 1 问题描述问题描述 设计一单项选择题标准化考试系统 实现考试的标准化管理 2 基本要求基本要求 功能要求 1 用文件保存试题库 每个试题包括题干 4 个备选答案 标准答案 2 试题录入 可随时增加试题到试题库中 3 试题抽取 每次从试题库中可以随机抽出 N 道题 N 由键盘输入 4 答题 用户可实现输入自己的答案 5 自动判卷 系统可根据用户答案与标准答案的对比实现判卷并给出成绩 注意 在 C 语言中产生随机数的方法 使用随机数函数 在使用随机数函数 random 之前 应包含文件 include 然后使用下述函数初始化 randomize init the random number generator 以后就可以直接使用 random 函数来产生需要的数据 如果需要产生 10 以内的数 使用 random 10 就可以了 产生 100 以内的数 使用 random 100 就可以了 在 C 中 产生随机数 include include 然后 srand time 0 以当前时间当做随机种子 rand 产生一个位于 0 32767 之间的随机数 27 通信录管理系统 通信录管理系统 1 问题描述问题描述 设计出模拟手机通信录管理系统 实现对手机中的通信录进行管理 2 基本要求基本要求 功能要求 1 查看功能 选择此功能时 列出下列三类选择 A 工作类 B 家庭类 C 朋友类 当选中某类时 显示出此类所有数据中的姓名 和电话号码 2 增加功能 能录入新数据 一个结点包括 姓名 电话号码 分类 可选项有 A 工作类 B 家庭类 C 朋友类 家庭住址 例如 杨春商务类 南开区 当录入了重复的姓名和电话号码时 则提示数据录入重复并取消录入 当通信录中超 过 10 条信息时 存储空间已满 不能再录入新数据 录入的新数据能按递增的顺序自 动进行条目编号 3 修改功能 选中某个人的姓名时 可对此人的相应数据进行修改 4 删除功能 选中某个人的姓名时 可对此人的相应数据进行删除 并自动调整 后续条目的编号 28 图书管理系统 图书管理系统 1 问题描述问题描述 设计一个系统 对图书信息进行管理 信息描述 有关该系统基本信息的描述 如 图 书名称 图书编号 单价 作者 存在状态 借书人姓名 性别 学号等 2 基本要求基本要求 基本功能 1 新进图书基本信息的输入 图书基本信息保存在数据文件中 2 图书基本信息的查询 3 对撤消图书信息的删除 4 为借书人办理注册 5 办理借书手续 非注册会员不能借书 6 办理还书手续 7 统计图书库存 已借出图书数量 29 通讯录管理 通讯录管理