哈夫曼编码与译码报告要点.pdf

用哈夫曼树对字符串进行编码译码 一、设计思想 程序要求： 利用哈夫曼树对字符串进行编码 ,要求每个字符有自己唯一的编码。将得到的一串 字串译成 0、 1 编码后存到一个文件夹中，然后再从这个文件夹中读出这串编码进行解 码。 实现方法： 输入一串字符， 要求字符的区间为大写的 26 个英文字母， 将获得的串字符用计算 权值的函数（ jsquanzhi() ）进行字符统计，统计出现的字符种数以及每种字符出现的次 数， 将该种字符出现的次数作为它的权值。将出现的字符的权值和该字符依次分别赋 给两个结构体 HT 和 HC ，利用 HT （节点）权值的大小建立哈夫曼树，首先用选择函 数 select （）函数选择两个权值最小的字符作为叶子节点，创建一个新的节点作为这两 个叶节点的父节点，被选中的节点给他的 HT[i].parent 赋值是他下次不再被选中，父节 点的权值为，子节点的权值之和。然后将该将父节点放入筛选区中，再进行选择（被选 过的不再被使用） ，直到所有的节点都被使用，这样一个哈夫曼树就被建立了。根据每 个字符在哈夫曼书中的位置来编译每个字符的 0、 1 密文代码，从叶节点判断该叶节点 是其父节点的左右字左字为‘ 0 ’，右子为‘ 1’，在判断父节点是上级父节点的左右子直 至根节点， 将生成的 0、1 字符串按所表示的字符倒序存入 HC 相应的字符的 bins[] 数组。 重新一个一个字符的读取输入的字符串，按照字符出现的顺序将它转为 0 、 1 代码并存 到一个 txt 文件夹中去。解码时从文件夹中，一个一个字符的读出那串 0 、 1 代码赋给 一个临时字符串 cd[] ，用该字符串与每个字符的 HC[i].bins 密文比较，直到与一个字符 的密文相同时， 译出该字符， 将字符存放在临时字符数组 tempstr[] 中，清空临时字符串 继续读取 0、 1 代码进行翻译，直至文件密文结束为止。于是就得到了原先被加密的那 串字符串。 - 1 - 用哈夫曼树对字符串进行编码译码 二、算法流程图 开始 获得输入的字符串 getstr[] ，i=0 。 判断 getstr[i] 是否 i++; 为 26 个大写字母 否 是 k=getstr[i]-64;quantemp [k]++( quantemp 为int 型数 组开始值都为 0)i++; i=1,j=0