哈夫曼编码译码

哈夫曼编码 译码 一 实验内容 问题描述 利用哈夫曼编码进行住处通讯可以大大提高信道利用率 缩短住处 传输时间 降低成本 但是 这要求在发送端通过一个编码系统将传输的 数据预先编码 在接收端通过一个译码系统对传来的数据进行译码 复 原 对于双向传输信息的信道 每端都一个完整的编码译码系统 试为这 样的住处收发站写一个哈夫曼友的编码译码系统 基本要求 一个完整的系统应以下功能 1 I 初始化 Initialization 从终端读入字符集大小 n 以及 n 个 字符和 n 个权值 建立哈夫曼树 并将它存放在文件 hfmTree 中 2 E 编码 Encoding 利用已建立好的哈夫曼树 如不在内存 则从文件 hfmTree 中读入 对文件 ToBeTran 中的正文进行编码 然后将结果代码存 传输 到文件 CodeFile 中 3 D 译码 Decoding 利用已建好的哈夫曼树 对传输到达的 Co deFile 中的数据代码进行译码 将译码结果存入文件 TextFile 中 4 P 印文件代码 Print 将文件 CodeFile 以紧凑格式显示在终端 上 每行 50 个代码 同时将此字符形式的编码文件写入文件 CodePr in 中 5 T 印哈夫曼树 TreePrinting 将已在内存中的哈夫曼树以直观 的方式 树或凹入表的形式 显示在终端上 同时将此字符形式的哈夫 曼树写入文件 TreePrint 中 测试数据 1 利用教科书例 6 2 中的数据调试程序 2 用下表给出的字符集和频度的计数据建立哈曼树 并实现以下报文 的编码和译码 THIS PROGRAM IS MY FAVORITE 字符 A B C D E F G H I J K L M 频数 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频数 57 63 15 1 48 51 80 23 8 18 1 16 1 二 实验目的 树型结构是一种应用极为广泛的非线性数据结构 也是本课程的重点内 容 哈夫曼树 最优二叉树 是树型结构的典型应用 本次实验突出了数据 结构加操作的程序设计观点 希望能根据树型结构的非线性特点 熟悉各 种存储结构的特性 达到如何应用树型结构的非线性特点 熟悉各种存储 结构的特性 达到如何应用树型结构解决具体问题的目的 三 实验文档 哈夫曼编码 译码 一 需求分析 1 利用哈夫曼编码进行信息通信可以大大提高信道利用率 缩短信 息传输时 间 降低传输成本 但是 这要求在发送端通过一个编码系统对待传 数据预先编码 在接收端将传来的数据进行译码 复原 对于双工 信道 既可以双向传输信息的信道 每端都需要一个完整的编 译码 系统 本次设计就是为这样的信息收发站写的一个哈夫曼的编 译码器 本实验要求 2 本演示程序中 用户可以输入键盘中的任意字符 长度为任意长 字符输入顺序不限 且允许出现重码 3 演示程序以用户与计算机的对话方式执行 即在计算机终端上显示 提示信息 之后 由用户在键盘上输入演示程序中规定的运算命令 相应的输入数据 可虑去输入中的非法字符 和运算结果显示在其后 4 本演示程序中 当用户选择的功能错误时 系统会输出相应的提示 5 在本系统中 用户可以对任意长的字符串可进行编码 译码 6 程序执行的命令包括 1 初始化 I 2 编码 E 3 译码 D 4 印代码文件 P 5 印哈夫曼树 T 6 退出 Q 测试数据 利用教科书例 6 2 中的数据调试程序 用下表给出的字符集和频度的计数据建立哈曼树 并实现以下报 文的 编码和译码 THIS PROGRAM IS MY FAVORITE 字符 A B C D E F G H I J K L M 频数 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频数 57 63 15 1 48 51 80 23 8 18 1 16 1 二 概要设计 为实现上述程序功能 应以指针存储结点 为此 需要定义一个抽象 数据类型 1 抽象数据类型定义为 ADT HuffmanTree 数据对象 D ai ai CharSet i 1 2 n n 0 数据关系 R ai 1 ai D ai 1 ai i 2 3 n 基本操作 P HuffmanTree 构造函数 HuffmanTree 析构函数 Initialization int WeightNum 操作结果 构造哈夫曼树 Encoder 初始条件 哈夫曼树已存在或者哈夫曼树已存到文件中 操作结果 对字符串进行编码 Decoder 初始条件 哈夫曼树已存在且已编码 操作结果 对二进制串进行译码 Print 初始条件 编码文件已存在 操作结果 把已保存好的编码文件显示在屏幕 TreePrinting 初始条件 哈夫曼树已存在 操作结果 将已在内存中的哈夫曼树以直观的方式显示在终端上 2 本程序包含三个模块 1 主程序模块 void main 初始化 do 接受命令 处理命令 while 命令 退出 2 建树模块 实现定义的抽象数据类型 3 编 译码模块 实现字符串的编 译码 各模块之间的调用关系如下 主程序模块 建树模块 编 译码模块 三 详细设计 程序代码如下 程序名 HuffmanTree h 程序功能 哈夫曼树类的头文件 并用其来实现编 译码 作者 刘伟高 日期 2006 11 27 版本 1 0 对应类实现文件 HuffmanTree cpp 对应主程序文件 main cpp include include include using namespace std struct HuffmanNode 定义哈夫曼树各结点 int weight 存放结点的权值 假设只考虑处理权值为整数 的情况 int parent 记录结点父亲位置 1 表示为根结点 否则表 示为非根结点 int lchild rchild 分别存放该结点的左 右孩子的所在单元的编 号 class HuffmanTree 建立哈夫曼树类 private HuffmanNode Node 哈夫曼树中结点的存储结构 char Info 用来保存各字符信息 int LeafNum 树中的叶子结点总数 public HuffmanTree 构造函数 HuffmanTree 析构函数 void Initialization int WeightNum 初始化函数 根据 Wei ghtNum 个权值建立一棵哈夫曼树 void Encoder 编码函数 利用构造好的哈夫曼树对字 符进行编码 void Decoder 译码函数 对二进制串进行译码 void Print 印文件函数 把已保存好的编码文件显示 在屏幕 void TreePrinting 印哈夫曼树函数 将已在内存中的哈夫 曼树以直观的方式显示在终端上 程序名 HuffmanTree cpp 程序功能 实现哈夫曼树类的源文件 并用其来实现编 译码 作者 刘伟高 日期 2006 11 27 版本 1 0 include HuffmanTree h include using namespace std 构造函数 函数功能 将结点指针初始化为 NULL 函数参数 无 参数返回值 无 HuffmanTree HuffmanTree Node NULL 将树结点初始化为空 Info NULL 将字符数组初始化为空 LeafNum 0 将叶子数初始化为 0 析构函数 函数功能 将所有结点的空间释放 函数参数 无 参数返回值 无 HuffmanTree HuffmanTree delete Node 释放结点空间 delete Info 释放字符存储空间 初始化函数 函数功能 从终端读入字符集大小 n 以及 n 个字符和 n 个权值 建立哈夫曼树 并将它存放在文件 hfmTree 中 函数参数 int WeightNum 表示代码个数 参数返回值 无 void HuffmanTree Initialization int WeightNum 初始 化 int i j pos1 pos2 max1 max2 Node new HuffmanNode 2 WeightNum 1 WeightNum 权值对应的哈夫曼树中的结点总数为 2 WeightNum 1 个 Info new char 2 WeightNum 1 for i 0 i WeightNum i cout 请输入第 i 1 个字符值 getchar 丢弃字符 t 与 n Info i getchar 输入一个字符 主要是考虑输入空格而采用 这种形式的 getchar cout Node i weight 输入权值 Node i parent 1 为根结点 Node i lchild 1 无左孩子 Node i rchild 1 无右孩子 for i WeightNum i 2 WeightNum 1 i 表示需做 Weigh tNum 1 次合并 pos1 1 pos2 1 分别用来存放当前最小值和次小值的所在单元 编号 max1 32767 32767 为整型数的最大值 max2 32767 分别用来存放当前找到的最小值和次小值 for j 0 j i j 在跟节点中选出权值最小的两个 if Node j parent 1 是否为根结点 if Node j weight max1 是否比最小值要小 max2 max1 原最小值变为次小值 max1 Node j weight 存放最小值 pos2 pos1 修改次小值所在单元编号 pos1 j 修改最小值所在单元编号 else if Node j weight max2 比原最小值大但比原次小值要 小 max2 Node j weight 存放次小值 pos2 j 修改次小值所在的单元编号 for Node pos1 parent i 修改父亲位置 Node pos2 parent i Node i lchild pos1 修改儿子位置 Node i rchild pos2 Node i parent 1 表示新结点应该是根结点 Node i weight Node pos1 weight Node pos2 weight for LeafNum WeightNum char ch cout ch if ch y ch Y ofstream fop 以二进制方式打开 hfmTree dat 文件 并当重 新运行时覆盖原文件 fop open hfmTree dat ios out ios binary ios trunc if fop fail 文件打开失败 cout 文件打开失败 n fop write char 写入 WeightNum for i 0 i WeightNum i 把各字符信息写入文件 fop write char flush cout for i 0 i 2 WeightNum 1 i 把个节点内容写入文件 fop write char flush cout fop close 关闭文件 cout 哈夫曼树已构造完成 n Initialization 编码函数 函数功能 利用已建立好的哈夫曼树 如不在内存 则从文件 hf mTree 中读入 对文件 ToBeTran 中的正文进行编码 然后将结果代码存 传输 到文件 CodeFile 中 函数参数 无 参数返回值 无 void HuffmanTree Encoder if Node NULL 哈夫曼树不在内存 从文件 hfmTree 中 读入 ifstream fip 以二进制方式打开 hfmTree dat 文件 fip open hfmTree dat ios binary ios in if fip fail 文件打开失败 cout 文件打开失败 n return 结束本函数 fip read char 读取叶子数 Info new char LeafNum Node new HuffmanNode 2 LeafNum 1 for int i 0 i LeafNum i 读取字符信息 fip read char for i 0 i 2 LeafNum 1 i 读取结点信息 fip read char char Tree 用于存储需编码内容 int i 0 num char Choose 让用户选择读取文件或重新输入需编码内容 cout Choose if Choose 1 读取文件 ToBeTran txt ifstream fip1 ToBeTran txt if fip1 fail 文件不存在 cout 文件打开失败 n return 结束本函数 char ch int k 0 while fip1 get ch k 计算 CodeFile 中代码长度 fip1 close Tree new char k 1 ifstream fip2 ToBeTran txt k 0 while fip2 get ch Tree k ch 读取文件内容 并存到 Tree 中 k fip2 close Tree k 0 结束标志 cout 需编码内容为 cout Tree endl if Choose 1 else Choose 1 重新输入 string tree 用于输入需编码内容 由于 string 类对象可 以输入任意长度 所以先利用这个对象输入 再转存在 Tree 中 cin ignore cout 请输入需要编码的内容 可输入任意长 结束时请按 2 下回 车 n getline cin tree n 输入任意长字符串 getline 以回车 n 作为结束符 第一次按回车表示字符串 结束 第二次按回车才开始输出 while tree i 0 i num i 计算 tree 长度 i 0 Tree new char num 1 while tree i 0 将 tree 中的字符转存到 Tree 中 Tree i tree i i Tree i 0 结束标志符 ofstream fop CodeFile dat ios trunc 存储编码后的 代码 并覆盖原文件 i 0 int k 0 char code code new char LeafNum 为所产生编码分配容量为 Le afNum 的存储空间 因为不等长编码中最长的编码一定不会超 过要求编码的字符个数 while Tree k 0 对每一个字符编码 int j start 0 for i 0 i LeafNum i if Info i Tree k 求出该文字所在单元的编号 break j i while Node j parent 1 结点 j 非树根 j Node j parent 非结点 j 的双亲结点 if Node j lchild i 是左子树 则生成代码 0 code start 0 else 是右子树 则生成代码 1 code start 1 i j code start 0 置串结束符 for i 0 i start 2 i 对二进制序列进行逆置 j code i code i code start i 1 code start i 1 j i 0 while code i 0 存储代码 fop code i i k fop close cout 已编码 且存到文件 CodeFile dat 中 n n Encode 译码函数 函数功能 利用已建好的哈夫曼树 对传输到达的 CodeFile 中的 数据代码进行译码 将译码结果存入文件 TextFile 中 函数参数 无 参数返回值 无 void HuffmanTree Decoder int i 0 k 0 int j LeafNum 2 1 1 表示从根结点开始往下搜索 char BitStr ifstream fip1 CodeFile dat 利用已建好的哈夫曼树 将文件 CodeFile 中的代码进行译码 if fip1 fail 文件打开失败 还未编码 cout 请先编码 n return cout 经译码 原内容为 char ch while fip1 get ch k 计算 CodeFile 中代码长度 fip1 close BitStr new char k 1 ifstream fip2 CodeFile dat k 0 while fip2 get ch BitStr k ch 读取文件内容 k fip2 close BitStr k 0 结束标志符 if Node NULL 还未建哈夫曼树 cout 请先编码 n return ofstream fop TextFile dat 将字符形式的编码文件写 入文件 CodePrin 中 while BitStr i 0 if BitStr i 0 j Node j lchild 往左走 else j Node j rchild 往右走 if Node j rchild 1 到达叶子结点 cout Info j 输出叶子结点对应的字符 j LeafNum 2 1 1 表示重新从根结点开始往下搜索 fop Info j 存入文件 if i while fop close cout n 译码成功且已存到文件 TextFile dat 中 n n Decoder 印文件代码函数 函数功能 将文件 CodeFile 以紧凑格式显示在终端上 每行 50 个代码 同时将此字符形式的编码文件写入文件 CodePrin 中 函数参数 无 参数返回值 无 void HuffmanTree Print char ch int i 1 ifstream fip CodeFile dat 读取文件 ofstream fop CodePrin dat 存储文件 if fip fail cout 没有文件 请先编码 n return while fip get ch cout ch 读取文件内容 fop ch 存到文件中 if i 50 每行输出 50 个字符 cout endl i 0 i cout endl fip close 关闭 CodeFile dat 文件 fop close 关闭 CodePrin dat 文件 印哈夫曼树函数 函数功能 将已在内存中的哈夫曼树以直观的方式 树或凹入表的 形式 显示在终端上 同时将此字符形式的哈夫曼树写入文件 TreePrint 中 函数参数 无 参数返回值 无 void HuffmanTree TreePrinting if Node NULL 未建立哈夫曼树 cout 请先建立哈夫曼树 n return ofstream fop TreePrint dat cout 结点位置 权值 编码 左孩子 编码 右孩子 表示叶子 n fop 结点位置 权值 编码 左孩子 编码 LeafNum 1 i 输出哈夫曼树 cout i Node i weight 1 Node i lchild Node Node i lchild weight 0 Node i rchild Node Node i rchild weight endl fop i Node i weight 1 Node i lchild Node Node i lchild weight 0 Node i rchild Node Node i rchild weight 0 i cout i Node i weight Info i n fop i Node i weight Info i n 程序名 main cpp 程序功能 主函数源文件 作者 刘伟高 日期 2006 11 27 版本 1 0 include HuffmanTree h include include 主函数 参数返回值 无 int main cout 欢迎使用哈夫曼码的编 译码系统 n cout 刘伟高 n cout 版权所有 盗版必究 n cout 在此系统中可以进行以下操作 n cout 1 初始化 I n cout 2 编码 E n cout 3 译码 D n cout 4 印代码文件 P n cout 5 印哈夫曼树 T n cout 6 退出 Q n n HuffmanTree huftree 定义哈夫曼树对象 int weight char Choose while 1 cout Choose switch Choose case I case i cout weight huftree Initialization weight 初始化哈夫曼树 break case E case e huftree Encoder break case D case d huftree Decoder break case P case p huftree Print break case T case t huftree TreePrinting break case Q case q cout n 感谢使用本系统 n n system pause 暂停运行 return 0 cout 1 初始化 I 2 编码 E