哈弗曼编码,C实现二叉树的图形化输出,已经界面

软件工程学院软件工程学院 程序设计实践 下 实验程序设计实践 下 实验 报告报告 题目 题目 哈夫曼编码哈夫曼编码 译码器译码器 姓名 姓名 张张 祺祺 学号 学号 1010934510109345 班级 班级 软件工程软件工程 3 3 班班 一 一 问题解析 对问题的分析 解题思路与解题方法 问题解析 对问题的分析 解题思路与解题方法 问题主要分为三部分 分别是文件的操作 界面的设计 文件 的压缩 其中界面的设计和文件的压缩又是基于哈弗曼编码的 因 此 构造哈弗曼树和获取哈弗曼编码是程序的关键 1 文件的操作 程序中文件的操作主要是文件的读和写 关于这点 基本上 没有遇到什么问题 2 界面设计 前面已经提到 界面设计是基于哈弗曼树和哈弗曼树的小时 我分到了这一块 下面做介绍 由于哈弗曼树是正则二叉树 即对于每个结点 要么其左右孩子都 存在 要么都不存在 但对于树形结构来说 其变化多端 每一行 的结点数不确定 虽然第二层 第一层只有根结点 和最后一层结 点数没有任何确定的关系 但他们之间却有相互制约关系 即底层 结点的个数关系着上层 尤其是第二 三层 结点之间的距离 这 也是最难把握的地方 最初 我用矩阵保存同一层结点之间的关系 但后来发现 兄弟结 点的关系容易获得 但如果两结点不是兄弟结点而是堂兄结点时 这种关系就比较难找了 再不理想一点 如果两结点在的根结点父 节点来自不同的结点 这种关系就更难确定了 然后 我又想想到了从根结点出发仿照先序遍历的原理逐个打印 结点的信息 很快 我发现 这种方法也是不行的 原因在于在先 序遍历时可也借助栈或者递归栈来储存后面要访问的元素 但是想 要找到这个元素的具体位置比较难 所以这种方法也很快被否认 一直找不到可行的办法 想过用打表 也想过放弃 但是实在不想 一个原因是这是我的任务 如果我放弃或者做的不够完美 这将会 影响我们组所有同学的成绩 另一个原因就是我一直认为 只要是 能想的到的 就能用代码实现 这也是编程的精髓 无奈之下 我 开始查找资料 突然 一张满二叉树的图片 其实是一张家谱图 给了我灵感 我为什么要根据结点选位置呢 完全可也根据位置确 定这点的结点啊 所以我的最初构想是先打印出一个树形结构 然后根据每个结点的信息 将其输出到指定的位置 最后我就是用 这种方法做到的 3 构造哈弗曼树 获取哈弗曼编码 构造哈弗曼树的关键在于每次将权值最小的两个结点合并成一个 新结点 如此循环 直到只剩一个结点 在获取编码时 从每一个 叶子结点出发 访问哈弗曼树的根结点 所走过的路径刚好和编码 相反 二 任务分工及进度计划任务分工及进度计划 我们组的成员还有王倩 求春磊 章力挺 最初分工时 王倩 负责文件的读写操作 求春磊负责文件的编码压缩这一块 章力挺 负责构造哈弗曼树 获取哈弗曼编码这一块 我负责疏导图形化输 出 界面这一块 总体来说 小组的进度比较慢 原因在于第一个程序还没写好 而且我的任务在中间 只有有了哈弗曼编码才能进行树形结构的输 出 所以在开始时 前面的问题我也解决了 下面谈谈我的见解 文件的读写基本上没有什么大的问题 在统计字符频率时 我 统计了 128 个常见字符 用了点小算法 效率比较高 在构造哈弗 曼树时出现了瓶颈 究其原因 主要是以前没有接触过哈弗曼树 只有老师在上课时提到过 所以 面对一个新问题 首先需要时间 去熟悉 等到哈弗曼树构造完成 获取编码也就相应比较简单了 三 三 数据结构选择 算法设计数据结构选择 算法设计 前面已经提到 这个程序我基本上全都做了 现在就出现的问题 分析 1 统计字符频率 常见的字符有 128 个 如果检索一个一个判断 那样的代价 会很大的 由于 128 个字符分别对应 1 128 的 ASCII 码值 所 以可以定义一个 128 单元的数组 用字符代替下标 这样一来 对于每一个字符 其计算频率其出现一次 下标为该字符的元素 递增 1 这样可以高效的简单的统计每一个字符出现的频率 2 构造哈弗曼树 获取哈弗曼编码 在问题分析中叶提到 构造哈弗曼树的关键是每次将两个 权值最小的结点合并成一个新的结点 教材上采用 0 号元素不用 通过判断结点的父结点是否为 0 确定该结点是否要被计算 在我 的计算中 我用 0 号结点 而且另外开辟了一个存放结点权值的 副本数组 这样一来 每次都是对结点判断 被合并的结点权值 变为 1 最后用副本还原所有结点的权值 结点的结构体定义如 下 struct Hafuman int weight 权值 3 int parent 父结点的位置 int left child 左孩子的位置 int right child 右孩子的位置 在构造哈弗曼树时 所有结点 包括本来有权值的结点和 通过合并的到新的权值的结点 其地位是等价的 因此 最好 把两种结点放在一起 这样方便访问 所以在有 128 种字符的前 提下 开辟 128 2 个结点 前 128 个结点存放本来就有权值的结 点 后 127 个结点存放新合成的结点 这样一来 访问两种结点 就只需要一个循环 由于 128 个结点不是很大 所以用线性结构 的数组存储 在获取哈弗曼编码时 由于是从前 128 个结点中有权值的 结点开始访问根的 因此访问得到的编码正好和要得到的哈弗曼 编码相反 估只需逆转就可得到哈弗曼编码 3 图形化输出树形结构 前面提到 在输出树形图时采用有点类似模板的方法输出 树 即先打印全部树枝 再根据情况条件树叶 最后擦掉多余的 树叶 但是 这种方法任然有缺陷 根据二叉树的性质 第 k 层 的结点个数最多为 2k 1 当是第 7 层时 需要结点 26即 64 个结 点 尽管对界面的宽度做了扩展 但在一列打印 64 个结点仍然 很难做到 或者即使做到 效果也不一定理想 所以最后树的深 度在 6 以内 即对于深度大于 6 的树 只输出前 6 层 在打印树形结构时 将每一层第一个结点所在的坐标记录 下来 在打印结点时首先找到这个坐标 这样一来 每层头结点 坐标相当于提供了一个借口 由于已经打印出了满二叉树的树枝 这样一来当这个位置 没有结点时 最好把它坐在的树枝擦掉 以免影响美观 擦除和 打印的类似 不同的是擦除只是打印空格 为了界面美观 我将树枝的颜色和结点的分成了两种 定 义了 color int n 函数这个函数的功能在于调用这个函数的时候 光标打印出的字符全部变为指定的颜色 4 编程与程序清单编程与程序清单 前面已经提到 这个程序的大部分问题我自己都解决了 现做 一下说明 1 统计字符频率 在定义好结点的结构后首先声明一个 2 N 大小的数组 为了 所有函数调用的方便 把这个数组声明为全局变量 首先是打开文件 if fp fopen C hafuman txt r NULL printf cannot open the file n exit 0 等打开文件后 通过一次循环就可以统计所有字符的频率 c fgetc fp while c EOF a c a N 是结点权值的副本是结点权值的副本 node c weight 结点权值递增结点权值递增 length 统计文件长度的变量递增统计文件长度的变量递增 c fgetc fp 获取下一个字符获取下一个字符 就这样 只需要循环一次就可以得到所有结点的权值 在打印统计结果时 我用了表格 由于有些特殊字符 比如 换行 r 回车 n 空格 tab t 等键无法打印 或者即使 打印出来也看不见 所以 对于特殊字符 我输出了他们的中文名 称 由于有 128 个字符 如果使用同一种颜色打印 未免太单调 而且不易区分 所以 我有分别设定了表格 字符 出现次数的 颜色 把它们区分开来 最后的效果如下 就这样 完全打印输出了 128 个字符出现的频率 在这里特别声明 由于默认的窗口太小 我用了拓展窗口的函数 system mode con cols 130 lines 38 这即表示窗口是 130 列 38 行 同样方法 在打印哈弗曼编码时也用该方法 效果如下 2 构造哈弗曼树 获取哈弗曼编码 由于前面已经统计了每个字符出现的频率 这些频率就是字符 的权值 构造哈弗曼树的关键点是每次将权值最小的两个结点合并 成一个结点 而且保证合并过的结点此后不会再被统计 我设计是 将没出现的字符频率即权值初始为 1 出现的 其权值就是 1 2 3 4 这样避开了 0 的特殊性 由于在统计字符时 统计 的是最小的 而 0 也可以算是最小的 这样会带来不便 所以 直 接用正 负两种状态区别 具体代码如下 void Greate Hafu int min 1 min 2 int Left Right int i for i N i 2 N i Find Min min 1 min 2 Left Right 找到两个权值最小的结点 最小权值为 min 1 min 2 最小 权值所在位置为 Left Right if Right 1 有最小两结点 node i weight min 1 min 2 新结点 a i node i weight a N 与 node weight N 同步 a Left node Left weight a Right node Right weight node i left child Left node i right child Right 新增了结点 该结点是刚最小权值两结点的父结点 node Right parent i node Left parent i 当前最小两结点的根结点为刚产生的新结点 node Right weight node Left weight 1 当前权值最小的两结点权值清 0 以便后面的选择 for i 0 i 2 N i node i weight a i 最后对所以结点的权值还原 由于前 N 个结点存放都是出现字符的权值 所以在合并新结点 时 新结点的位置一定在 N 2 N 直接 所以在访问 1 N 之间的 元素时 循环用的是 for i N i 2 N i 这样当找到两个权值 最小的结点时 将其权值赋值给一个新的结点 而这个新结点一定 在 N 2 N 之间 找到的权值最小的两个结点其父结点都指向了新 的结点 为新结点的左 右孩子也分别指向了两个权值最小的结点 这一年以来 相当于建立了一个双向二叉树 即通过父结点可以直 接找到其左 右孩子结点 也可以通过左 右孩子结点直接找到其 父结点 这么做的原因主要是为了后面获取哈弗曼 编码的方便 由于已经建立好了哈弗曼树 那么 获取哈弗曼编码的过程就 是从叶子结点出发 访问根结点的过程 具体代码如下 void Get Code char str 2 N 声明一个临时存储编码的数组 for int i 0 i 0 权值为正时才可能有父结点 只有权值不为 1 的结点才有其父结点 int p i k 0 j 0 memset str 0 sizeof str 临时数组全部置 0 找到了一个有权值的结点时 需要从此结点出发 访问根结点 while node p weight 0 int parent node p parent if node node p parent left child p 判断是当前结点是左孩子 str k 0 左为 0 else if node parent right child p str k 1 右为 1 p parent parent node parent parent 父结点继续访问根 这个循环相当于是递归的过程 while k hafucode i j str k 最后编码赋值 是逆序编码 由于 0 2 N 之间的每一个结点都可能存有有权值的结点 所 以循环是从 0 2 N 由于前 N 个结点存放的是本来就有结点的权 值 也就是说 前 N 个结点存放的恰恰是叶子结点 其所在的位置 也应该是树的最下层 其父结点一定在 N 2 N 之间 但是 由于 N 2 N 之间的结点可能还有父结点 因此在 N 2 N 之间也要循 环 最后到 01 字符串是从下往上的编码 而真正的 哈弗曼编码又 是从上到下的 刚好相反 所以需要逆转 3 图形化输出 前面已经说了 我图形化输出时 先打印了树形结构 在打印 各个结点 在打印树枝时 我用了暴力的方法 即一层一层输出 并没有用规律循环 但是 规律肯定是有的 只是我的深度只有 6 找规律还不如直接打印来的快 最初打印的树枝图如下所示 这样一来 在打印结点时只需找到其所在层的入口 int x 1 y END 10 local 5 0 x local 5 1 y gotoxy x y 1 for i 0 i 16 i printf x 3 y 2 local 4 0 x local 4 1 y gotoxy x 1 y 1 for i 0 i 8 i printf t t 其中 local 5 5 是声明的每一层入口坐标的起始坐标的全局变量 上述代码实现了第 6 5 层树枝的打印 上面所示图形是左右完全对称的 但是 在打印结点时 由于 仅仅知道每层的入口地址 而不知道某个结点的具体位置 因此在 打印结点时需慢慢尝试 for i 0 i 2 N i 第一个 if node p left child i Print Data local 3 0 local 3 1 i for i 1 0 i 1 2 N i 1 if node i left child i 1 Print Data local 4 0 local 4 1 i 1 break for i 1 0 i 1 2 N i 1 if node i right child i 1 Print Data local 4 0 8 local 4 1 i 1 break for i 1 0 i 1 2 N i 1 if node node i left child left child i 1 Print Data local 5 0 local 5 1 i 1 break for i 1 0 i 1 2 N i 1 if node node i left child right child i 1 Print Data local 5 0 6 local 5 1 i 1 break for i 1 0 i 1 2 N i 1 if node node i right child left child i 1 Print Data local 5 0 8 local 5 1 i 1 break for i 1 0 i 1 0 if i N if i 10 printf 换 if i 32 printf 空 特殊字符打印中文名称 else printf c i 如果是出现的字符 为了直观 打印字符 else printf d node i weight 是新合并的结点时只需打印权值即可 else 通过判断 node node i child weight 来擦除 if y local 5 1 第 6 层的擦除 int k for k 0 k 130 k if 1 k 8 x gotoxy x 1 y 1 printf break for k 0 k 130 k if 7 k 8 x gotoxy x 1 y 1 printf break if y local 4 1 第 5 层的擦除 gotoxy x 1 y 1 printf gotoxy x 7 y 1 printf if y local 3 1 第 4 层的擦除 for k 0 k 3 k gotoxy x k 1 y 1 printf x y y 3 x 3 for k 0 k 3 k gotoxy x 14 k y 1 printf x y if y local 2 1 第 3 层的擦