数据结构课程设计题目名称：huffman编码与解码实现文件的压缩与解压专业年级：组长：小组成员：指导教师：二〇一二年十二月二十六日目录一、目标任务与问题分析 (2)1.1目标任务 (2)1.2问题分析 (2)二、算法分析 (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每个字符的编码 (4)3.3操作部分 (5)3.4文件效果 (6)四、源程序 (7)五、参考文献 (16)huffman编码与解码实现文件的压缩与解压一、目标任务与问题分析1.1目标任务采用huffman编码思想实现文件的压缩和解压功能，可以将任意文件压缩，压缩后也可以解压出来。

这样即节约了存储空间，也不会破坏文件的完整性。

1.2问题分析本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件（不管包含的是字母还是汉字）采取一个个的字节处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。

解压过程则利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。

二、算法分析2.1构造huffman树要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。

为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。

由于一个字符的范围在[0-255]之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。

2.1.1 字符的统计用结构体huffchar来存放文件字符的信息。

其中有文件中不同字符出现的种类Count、字符data。

struct 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 lchild;int rchild;int weight;};函数实现：void creathuffman() //构造huffman树的函数2.2构造huffman编码2.2.1 huffman编码的设计用结构体huffcode来存储每个字符的编码。

其中有编码数组bits、起始编码start、频数count、编码对应的字符c。

struct huffcode{//结构体string bits[100];//存放解码；int start;//int count;//频数string c;//存放字符；};函数实现：void huffmancode()//编码函数2.3 压缩文件与解压文件的实现将压缩的文件根据huffman树进行编码，存入新的文件（huffman1.txt）中，将huffman.txt 按照huffman编码对应的字符解压回来，但是这样的文件是压缩不了的，当时用了一个30kb 的文件压缩后竟然成了119kb，导致这样的问题是因为一个字符对应几个二进制数字，然而一个二进制文字也是占一个字节，这就导致了压缩后的文件变大。

处理的方法将huffman1.txt文件中的二进制编码7位7位的存成一个ascII值存入新的文件，这样就实现了真正打压缩。

解压的时候将文件中的ascII值重新弄成二进制，不够7位的前边补0，例如ascII值为99的二进制位100011这是6位的ascII码所以再前边补一个0那么99的二进制就变成0100011。

接下来就利用huffman编码将这个文件重新译码过来。

函数实现：void code_huffman_file()//编码后的二进制码存入文件void code_file_out()//将编码过的文件恢复；void evaluating()//比较文件压缩的比例void change()//将二进制编码变成ascII码void yichu()//将ascII翻译成二进制码恢复文件三、执行效果本算法有一个初始文件为huffman.txt。

为一篇小说，大小为32KB3.1界面3.2每个字符的编码3.3操作部分3.4文件效果huffman为初始文件大小为30KB，huffman1为二进制编码文件大小为130KB，huffman2文件为解压后的文件大小为30KB，huffman3.为真正压缩后的文件大小为19KB，huffman 为huffman3文件解压后的文件大小为30KB，与huffman文件内容相同。

标记的文件就是压缩后的huffman3文件。

四、源程序：#include <iostream>#include <fstream>#include <string>#include <iomanip>#include <cstdio>#include <algorithm>#include <queue>using namespace std;string remfile[3100000];//存放原文件字符的数组；char strstr[1500000];int remcount=0;//记录元素个数；float bitecount=0;//记录二进制码的个数；/****************************************************************/ struct huffchar{//存放读入字符的类；int Count;//字符出现的个数；char data;//字符；};int Count=1;//记录huff数组中字符实际出现的个数；huffchar huff[1000];//类的对象；/****************************************************************//*文件读入部分和统计字符出现的频率*/bool char_judge(char c)//判断字符出现的函数；{for(int i=1;i<=Count;i++)if(huff[i].data==c){huff[i].Count++;return true;}//如果出现过，出现的频数加1；return false;}void char_add(char c)//添加新出现的字符；{huff[Count].data=c;huff[Count++].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){remfile[++remcount]=c;if(!char_judge(c))char_add(c);}cout<<endl;}/******************文件读入和统计字符出现频率部分结束**************/ /******************************************************************//******************构造huffman树程序部分***************************/ struct huff_tree{//huffman树结点定义；int parent;int lchild;int rchild;int weight;};int sum;//huffman树中结点的个数；huff_tree huffman[1000];void creathuffman()//构造huffman树的函数{int min1,min2;//指示权值最小；int loc1,loc2;//指向权值最小的两个数的位置；for(int i=1;i<=sum;i++){ //对huffman树的结点进行初始化；huffman[i].parent=0;huffman[i].lchild=0;huffman[i].rchild=0;huffman[i].weight=0;}for(int ii=1;ii<Count;ii++)//将权值赋给huffman[].weight;huffman[ii].weight=huff[ii].Count;sum=2*Count-3;for(int j=Count;j<=sum;j++){loc1=loc2=0;//权值最小的min1=min2=2000000;for(int k=1;k<=j-1;k++)//求权值最小的两个地址；if(huffman[k].parent==0)if(huffman[k].weight<=min1){min2=min1;min1=huffman[k].weight;loc2=loc1;loc1=k;}elseif(huffman[k].weight<=min2){min2=huffman[k].weight;loc2=k;}////////////将求出的两个权值最小的结点合并为新的结点，并将新的结点存入数组中huffman[loc1].parent=j;huffman[loc2].parent=j;huffman[j].lchild=loc1;huffman[j].rchild=loc2;huffman[j].weight=huffman[loc1].weight+huffman[loc2].weight;}}/*******************************构造huffman树的程序部分结束********************************//*************************************huffman编码开始**************************************/struct huffcode{//结构体string bits[100];//存放解码；int start;//int count;//频数string c;//存放字符；};huffcode hcode[100];void huffmancode()//编码函数{int rem,p;int count1=0;for(int y=1;y<=Count;y++){//编码部分；rem=y;hcode[y].start=sum;hcode[y].c=huff[y].data;p=huffman[y].parent;while(p!=0){if(huffman[p].lchild==rem)hcode[y].bits[++count1]='0';else hcode[y].bits[++count1]='1';rem=p;p=huffman[p].parent;}hcode[y].count=count1;count1=0;}cout<<"字符以及其编码："<<endl;for(int t=1;t<=Count;t++)//输出所编的码；{cout<<"字符"<<hcode[t].c<<"；编码：";int r=hcode[t].count;while(r)cout<<hcode[t].bits[r--];cout<<endl;}}/****************************************************************************** ******/string str;void code_huffman_file(){ofstream fp;cout<<"请输入文件名"<<endl<<"例如：huffman1.txt"<<endl;cout<<"该文件用来存放编码后的文件即压缩文件"<<endl;cin>>str;fp.open(str.c_str());if(!fp)//检查文件是否打开。