2015-2016学年第2学期《算法与数据结构课程设计》任务书及指导书.pdf
8页
《算法与数据结构》课程设计指导书课 程 名 称 ： 算 法 与 数 据 结 构 课 程 设 计课 程 代 码 ： 24090500S适 用 专 业 ： 计 算 机 科 学 与 技 术制 定 人 ： 张 淼 艳审 阅 人 ： 张 绍 阳 （ 系 主 任 ）修 订 时 间 ： 2016 年 6 月信息工程学院课 程 编 号 ： 2409050S 课 程 性 质 ： 专 业 实 践 课学 时 /学 分 ： 1周 /1. 适 用 专 业 ： 计 算 机 科 学 与 技 术教 材 ： 《 数 据 结 构 》 C语 言 版 ， 严 蔚 敏 、 吴 伟 民 编 著 ， 清 华 大 学 出 版 社课程设计目的：1． 训 练 学 生 灵 活 应 用 所 学 数 据 结 构 知 识 ， 独 立 完 成 问 题 分 析 ， 结 合 数 据 结构 理 论 知 识 ， 编 写 程 序 求 解 指 定 问 题 的 能 力 2． 初 步 掌 握 软 件 开 发 过 程 的 问 题 分 析 、 系 统 设 计 、 程 序 编 码 、 测 试 等 基 本方 法 和 技 能 ；3． 培 养 学 生 在 分 析 问 题 和 解 决 问 题 过 程 严 谨 的 科 学 态 度 和 良 好 的 工 作 作 风课程设计要求：1． 16周 周 1至 周 5完 成 选 题 、 问 题 分 析 、 算 法 设 计 、 程 序 编 写 、 程 序 测 试和 程 序 验 收 。
2． 按 照 课 设 格 式 提 交 课 程 设 计 报 告 3． 分 数 =80%程 序 +20%报 告课程设计题目课 程 设 计 题 一 ： 学 生 成 绩 管 理 系 统设 计 目 的 ：1. 掌 握 线 性 链 表 的 建 立 2. 掌 握 线 性 链 表 的 基 本 操 作 3. 加 深 对 线 性 链 表 及 其 基 本 操 作 的 理 解 设 计 内 容 ：利 用 线 性 链 表 实 现 学 生 成 绩 管 理 系 统 具 体 功 能 ： 输 入 、 输 出 、 插 入 、 删 除 、查 找 、 追 加 、 显 示 、 分 类 合 计 ， 并 能 在 屏 幕 上 输 出 操 作 前 后 的 结 果 设 计 要 求 ：1. 初 始 化 线 性 链 表 可 以 通 过 键 盘 输 入 ， 进 行 学 生 信 息 的 录 入 并 根 据 命 令 ，进 行 插 入 、 删 除 、 追 加 、 遍 历 、 分 类 合 计 等 操 作 2. 输 出 操 作 前 后 的 结 果 3. 如 果 有 时 间 ， 可 以 添 加 保 存 功 能 即 将 链 表 中 的 学 生 记 录 保 存 到 一 个 文 本 文件 中 。
课 程 设 计 题 二 ： 停 车 场 管 理 系 统设 计 目 的 ：1. 掌 握 栈 和 队 列 的 建 立 2. 掌 握 栈 和 队 列 的 基 本 操 作 3. 深 入 了 解 栈 和 队 列 的 特 性 ， 以 便 在 解 决 实 际 问 题 中 灵 活 运 用 它 们 4. 加 深 对 栈 和 队 列 的 理 解 和 认 识 设 计 内 容 ：设 有 一 个 可 以 停 放 n 辆 汽 车 的 狭 长 停 车 场 ， 它 只 有 一 个 大 门 可 以 供 车 辆 进出 车 辆 按 到 达 停 车 场 时 间 的 早 晚 依 次 从 停 车 场 最 里 面 向 大 门 口 处 停 放 (最 先 到达 的 第 一 辆 车 放 在 停 车 场 的 最 里 面 )如 果 停 车 场 已 放 满 n 辆 车 ， 则 后 来 的 车 辆 只 能 在 停 车 场 大 门 外 的 便 道 上 等待 ， 一 旦 停 车 场 内 有 车 开 走 ， 则 排 在 便 道 上 的 第 一 辆 车 就 进 入 停 车 场 停 车 场 内 如 有 某 辆 车 要 开 走 ， 在 它 之 后 进 入 停 车 场 的 车 都 必 须 先 退 出 停 车 场为 它 让 路 ， 待 其 开 出 停 车 场 后 ， 这 些 车 辆 再 依 原 来 的 次 序 进 场 。
每 辆 车 在 离 开 停 车 场 时 ， 都 应 依 据 它 在 停 车 场 内 停 留 的 时 间 长 短 交 费 编 制 一 程 序 模 拟 该 停 车 场 的 管 理 设 计 要 求 ：1. 以 栈 模 拟 停 车 场 ， 以 队 列 模 拟 车 场 外 的 便 道 ， 按 照 从 终 端 读 入 的 输 入 数 据 序列 进 行 模 拟 管 理 2. 每 一 组 输 入 数 据 包 括 三 个 数 据 项 ： 汽 车 “到 达 ”或 “离 去 ”信 息 、 汽 车 牌 照 号 码以 及 到 达 或 离 去 的 时 刻 3. 对 每 一 组 输 入 数 据 进 行 操 作 后 的 输 出 信 息 为 ： 若 是 车 辆 到 达 ， 则 输 出 汽 车 在停 车 场 或 便 道 上 的 停 车 位 置 ； 若 是 车 辆 离 去 ， 则 输 出 汽 车 在 停 车 场 内 停 留 的时 间 和 应 交 纳 的 费 用 (在 便 道 上 停 留 的 时 间 不 收 费 ， 功 能 可 自 己 添 加 )课 程 设 计 题 三 ： 约 瑟 夫 (Joseph)环设 计 目 的 ：1. 掌 握 单 向 循 环 链 表 的 建 立 。
2. 掌 握 单 向 循 环 链 表 的 操 作 3. 深 入 了 解 单 向 循 环 链 表 的 特 性 ， 以 便 在 解 决 实 际 问 题 中 灵 活 运 用 它 们 设 计 内 容 ：编 号 是 1， 2， … … ， n 的 n 个 人 ， 按 照 顺 时 针 方 向 围 坐 一 圈 ， 每 个 人 拥 有 一个 密 码 (正 整 数 ) 一 开 始 任 选 一 个 正 整 数 m， 从 第 一 个 人 开 始 顺 时 针 方 向 自 1开始 顺 序 报 数 ， 报 到 m 时 停 止 报 数 报 m的 人 出 列 ， 将 他 的 密 码 作 为 新 的 m值 ， 从他 的 顺 时 针 方 向 的 下 一 个 人 开 始 重 新 从 1 报 数 ， 如 此 下 去 ， 直 到 所 有 人 全 部 出 列为 止 请 设 计 一 个 程 序 求 出 出 列 顺 序 设 计 要 求 ：1. 利 用 单 向 循 环 链 表 存 储 结 构 模 拟 此 过 程 ， 按 照 出 列 的 顺 序 输 出 各 个 人 的 编 号 2. 测 试 数 据 ： m的 初 值 为 20， n=7， 7个 人 的 密 码 依 次 为 3， 1， 7， 2， 4， 7， 4，首 先 m=6， 则 正 确 的 输 出 是 什 么 ？3. 输 入 数 据 ： 建 立 输 入 函 数 处 理 输 入 的 数 据 ， 输 入 m的 初 值 ， 输 入 每 个 人 的 密码 ， 建 立 单 向 循 环 链 表 。
4. 输 出 形 式 ： 建 立 一 个 输 出 函 数 ， 将 正 确 的 出 列 顺 序 输 出 课 程 设 计 题 四 ： 哈 夫 曼 编 /译 码 器设 计 目 的 ：1. 掌 握 建 立 哈 夫 曼 树 和 哈 夫 曼 编 码 的 方 法 2. 掌 握 哈 夫 曼 编 码 的 实 际 应 用 方 法 设 计 内 容 ：利 用 哈 夫 曼 编 码 进 行 通 信 可 以 大 大 提 高 信 道 利 用 率 ， 缩 短 信 息 传 输 时 间 ， 降低 传 输 成 本 这 要 求 在 发 送 端 通 过 一 个 编 码 系 统 ， 对 待 传 数 据 预 先 编 码 ， 在 接 收端 将 传 来 的 数 据 进 行 译 码 对 于 双 工 信 道 (即 可 以 双 向 传 输 信 息 的 信 道 )， 每 端 都需 要 一 个 完 整 的 编 \译 码 系 统 试 为 这 样 的 信 息 收 发 站 写 一 个 哈 夫 曼 的 编 \译 码 系统 设 计 要 求 ：1. 初 始 化 根 据 下 表 给 出 的 英 文 字 母 的 使 用 频 度 ， 建 立 哈 夫 曼 树 。
空 格 ： 0.2 E： 0.105 T： 0.071 O： 0.0644A： 0.063 N： 0.059 I： 0.054 R： 0.053S： 0.052 H： 0.047 D： 0.035 L： 0.029C： 0.023 U： 0.0225 F： 0.0221 M： 0.021P： 0.0175 Y、 W： 0.012 G： 0.011 B： 0.0105V： 0.008 K： 0.003 X： 0.002 J、 Q： 0.001Z： 0.0012. 编 码 利 用 已 建 好 的 哈 夫 曼 树 ， 对 电 报 正 文 进 行 编 码 3. 译 码 对 编 码 好 的 内 容 进 行 译 码 4. 打 印 编 码 5. 打 印 哈 夫 曼 树 课 程 设 计 题 五 ： 图 的 遍 历 演 示设 计 目 的 ：1. 理 解 图 的 基 本 概 念 ， 熟 悉 图 的 各 种 存 储 结 构 及 其 构 造 算 法 2. 掌 握 图 的 遍 历 方 法 设 计 内 容 ：实 现 图 的 深 度 优 先 搜 索 、 广 度 优 先 搜 索 遍 历 算 法 ， 并 输 出 原 图 结 构 及 遍 历 结果 。
设 计 要 求 ：1. 首 先 利 用 邻 接 矩 阵 或 邻 接 表 构 建 图 ， 并 分 别 实 现 两 种 遍 历 方 法 2. 函 数 功 能 要 划 分 合 理 3. 画 出 流 程 图 4. 程 序 要 加 必 要 的 注 释 课 程 设 计 题 六 ： 交 通 咨 询 系 统 设 计设 计 目 的 ：1. 掌 握 图 的 概 念 和 其 常 用 的 存 储 结 构 ；2. 熟 练 掌 握 迪 杰 斯 特 拉 算 法 和 费 洛 伊 德 算 法 ， 能 够 利 用 它 们 解 决 最 短 路 径 问 题 设 计 内 容 ：设 计 一 个 交 通 咨 询 系 统 ， 能 让 旅 客 咨 询 从 任 一 个 城 市 定 点 到 另 一 个 城 市 定 点之 间 的 最 短 路 径 或 最 低 花 费 或 最 少 时 间 等 问 题 对 于 不 同 的 咨 询 要 求 、 可 输 入 城市 间 的 路 程 长 度 或 所 需 时 间 或 所 需 花 费 设 计 要 求 ：1. 建 立 交 通 网 络 网 的 存 储 结 构 2. 总 体 设 计 要 画 流 程 图 3. 提 供 程 序 测 试 方 案 。
课 程 设 计 题 七 ： 列 车 查 询 系 统设 计 目 的 ：1. 综 合 运 用 链 表 知 识 解 决 实 际 问 题 的 能 力 设 计 内 容 ：设 计 火 车 售 票 处 的 计 算 机 系 统 ， 可 以 为 客 户 提 供 下 列 各 项 服 务 ：1. 查 询 列 车 信 息 ： 根 据 旅 客 提 出 的 起 始 站 和 终 点 站 名 ， 或 者 列 车 车 次 ， 输出 下 列 信 息 ： 列 车 车 次 、 发 车 时 刻 、 到 达 时 刻 、 运 行 时 间 ， 以 及 每 个 途 经 站 点 的站 名 、 到 达 时 间 、 发 车 时 间 、 运 行 里 程 等 信 息 ；2. 录 入 列 车 信 息 ；3. 修 改 列 车 信 息 ；4. 删 除 列 车 信 息 ；5. 浏 览 所 有 列 车 信 息 ；6. 其 它 必 要 功 能 设 计 要 求 ：1. 要 求 采 用 链 表 方 式 存 储 所 有 列 车 车 次 基 本 信 息 （ 如 车 次 名 称 等 ） ， 对 于 其 中 的每。
