《huffman编码译码实现文件的压缩与解压》由会员分享，可在线阅读，更多相关《huffman编码译码实现文件的压缩与解压（17页珍藏版）》请在金锄头文库上搜索。
1、. 数据结构 课程设计题目名称：huffman编码与解码实现文件的压缩与解压专业年级： 组 长： 小组成员： 指导教师： 二一二 年 十二 月 二十六 日 . . . 目录1、 目标任务与问题分析2 1.1目标任务2 1.2问题分析22、 算法分析2 2.1构造huffman树2 2.1.1 字符的统计 2 2.1.2 huffman树节点的设计2 2.2构造huffman编码 3 2.2.1 huffman编码的设计 3 2.3 压缩文件与解压文件的实现3 三、执行效果 4 3.1界面 4 3.2每个字符的编码 43.3操作部分 53.4文件效果 64、 源程序 7 5、 参考文献16huf
2、fman编码与解码实现文件的压缩与解压一、目标任务与问题分析 1.1目标任务 采用huffman编码思想实现文件的压缩和解压功能，可以将任意文件压缩，压缩后也可以解压出来。这样即节约了存储空间，也不会破坏文件的完整性。 1.2问题分析 本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件（不管包含的是字母还是汉字）采取一个个的字节处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。解压过程则利用相应
3、的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。二、算法分析 2.1构造huffman树 要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。由于一个字符的范围在0-255之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。2.1.1 字符的统计用结构体huffchar来存放文件字符的信息。其中有文件中不同字符出现的种类Count、字符data。stru
4、ct huffchar/存放读入字符的类； int Count;/字符出现的个数； char data;/字符；;函数实现： bool char_judge(char c)/判断字符出现的函数； void char_add(char c)/添加新出现的字符； void read_file_count() /文件的读取2.1.2 huffman树节点的设计用结构体huff_tree来存储结点信息，其中有成员频率weight、父亲节点parent、左儿子节点lchild、右儿子节点rchild。struct huff_tree/huffman树结点定义； int parent; int lchil
5、d; int rchild; int weight;函数实现： void creathuffman() /构造huffman树的函数 2.2构造huffman编码 2.2.1 huffman编码的设计 用结构体huffcode来存储每个字符的编码。其中有编码数组bits、起始编码start、频数count、编码对应的字符 c。struct huffcode/结构体 string bits100;/存放解码； int start;/ int count;/频数 string c;/存放字符；;函数实现： void huffmancode()/编码函数 2.3 压缩文件与解压文件的实现 将压缩的文
6、件根据huffman树进行编码，存入新的文件（huffman1.txt）中，将huffman.txt按照huffman编码对应的字符解压回来，但是这样的文件是压缩不了的，当时用了一个30kb的文件压缩后竟然成了119kb，导致这样的问题是因为一个字符对应几个二进制数字，然而一个二进制文字也是占一个字节，这就导致了压缩后的文件变大。处理的方法将huffman1.txt文件中的二进制编码7位7位的存成一个ascII值存入新的文件，这样就实现了真正打压缩。解压的时候将文件中的ascII值重新弄成二进制，不够7位的前边补0，例如ascII值为99的二进制位100011这是6位的ascII码所以再前边补
7、一个0那么99的二进制就变成0100011。接下来就利用huffman编码将这个文件重新译码过来。函数实现： void code_huffman_file()/编码后的二进制码存入文件 void code_file_out()/将编码过的文件恢复； void evaluating()/比较文件压缩的比例 void change()/将二进制编码变成ascII码 void yichu()/将ascII翻译成二进制码恢复文件三、执行效果 本算法有一个初始文件为huffman.txt。为一篇小说，大小为32KB 3.1界面 3.2每个字符的编码3.3操作部分3.4文件效果huffman为初始文件大小
8、为30KB，huffman1为二进制编码文件大小为130KB，huffman2文件为解压后的文件大小为30KB，huffman3.为真正压缩后的文件大小为19KB，huffman为huffman3文件解压后的文件大小为30KB，与huffman文件内容相同。标记的文件就是压缩后的huffman3文件。四、源程序：#include #include #include #include #include #include #include using namespace std;string remfile3100000;/存放原文件字符的数组；char strstr1500000;int rem
9、count=0;/记录元素个数；float bitecount=0;/记录二进制码的个数；/*/struct huffchar/存放读入字符的类； int Count;/字符出现的个数； char data;/字符；;int Count=1;/记录huff数组中字符实际出现的个数；huffchar huff1000;/类的对象；/*/*文件读入部分和统计字符出现的频率*/bool char_judge(char c)/判断字符出现的函数； for(int i=1;i=Count;i+) if(huffi.data=c)huffi.Count+;return true;/如果出现过，出现的频数加
10、1； return false;void char_add(char c)/添加新出现的字符； huffCount.data=c; huffCount+.Count+;/个数增加，/文件的读取void read_file_count() char c; ifstream infile; infile.open(huffman.txt);/打开huffman.txt文件； if(!infile)/检查文件是否打开。 cerr不能打开 huffman.txt文件;/输出文件未打开的标志。 exit(0); cout读入的文件中的内容为：endl; while(c=infile.get()!=EOF
11、) remfile+remcount=c; if(!char_judge(c) char_add(c); coutendl;/*文件读入和统计字符出现频率部分结束*/*/*构造huffman树程序部分*/struct huff_tree/huffman树结点定义； int parent; int lchild; int rchild; int weight; int sum;/huffman树中结点的个数； huff_tree huffman1000;void creathuffman()/构造huffman树的函数 int min1,min2;/指示权值最小； int loc1,loc2;/指向权值最小的两个数的位置； for(int i=1;i=sum;i+) /对huffman树的结点进行初始化； huffmani.parent=0; huffmani.lchild=0; huffmani.rchild=0; huffmani.weight=0; for(int ii=1;iiCount;ii+)/将权值赋给huffman.weight; huffmanii.weight=huffii.Count; sum=2*Count-3;for(int j=
