北邮数据结构实验报告实验三哈夫曼

《北邮数据结构实验报告实验三哈夫曼》由会员分享，可在线阅读，更多相关《北邮数据结构实验报告实验三哈夫曼（8页珍藏版）》请在金锄头文库上搜索。

1、北 京 邮 电 大 学 信 息 与 通 信 工 程 学 院第 1页数 据 结 构 实 验 报 告实 验 名 称 ： 实 验 三 哈 夫 曼 编 /解 码 器 的 实 现学 生 姓 名 ： 侯 在 鹏班 级 ： 2012211120班 内 序 号 ： 13学 号 ： 2012210583日 期 ： 2013年 12月 10日1实验要求利 用 二 叉 树 结 构 实 现 赫 夫 曼 编 /解 码 器 。基 本 要 求 ：1、 初 始 化 (Init)： 能 够 对 输 入 的 任 意 长 度 的 字 符 串 s进 行 统 计 ， 统 计 每 个字 符 的 频 度 ， 并 建 立 赫 夫 曼 树2、

2、 建 立 编 码 表 (CreateTable)： 利 用 已 经 建 好 的 赫 夫 曼 树 进 行 编 码 ， 并 将 每个 字 符 的 编 码 输 出 。3、 编 码 (Encoding)： 根 据 编 码 表 对 输 入 的 字 符 串 进 行 编 码 ， 并 将 编 码 后 的字 符 串 输 出 。4、 译 码 (Decoding)： 利 用 已 经 建 好 的 赫 夫 曼 树 对 编 码 后 的 字 符 串 进 行 译 码 ，并 输 出 译 码 结 果 。5、 打 印 (Print)： 以 直 观 的 方 式 打 印 赫 夫 曼 树 （ 选 作 ）6、 计 算 输 入 的 字 符

3、串 编 码 前 和 编 码 后 的 长 度 ， 并 进 行 分 析 ， 讨 论 赫 夫 曼编 码 的 压 缩 效 果 。测 试 数 据 ：IlovedataStructure,IloveComputer。 IwilltrymybesttostudydataStructure.提 示 ：1、 用 户 界 面 可 以 设 计 为 “ 菜 单 ” 方 式 ： 能 够 进 行 交 互 。2、 根 据 输 入 的 字 符 串 中 每 个 字 符 出 现 的 次 数 统 计 频 度 ， 对 没 有 出 现 的字 符 一 律 不 用 编 码 。2.程序分析北 京 邮 电 大 学 信 息 与 通 信 工 程

4、学 院第 2页2.1存储结构程 序 实 现 了 基 本 的 编 解 码 功 能输 入 字 符 串选 择 工 作 目 标编 码解 码相 关 树 ， 表 显 示编 码 上根 节 点 向 下 ， 左 0右 1根 据 不 同 字 符 在 尾 端 相 应 排 位 ,获 得 自 己 的 编 码 ， 存 储 。解 码 上依 次 读 取 数 据 0或 1， 循 序 寻 找 ，最 后 在 存 储 中 找 到 对 应 编 码 的 字 符 ， 输 出再 重 新 读 取 下 一 数 字 开 始 的 数 码在 哈 夫 曼 树 编 码 这 个 程 序 中 ， 所 有 数 据 用 的 存 储 结 构 都 是 顺 序 存 储

5、 结 构 ， 其 中 包 括 顺 序 表 和树 （ 三 叉 树 ） 树 的 存 储 结 构 如 下 ： （ 输 入 的 字 符 串 为 assddddffffffffgggggggggggggggg）0 1 2 3 4 5 6 7 8ASC 9 115 100 102 103weight 1 2 4 8 16 3 7 15 31lchild -1 -1 -1 -1 1 0 2 3 4rchild 1 1 1 1 1 1 5 6 7parent -5 5 -6 -7 -8 6 7 8 0上 结 构 图 中 ， 填 充 为 黄 色 的 部 分 为 写 入 内 存 中 的 部 分 。 每 一 行 的

6、 部 分 为 数 组 的 下 标 ， 左边 部 分 为 所 定 义 的 结 构 的 成 员 。 其 中 有 的 结 点 的 父 节 点 的 下 标 是 一 个 负 数 ， 用 来 说 明 该 节 点是 该 节 点 的 父 节 点 的 左 孩 子 ， 正 数 说 明 的 是 该 节 点 的 父 节 点 的 右 孩 子 。 父 节 点 这 零 的 节 点 说明 该 节 点 是 该 哈 夫 曼 树 的 根 节 点 。 画 出 树 的 结 构 如 下 画 所 示 ： （ 结 点 中 第 一 个 数 表 示 这 个 字符 的 ASC 编 码 ， 第 二 个 数 字 表 示 权 值 ）北 京 邮 电 大

7、学 信 息 与 通 信 工 程 学 院第 3页37153116 1028 9711004 11528 7 6 54 3 2 1 00 0 0 010 1 1 1红 色 箭 头 表 示 父 指 针 ， 黑 色 箭 头 表 示 孩 子 指 针由 上 面 的 图 可 知 ， 原 字 符 串 编 码 后 的 二 进 制 编 码 为11101111111111011011011010101010101010100000000000000000字 符 串 中 出 现 的 所 有 的 字 符 的 编 码 如 下 ：a 1110；s 1111；d 110；f 10；g 02.2关键算法分析2.2.1选 择 两

8、 个 最 小 权 值 的 函 数算 法 伪 代 码 ：(1) 初 始 化 最 小 权 值 min1,min2.可 引 用 变 量 x,y。(2) 遍 历 哈 夫 曼 树 ， 比 较 字 符 的 权 值 与 min1,min2的 大 小 。 若 小 于 min1， 则 将 min1值 赋 给min2,字 符 权 值 赋 给 min1,同 时 改 变 权 值 最 小 的 结 点 编 号 x,y.若 大 于 min1 同 时 小 于 min2,则 将 字 符 权 值 赋 给 min2， 改 变 y值 。源 代 码 ：voidHuffman:SelectMin(int&x,int&y,inta,int

9、b)/选 出 两 个 权 值 最 小 的 结 点 intj,min1,min2;min1=min2=-1;for(j=a;jb;j+)if(HTreej.parent=-1) if(HTreej.weightmin1|min2=-1) if(min1!=-1)北 京 邮 电 大 学 信 息 与 通 信 工 程 学 院第 4页 min2=min1;y=x;min1=HTreej.weight;x=j;else if(HTreej.weightmin2|min2=-1) min2=HTreej.weight;y=j;时 间 复 杂 度 ： 遍 历 链 表 ， 时 间 复 杂 度 为 O（ n）2.

10、2.2.创 建 哈 夫 曼 树算 法 伪 代 码 ：(1)创 建 一 个 长 度 为 2*n-1的 三 叉 链 表(2)将 存 储 字 符 及 其 权 值 的 链 表 中 的 字 符 逐 个 写 入 三 叉 链 表 的 前 n个 结 点 的 data域 ， 并 将对 应 结 点 的 孩 子 域 和 双 亲 域 赋 为 空(3)从 三 叉 链 表 的 第 n个 结 点 开 始 ， i=n(3.1)从 存 储 字 符 及 其 权 值 的 链 表 中 取 出 两 个 权 值 最 小 的 结 点 x,y， 记 录 其 下 标 x,y。(3.2)将 下 标 为 x和 y的 哈 夫 曼 树 的 结 点 的

11、 双 亲 设 置 为 第 i个 结 点(3.3)将 下 标 为 x的 结 点 设 置 为 i结 点 的 左 孩 子 ， 将 下 标 为 y的 结 点 设 置 为 i结 点 的 右孩 子 ， i结 点 的 权 值 为 x结 点 的 权 值 加 上 y结 点 的 权 值 ， i结 点 的 双 亲 设 置 为 空(4) 根 据 哈 夫 曼 树 创 建 编 码 表voidHuffman:CreateHTree(inta,intn) HTree=newHNode2*n-1;for(inti=0;in;i+) HTreei.weight=ai;HTreei.LChild=-1;HTreei.RChild=

12、-1;HTreei.parent=-1;intx,y;for(inti=n;i2*n-1;i+) SelectMin(x,y,0,i);/从 0i中 选 出 两 个 权 值 最 小 的 结 点HTreex.parent=HTreey.parent=i;/用 两 个 权 值 最 小 的 结 点 生 成 新 结 点 ， 新 节 点 为 其 双北 京 邮 电 大 学 信 息 与 通 信 工 程 学 院第 5页亲 HTreei.weight=HTreex.weight+HTreey.weight;/新 结 点 的 权 值 为 其 孩 子 的 权 值 的 和HTreei.LChild=x;HTreei.

13、RChild=y;HTreei.parent=-1;时 间 复 杂 度 ：在 选 取 两 个 权 值 最 小 的 结 点 的 函 数 中 要 遍 历 链 表 ， 时 间 复 杂 度 为 O(n),故 该 函 数的 时 间 复 杂 度 为 O（ n2）2.2.3编 码 函 数算 法 伪 代 码 ：（ 1） 从 a开 头 的 字 符 开 始 ， 逐 一 对 a中 的 字 符 进 行 编 码（ 2） 在 编 码 表 中 查 找 与 当 前 字 符 对 应 的 字 符（ 3） 如 果 找 到 了 与 当 前 字 符 对 应 的 编 码 表 中 的 字 符 ， 将 其 编 码 追 加 到 解 码 串 的

14、 末尾 。（ 4） 重 复 以 上 步 骤 ， 直 到 所 有 待 编 码 串 中 的 字 符 都 编 码 完 毕（ 5） 输 出 编 码 后 的 字 符 串voidHuffman:Encode(chara,char*d,intn,intj) /a为 原 始 字 符 串 ， d 为 编 码 后 的 哈夫 曼 编 码 字 符 串 ， n为 编 码 表 长 度 ， j为 原 始 字 符 串 的 长 度 for(intm=0;mj;m+) for(inti=0;in;i+)if(am=HCodeTablei.data) d=strcat(d,HCodeTablei.code);cout编 码 后 的

15、 哈 夫 曼 编 码 字 符 串 为 ： dendl;时 间 复 杂 度 ： 设 待 编 码 字 符 串 长 度 为 n， 编 码 表 中 字 符 个 数 为 m， 则 复 杂 度 为 O（ n*m）2.2.4解 码 函 数算 法 伪 代 码 ： (1)得 到 指 向 哈 夫 曼 树 的 根 结 点 的 指 针 和 指 向 待 解 码 串 中 的 第 1个 字 符 的 指 针(2)逐 个 读 取 待 解 码 串 中 的 字 符 ， 若 为 0， 则 指 向 哈 夫 曼 树 当 前 结 点 的 指 针 指 向当 前 结 点 的 左 孩 子 ， 若 为 1， 则 指 向 当 前 结 点 的 右 孩

16、 子(3)指 向 待 解 码 串 的 指 针 指 向 解 码 串 中 的 下 一 个 字 符 ， 直 到 指 向 哈 夫 曼 树 结 点 的指 针 的 孩 子 结 点 为 空(4)如 果 指 向 哈 夫 曼 树 结 点 的 指 针 的 孩 子 结 点 已 经 为 空 ， 则 将 叶 子 结 点 下 标 对 应北 京 邮 电 大 学 信 息 与 通 信 工 程 学 院第 6页的 字 符 追 加 到 解 码 串 中 。(5)输 出 解 码 串源 代 码 ： voidHuffman:Decode(char*s,char*d,intn)/解 码 。 s为 编 码 后 的 数 组 ， d 为 解 码后 的 数 组 while(*s!=0) intparent=2*n-1