哈夫曼编码译码器

1 20 哈夫曼编码译码器 学院班级 信息工程学院 软件 1501 指导教师 朱俊武 小组成员 刘洋 蒋佳烨 冀若含 本人学号 报告书写 冀若含 学生成绩 2 20 目录 一 总体介 绍 03 04 二 详细设 计 04 11 三 运行测 试 11 12 四 课设总 结 13 13 五 附录代 码 13 19 3 20 一 总体介绍 1 1 任务概述 我们小组做了两个版本 其中一个为文件操作版 另一个为键盘 操作版 两个版本都实现了哈夫曼编码 译码操做 我主要负责的是 构造哈夫曼树 给出各个字符的哈夫曼编码 加密操做 整个键盘 操作版系统的代码重组 编辑 开发的过程中使用了 Codelite Dev Vc 等软件 参考书籍为 数据结构 c 语言版 其中文件操作版的具体实现为 能够实现对 26 个小写字母外加空格进行哈夫曼编码 并能够对一 1 整篇文章 有小写字母和空格组成 进行加密 生成密码文件 最 后根据生成的密码翻译出原文并存档 在使用程序时 使用者只需要对 ToBetran 文件进行原文的输入 2 4 20 使用小写字母或空格 加密和解密功能由程序自主来完成 程序运行的过程中会输出进行编码的 26 个小写字母和空格 字符 3 型 并输出其对应的权值 整型 还输出字符的编码及生成的密 文 最后输出解密后的原文 键盘操作版为 要求从键盘输入字符集和字符的权值 大部分字符均可输入 需 1 要各个字符的权值不能相同 利用输入的权值建立哈夫曼树 得到每个字符的前缀编码 2 输入字符串 程序对其进行加密 3 输入密文 对密文进行解密 4 两个版本都利用了哈夫曼树解决问题 通过建立哈夫曼树 得出 每个字符的独特前缀编码 也就是密文 然后利用密文对明文进行 加密得到密文 密文转换为明文则是通过对哈夫曼树的遍历 之前 想过字符串的匹配得到明文但是算法太为复杂 1 2 系统功能框图 开始 构建哈夫 曼树 编码译码 本系统分为三个大的模块 构造哈夫曼树 编码 译码 5 20 1 3 功能难点 本系统的实现难点在于哈夫曼树的构造 编码 译码功能的实现 都是基于哈夫曼树的 二 详细设计 2 1 哈夫曼树的构造 哈夫曼树 又称最优树 是一类带权路径长度最短的树 有着广 泛的应用 哈夫曼树的构造过程如下 1 初始化 根据给定的 n 个权值 w1 w2 wn 构成 n 棵二叉树的集 合 F T1 T2 Tn 其中每棵二叉树 Ti 中只有一个带权 wi 的根 节点 左右子树均空 2 找最小树 在 F 中选择两棵根结点权值最小的树作为左右子树构 造一棵新的二叉树 且至新的二叉树的根结点的权值为其左右子树 上根结点的权值之和 3 删除与加入 在 F 中删除这两棵树 并将新的二叉树加入 F 中 4 判断 重复前两步 2 和 3 直到 F 中只含有一棵树为止 该树 即为哈夫曼树 2 2 代码实现 哈夫曼树和哈夫曼编码的储存表示 typedef struct int weight int parent lchild rchild HTNode HuffmanTree 动态分配数组储存哈夫曼树 6 20 typedef char HuffmanCode 动态分配数组储存哈夫曼编码表 void Select HuffmanTree HT int p int s1 int s2 该函数的功能为 找出 HT 1 i 1 中 parent 为 0 且 weight 最小的两 个结点 其序号为 s1 s2 void HuffmanCoding HuffmanTree HT HuffmanCode HC int w int n char a 该函数的功能为构造哈夫曼树 HT 并求出 n 个字符的哈夫曼编码 HC 以下为两个函数的流程图或详细设计 void HuffmanCoding HuffmanTree HT HuffmanCode HC int w int n char a 7 20 M 2 n 1 开始 为HT申请长度为m 1的内存 空间 给HT数组的前n个赋值为 w 0 0 0 给HT数组的后n 1个赋值为 0 0 0 0 i n 1 Select HT s1 parent I Ht s2 parent I Ht i lchild s1 Ht i rchild s2 Ht i weight HT s1 weight HT s2 weight i i m Y N weiHC指针 分配空间 指针 a 指向输入的字符集 指针 w 指向字符集的度 n 为字符集的 大小 注 具体程序中加入了输出各个字符的哈夫曼编码的功能 在流程 图没有显示 没画完下面还有哟 8 20 weiHC指针 分配空间 为cd分配纯储存空间 Cd n 1 0 i 1 Start n 1 C I F HT I PARENT HT F LCHILD C Y CD START 0 N Cd start 1 C f f HT f p arent F 0 Y N 为第i个字符分配空 间 复制cd到HC i N N Free cd Y 详细代码 void HuffmanCoding HuffmanTree HT HuffmanCode HC int w int n char a int m 0 int c int f int start char cd int s1 int s2 int i s1 int malloc sizeof int s2 int malloc sizeof int m 2 n 1 if n 1 printf 字符的个数过少 n return 9 20 HuffmanTree p p HT p for i 1 iweight w p parent 0 p lchild 0 p rchild 0 for iweight 0 p parent 0 p lchild 0 p rchild 0 for i n 1 i m i Select HT i 1 s1 s2 HT s1 parent i HT s2 parent i HT i lchild s1 HT i rchild s2 HT i weight HT s1 weight HT s2 weight cd char malloc n sizeof char cd n 1 0 for i 1 i n i start n 1 for c i f HT i parent f 0 c f f HT f parent if HT f lchild c cd start 0 else cd start 1 HC i char malloc n start sizeof char strcpy HC i printf c a a printf s n HC i free cd void Select HuffmanTree HT int p int s1 int s2 详细设计 首先通过一个循环找出当前数组中 weight 最小的一个 记录下它 1 10 20 的序号 也是一和一样的循环和算法 加上一个 if 语句 如果循环到与第 2 一次序号一样的那次 就 continue 跳过这次比较 将得到的权值最小的两个传到 s1 和是 s2 指向的地址 3 这就是哈夫曼树的构造和生成哈夫曼编码的过程 详细代码 void Select HuffmanTree HT int p int s1 int s2 i 为遍历长度 int i 1 int x 0 int y 0 int min 1000 int min1 1000 int v 1 s1 1 s2 1 for i 1 iy min HT i weight s1 i v i for i 1 i y min1 HT i weight s2 i 11 20 2 3 编码 加密 void HuffmanEncryption HuffmanCode HC char a int n 此函数 为加密函数 该加密函数的流程图如下 开始 从键盘读入要加密的字 符串 i 0 J 0 Input i a j Y 输出HC j 1 J N J N Y N I I LO N Y 结束 该功能的实现就是通过一个简单的查找 通过字符与字符的哈夫曼 编码在不同数组的对应关系 进行加密 Input 储存输入的字符串 Lo 为输入的字符串长度 n 为原字符集的字符个数 详细代码如下 12 20 void HuffmanEncryption HuffmanCode HC char a int n char input 100 int i 0 j 0 char lu int lo 0 要加密的字符串的长度 char c printf 请输入你要加密的字符串 n while lu getchar n c getchar while c n input i c i c getchar lo i for i 0 i lo i for j 0 j n j if input i a j printf s HC j 1 printf n 三 运行测试 菜单界面 13 20 构造哈夫曼树 编码 14 20 译码 密钥 译码测试 四 总结 经过几天的设计与编码我们小组终于完成了两个不同的版本的哈 夫曼编码译码器 虽然两个系统大部分的算法相同 但是也算我们 的尝试 美中不足的是我们没能把两个版本的系统融合起来 开发 过程中遇到的最大的问题就是输入输出流的问题 因为是从键盘输 入数据的所以难免会遇到这种问题 我通过输入流的过滤解决了此 问题 通过这几天的实验 加深了我对哈夫曼树的理解 也加强了 自己的动手能力 数据结构这门课程还有很多很多的东西 我们仍 应该继续努力 15 20 附录全部代码 include include include include typedef struct int weight int parent lchild rchild HTNode HuffmanTree typedef char HuffmanCode void Select HuffmanTree HT int p int s1 int s2 i 为遍历长度 big int i 1 int x 0 int y 0 int min 1000 int min1 1000 int v 1 s1 1 s2 1 for i 1 iy min HT i weight s1 i v i for i 1 i y min1 HT i weight s2 i void HuffmanCoding HuffmanTree HT HuffmanCode HC int w int n char a int m 0 int c int f 16 20 int start char cd int s1 int s2 int i s1 int malloc sizeof int s2 int malloc sizeof int m 2 n 1 if n 1 printf 字符的个数过少 n return HuffmanTree p p HT p for i 1 iweight w p parent 0 p lchild 0 p rchild 0 for iweight 0 p parent 0 p lchild 0 p rchild 0 for i n 1 i m i Select HT i 1 s1 s2 HT s1 parent i HT s2 parent i HT i lchild s1 HT i rchild s2 HT i weight HT s1 weight HT s2 weight cd char malloc n sizeof char cd n 1 0 for i 1 i n i start n 1 for c i f HT i parent f 0 c f f HT f parent if HT f lchild c cd start 0 else cd start 1 HC i char malloc n start sizeof char strcpy HC i printf c a 17 20 a printf s n HC i free cd void HuffmanEncryption HuffmanCode HC char a int n char input 100 int i 0 j 0 char lu int lo 0 要加密的字符串的长度 char c printf 请输入你要加密的字符串 n while lu getchar n c getchar while c n input i c i c getchar lo i for i 0 i lo i for j 0 j n j if input i a j printf s HC j 1 printf n void Huffmandeciphering HuffmanCode HC char a int n HuffmanTree HT 解密 int input 100 0 char c int num 0 int m 1 int t 0 printf 请输入你要解密的字符串 n int i 0 getchar while c n c getchar input i int c 48 i 18 20 num i for i 1 t 0 i if HT i parent 0 t i 根结点的位置 m t for i 0 i scanf c switch choice case a case A system cls view getchar break case b case B pri