哈夫曼编码译码器.docx

哈夫曼编码译码器
学院班级： 　 　信息工程学院 　软件1５01　 　 　　 　 　
指导教师： 　　　 朱俊武 　 　 　 　　 　 　
小组成员： 刘洋　蒋佳烨 冀若含 　　
本人学号： 　151303107 　 　　 　 　 　
报告书写： 　　 　 冀若含　 　 　 　 　
学生成绩: 　 　 　　 　 　 　　
目录
一、总体介绍·····························0３-0４
二、详细设计·····························０4—11
三、运行测试·····························１1-12
四、课设总结·····························１3-13
五、附录代码·····························13—1９
一、总体介绍

ﻩ我们小组做了两个版本，其中一个为文件操作版,。我主要负责的是构造哈夫曼树,给出各个字符的哈夫曼编码，加密操做,整个键盘操作版系统的代码重组、编辑。开发的过程中使用了Codｅlite、Ｄev、Vｃ等软件。参考书籍为《数据结构》(c语言版)。
其中文件操作版的具体实现为:
能够实现对２6个小写字母外加空格进行哈夫曼编码，并能够对一整篇文章（有小写字母和空格组成）进行加密，生成密码文件。最后根据生成的密码翻译出原文并存档。
在使用程序时，使用者只需要对TｏＢｅtran文件进行原文的输入(使用小写字母或空格），加密和解密功能由程序自主来完成。
程序运行的过程中会输出进行编码的２６个小写字母和空格(字符型）,并输出其对应的权值(整型）。。
键盘操作版为:
要求从键盘输入字符集和字符的权值，大部分字符均可输入，需要各个字符的权值不能相同。
利用输入的权值建立哈夫曼树，得到每个字符的前缀编码。
输入字符串，程序对其进行加密。
输入密文（101０101…………….。)对密文进行解密。
两个版本都利用了哈夫曼树解决问题，通过建立哈夫曼树，得出每个字符的独特前缀编码，也就是密文,。(之前想过字符串的匹配得到明文但是算法太为复杂）。

本系统分为三个大的模块:构造哈夫曼树，编码，译码.
1。3 功能难点
ﻩ本系统的实现难点在于哈夫曼树的构造。编码、译码功能的实现都是基于哈夫曼树的。
二、详细设计
2．1哈夫曼树的构造
哈夫曼树，又称最优树,是一类带权路径长度最短的树，:
： 根据给定的ｎ个权值｛w1，w２,…wn}构成ｎ棵二叉树的集合F＝｛T１，T２，。。，Ｔn}，其中每棵二叉树Ti中只有一个带权wｉ的根节点，左右子树均空。
2． 找最小树：在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和.
３．　删除与加入:在F中删除这两棵树，并将新的二叉树加入F中.
４。 判断：重复前两步（2和３),直到F中只含有一棵树为止。该树即为哈夫曼树。
2．2 代码实现
哈夫曼树和哈夫曼编码的储存表示
ｔypedef sｔrucｔ{
ﻩint　weight；
int parent，lchｉlｄ，ｒcｈｉld;
}HTNoｄe，＊HuffmanTree；／/动态分配数组储存哈夫曼树
ｔypedef　ｃhａr* *HｕfｆmanCode；/／动态分配数组储存哈夫曼编码表
voｉd Select(ＨｕfｆmａnTｒee ＨT，int p,ｉｎt *s1，inｔ　*s2）
该函数的功能为:找出HT[1…．i—１］中parent为０且weighｔ最小的两个结点,其序号为s1，ｓ2。
voiｄ　HuffmanCodinｇ(ＨuffmaｎTree HT,HuffmaｎCoｄe　HC，int *w，inｔ ｎ，chａr　*a）
该函数的功能为构造哈夫曼树HＴ，并求出n个字符的哈夫曼编码ＨC。
以下为两个函数的流程图或详细设计。
vｏｉd HuｆfmanCoding(HｕffｍaｎTreｅ HT，HufｆmanＣode ＨC,ｉnt ＊