中南大学物理学院 （数据结构课程） 实验报告 实验名称： 哈弗曼编码和译码 专业班级： 电子信息科学与技术 0904 姓 名： 秦杰 学 号： 1404090506 指导教师： 胡志坤 2011年 11月 27 日 实 验 四 ： 哈 夫 曼 编 码 和 译 码 一 、 实 验 目 的 和 要 求 （ 1 ） 掌 握 哈 夫 曼 树 的 基 本 概 念 及 其 存 储 结 构 。 （ 2 ） 掌 握 哈 夫 曼 树 的 建 立 算 法 。 （ 3 ） 掌 握 哈 夫 曼 树 的 应 用 （ 哈 夫 曼 编 码 和 译 码 ）。 二 、 实 验 内 容 和 原 理 1.实 验 内 容 用 下 表 给 出 的 字 符 集 和 频 度 的 数 据 建 立 哈 曼 树 ,并 实 现 以 下 报 文 的 编 码 和 译码 ： “this*program*is*my*favourite”。 字 符 * a b c d e f g h i 频 度 186 64 13 22 32 103 21 15 47 57 字 符 j k l m n o p q r s 频 度 1 5 32 20 57 63 15 1 48 51 字 符 t u v w x y z 频 度 80 23 8 18 1 16 1 2.实 验 原 理 首 先 规 定 构 建 哈 夫 曼 树 ， 再 去 进 行 哈 夫 曼 树 的 编 码 ， 接 着 设 计 函 数 进 行 字符 串 的 编 码 过 程 ， 最 后 进 行 哈 夫 曼 编 码 的 译 码 。 定 义 一 个 结 构 体 ， 用 于 存 放 构 建 哈 夫 曼 树 所 需 要 的 所 有 变 量 ， 开 辟 一 块 地址 空 间 ， 用 于 存 放 数 组 ， 数 组 中 每 个 元 素 为 之 前 定 义 的 结 构 体 。 输 入 n个 字 符 及其 权 值 。 构 建 哈 夫 曼 树 ： 在 上 述 存 储 结 构 上 实 现 的 哈 夫 曼 算 法 可 大 致 描 述 为 ： 1.初 始 化 :将 ht[0„ m-1]中 2n-1个 结 点 里 的 三 个 指 针 均 置 为 空 ， 权 值 置 为0。 2.输 入 :读 入 n个 叶子的 权 值 存 于 向量 的 前 n个 分量 中 。它们是初 始 森林中n个 孤立 的 根结 点 上 的 权 值 。 3.合并 :对森林中 的 树 共进 行n-1次合并 ， 所 产生的 新结 点 依次放 入 向量ht的 第i 个 分量 中 。 每 次合并 分两步： ①在 当...
