数据结构 用哈夫曼编码实现文件压缩

利用哈夫曼编码实现压缩和解压缩1.问题描述利用哈夫曼编码，实现压缩和解压缩的数据元素具有如下形式:结点：weight:存储结点的权值parent:是结点双亲在向量中的下标lchild:结点的左儿子向量下标rchild:结点右儿子向量下标bits:位串，存放编码ch:字符start:编码在位串中的起始位置文件操作记录：b:记录字符在数组中的位置count:字符出现频率（权值）lch、rch、parent:定义哈夫曼树指针变量bits[256]:定义存储哈夫曼编码的数组2.功能需求对于给定的一组字符，可以根据其权值进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。

能够分析文件，统计文件中出现的字符，再对文件进行编码，实现文件的压缩和解压缩，能够对于文件的压缩，比例进行统计，能够打印文件。

3.实现要点（1）构造哈弗曼树过程中，首先将初始森林的各根结点的双亲和左、右儿子指针置-1；叶子在向量T的前n个分量中，构成初始森林的n个结点；对森林中的树进行n次合并，并产生n-1个新结点，依次放入向量T的第i个分量中。

（2）编码过程中，从叶子T[i]出发，利用双亲的指针找到双亲T[p]；再根据T[p]的孩子指针可以知道T[i]是T[p]的左儿子还是右儿子，若是左儿子，则生成代码0，否则生成代码1；（3）在文件压缩和解压过程中，主要参考网上资料，每个步骤都基本理解，并注上了详细解析。

4．函数定义功能：输入权重，构造一棵哈弗曼树void huffman(hftree T){if(n<1 || n > m)return;int i,j,p1,p2;float small1,small2;//初始化cout<<"请输入叶子权重(5个)："<<endl;for(i=0; i<n; i++){T[i].parent = -1;T[i].lchild = T[i].rchild = -1;}//输入叶子权值for(i=0; i<n; i++){cin>>T[i].weight;}for(i=n; i<m; i++){p1 = p2 = -1;small1 = small2 = MAX_FLOAT;for(j=0; j<=i-1; j++){if(T[j].parent != -1)continue;if(T[j].weight < small1){small2 = small1;small1 = T[j].weight;p2 = p1;p1 = j;}else if(T[j].weight < small2){small2 = T[j].weight;p2 = j;}}T[p1].parent = T[p2].parent = i;T[i].parent=-1;T[i].lchild=p1;T[i].rchild=p2;T[i].weight=small1 + small2;}cout<<"创建成功！"<<endl;}功能：对哈弗曼树进行编码void encode(codelist codes, hftree T){int i,c,p,start;cout<<"请输入需要编码的字符(5个)："<<endl;for(i=0; i<n; i++){cin>>codes[i].ch;start=n;c=i;p=T[i].parent;while(p!=-1){start--;if(T[p].lchild==c) codes[i].bits[start]='0';else codes[i].bits[start]='1';c=p;p=T[p].parent;}codes[i].start=start;}cout<<"输入成功！："<<endl;cout<<"编码表:"<<endl;for(int x=0; x<n; x++){cout<<codes[x].ch<<": ";for(int q=codes[x].start;q<n;q++) cout<<codes[x].bits[q];cout<<endl;}}函数功能：对哈弗曼树进行解码void decode(codelist codes,hftree T) {int i,c,p,b;int endflag;endflag=-1;i=m-1;while(cin>>b,b!=endflag){if(b==0) i=T[i].lchild;else i=T[i].rchild;if(T[i].lchild==-1){cout<<codes[i].ch;i=m-1;}}if(i!=m-1)cout<<"编码有错！\n";}功能：对文件进行压缩，统计压缩率void compress(){char filename[255],outputfile[255],buf[512];unsigned char c;long i,j,m,n,f;long min1,pt1,flength,length1,length2;double div;FILE *ifp,*ofp;cout<<"\t请您输入需要压缩的文件：";cin>>filename;ifp=fopen(filename,"rb");if(ifp==NULL){cout<<"\n\t文件打开失败!\n\n";return;}cout<<"\t请您输入压缩后的文件名：";cin>>outputfile;ofp=fopen(strcat(outputfile,".encode"),"wb");if(ofp==NULL){cout<<"\n\t压缩文件失败!\n\n";return;}flength=0;while(!feof(ifp)){fread(&c,1,1,ifp);header[c].count++; //字符重复出现频率+1flength++; //字符出现原文件长度+1}flength--;length1=flength; //原文件长度用作求压缩率的分母header[c].count--;for(i=0;i<512;i++){if(header[i].count!=0) header[i].b=(unsigned char)i;else header[i].b=0;header[i].parent=-1;header[i].lch=header[i].rch=-1; //对结点进行初始化}for(i=0;i<256;i++) //根据频率（权值）大小，对结点进行排序，选择较小的结点进树{for(j=i+1;j<256;j++){if(header[i].count<header[j].count){tmp=header[i];header[i]=header[j];header[j]=tmp;}}}for(i=0;i<256;i++) if(header[i].count==0) break;n=i; //外部叶子结点数为n个时，内部结点数为n-1，整个哈夫曼树的需要的结点数为2*n-1.m=2*n-1;for(i=n;i<m;i++) //构建哈夫曼树{min1=999999999; //预设的最大权值，即结点出现的最大次数for(j=0;j<i;j++){if(header[j].parent!=-1) continue;//parent!=-1说明该结点已存在哈夫曼树中，跳出循环重新选择新结点*/if(min1>header[j].count){pt1=j;min1=header[j].count;continue;}}header[i].count=header[pt1].count;header[pt1].parent=i; //依据parent域值（结点层数）确定树中结点之间的关系header[i].lch=pt1; //计算左分支权值大小min1=999999999;for(j=0;j<i;j++){if(header[j].parent!=-1) continue;if(min1>header[j].count){pt1=j;min1=header[j].count;continue;}}header[i].count+=header[pt1].count;header[i].rch=pt1; //计算右分支权值大小header[pt1].parent=i;}for(i=0;i<n;i++) //哈夫曼无重复前缀编码{f=i;header[i].bits[0]=0; //根结点编码0while(header[f].parent!=-1){j=f;f=header[f].parent;if(header[f].lch==j) //置左分支编码0{j=strlen(header[i].bits);memmove(header[i].bits+1,header[i].bits,j+1);//依次存储连接“0”“1”编码header[i].bits[0]='0';}else //置右分支编码1{j=strlen(header[i].bits);memmove(header[i].bits+1,header[i].bits,j+1);header[i].bits[0]='1';}}}fseek(ifp,0,SEEK_SET); //从文件开始位置向前移动0字节，即定位到文件开始位置fwrite(&flength,sizeof(int),1,ofp);fseek(ofp,8,SEEK_SET);buf[0]=0; //定义缓冲区,它的二进制表示00000000f=0;pt1=8;while(!feof(ifp)){c=fgetc(ifp);f++;for(i=0;i<n;i++){if(c==header[i].b) break;}strcat(buf,header[i].bits);j=strlen(buf);c=0;while(j>=8) //对哈夫曼编码位操作进行压缩存储{for(i=0;i<8;i++){if(buf[i]=='1') c=(c<<1)|1;else c=c<<1;}fwrite(&c,1,1,ofp);pt1++; //统计压缩后文件的长度strcpy(buf,buf+8); //一个字节一个字节拼接j=strlen(buf);}if(f==flength) break;}if(j>0) //对哈夫曼编码位操作进行压缩存储{strcat(buf,"00000000");for(i=0;i<8;i++){if(buf[i]=='1') c=(c<<1)|1;else c=c<<1;}fwrite(&c,1,1,ofp);pt1++;}fseek(ofp,4,SEEK_SET);fwrite(&pt1,sizeof(long),1,ofp);fseek(ofp,pt1,SEEK_SET);fwrite(&n,sizeof(long),1,ofp);for(i=0;i<n;i++){fwrite(&(header[i].b),1,1,ofp);c=strlen(header[i].bits);fwrite(&c,1,1,ofp);j=strlen(header[i].bits);if(j%8!=0) //若存储的位数不是8的倍数，则补0 {for(f=j%8;f<8;f++)strcat(header[i].bits,"0");}while(header[i].bits[0]!=0){c=0;for(j=0;j<8;j++) //字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接{if(header[i].bits[j]=='1') c=(c<<1)|1; //|1不改变原位置上的“0”“1”值else c=c<<1;}strcpy(header[i].bits,header[i].bits+8); //把字符的编码按原先存储顺序连接fwrite(&c,1,1,ofp);}}length2=pt1--;div=((double)length1-(double)length2)/(double)length1; //计算文件的压缩率fclose(ifp);fclose(ofp);printf("\n\t压缩文件成功!\n");printf("\t压缩率为 %f%%\n\n",div*100);return;}函数功能：对文件解压缩void uncompress(){char filename[255],outputfile[255],buf[255],bx[255];unsigned char c;long i,j,m,n,f,p,l;long flength;FILE *ifp,*ofp;cout<<"\t请您输入需要解压缩的文件：";cin>>filename;ifp=fopen(strcat(filename,".encode"),"rb");if(ifp==NULL){cout<<"\n\t文件打开失败!\n";return;}cout<<"\t请您输入解压缩后的文件名：";cin>>outputfile;ofp=fopen(outputfile,"wb");if(ofp==NULL){cout<<"\n\t解压缩文件失败!\n";return;}fread(&flength,sizeof(long),1,ifp); //读取原文件长度，对文件进行定位fread(&f,sizeof(long),1,ifp);fseek(ifp,f,SEEK_SET);fread(&n,sizeof(long),1,ifp);for(i=0;i<n;i++){fread(&header[i].b,1,1,ifp);fread(&c,1,1,ifp);p=(long)c; //读取原文件字符的权值header[i].count=p;header[i].bits[0]=0;if(p%8>0) m=p/8+1;else m=p/8;for(j=0;j<m;j++){fread(&c,1,1,ifp);f=c;itoa(f,buf,2); //将f转换为二进制表示的字符串f=strlen(buf);for(l=8;l>f;l--){strcat(header[i].bits,"0");}strcat(header[i].bits,buf);}header[i].bits[p]=0;}for(i=0;i<n;i++) //根据哈夫曼编码的长短，对结点进行排序{for(j=i+1;j<n;j++){if(strlen(header[i].bits)>strlen(header[j].bits)){tmp=header[i];header[i]=header[j];header[j]=tmp;}}}p=strlen(header[n-1].bits);fseek(ifp,8,SEEK_SET);m=0;bx[0]=0;while(1) //通过哈夫曼编码的长短，依次解码，从原来的位存储还原到字节存储{while(strlen(bx)<(unsigned int)p){fread(&c,1,1,ifp);f=c;itoa(f,buf,2);f=strlen(buf);for(l=8;l>f;l--) //在单字节内对相应位置补0{strcat(bx,"0");}strcat(bx,buf);}for(i=0;i<n;i++){if(memcmp(header[i].bits,bx,header[i].count)==0) break;}strcpy(bx,bx+header[i].count);c=header[i].b;fwrite(&c,1,1,ofp);m++; //统计解压缩后文件的长度if(m==flength) break; //flength是原文件长度}fclose(ifp);fclose(ofp);cout<<"\n\t解压缩文件成功!\n";if(m==flength) //对解压缩后文件和原文件相同性比较进行判断（根据文件大小）cout<<"\t解压缩文件与原文件相同!\n\n";else cout<<"\t解压缩文件与原文件不同!\n\n";return;}5、总结和体会本次大作业与C++大作业有所不同，主要是利用构造数据结构解决问题，C++大作业主要体现类和文件读写功能。

数据结构实验报告实验名称：文件压缩实验类型：综合性试验班级：20112111学号：2011211107姓名：冯若航实验日期：2003.6.19 下午4:001.问题描述文件压缩①基本要求哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。

要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。

●统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat中。

●根据哈夫曼树（保存在HufTree.dat中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt文件中。

●压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。

●解压：将CodeFile.dat文件利用哈夫曼树译码解压，恢复为源文件。

2.数据结构设计此类问题，应设计文件的数据结构。

* 4 压缩头标记* 1 文件名长度* ns 文件名* 4 源文件长度* 1020 huffman树* 1021~EOF 文件内容赫夫曼树节点的数据结构typedef struct node{long w; //权short p,l,r; //父亲，左孩子，右孩子}HTNODE,*HTNP; //霍夫曼树的结点赫夫曼编码数组元素的数据结构设计typedef struct huffman_code{BYTE len; //长度BYTE *codestr; //字符串}HFCODE; //霍夫曼编码数组元素3.算法设计源代码#define_CRT_SECURE_NO_DEPRECATE#include<stdio.h>#include<string.h>#include<stdlib.h>typedef unsigned int UINT;typedef unsigned char BYTE;typedef struct node{long w; //权short p,l,r; //父亲，左孩子，右孩子}HTNODE,*HTNP; //霍夫曼树的结点typedef struct huffman_code{BYTE len; //长度BYTE *codestr; //字符串}HFCODE; //霍夫曼编码数组元素#define OK 1#define ERROR -1#define UNUSE -1 //未链接节点标志#define CHAR_BITS 8 //一个字符中的位数#define INT_BITS 32 //一个整型中的位数#define HUFCODE_SIZE 256 //霍夫曼编码个数#define BUFFERSIZE 256 //缓冲区大小大小#define UINTSIZE sizeof(UINT)#define BYTESIZE sizeof(BYTE)#define TAG_ZIGHEAD 0xFFFFFFFF //压缩文件头标#define MAX_FILENAME512//函数声明//压缩模块int Compress(char *SourceFilename,char *DestinationFilename);//压缩调用int Initializing(char *SourceFilename,FILE **inp,char *DestinationFilename,FILE **outp); //初始化文件工作环境long AnalysisFiles(FILE *in,long frequency[]);//计算每个不同字节的频率以及所有的字节数int CreateHuffmanTree(long w[],int n,HTNODE ht[]);//生成霍夫曼树int HuffmanTreeCoding(HTNP htp,int n,HFCODE hc[]);//霍夫曼编码int Search(HTNP ht,int n);//查找当前最小权值的霍夫曼树节点并置为占用BYTE Char2Bit(const BYTE chars[CHAR_BITS]);//将一个字符数组转换成二进制数字int Search(HTNP ht,int n);//查找当前最小权值的霍夫曼树节点并置为占用int WriteZipFiles(FILE *in,FILE *out,HTNP ht,HFCODE hc[],char* SourceFilename,long source_filesize);//写压缩文件//解压缩模块int DeCompress(char *SourceFilename,char *DestinationFilename);//解压缩调用int Initializing_Dezip(char *SourceFilename,FILE **inp,char*DestinationFilename,FILE **outp); //为处理解压缩流程初始化文件void ReadHuffmanTree(FILE* in,short mini_ht[][2]);//从待解压缩文件中读取huffman树int WriteDeZipFiles(FILE *in,FILE* out,short mini_ht[][2],long bits_pos,longDst_Filesize); //写解压缩文件void ErrorReport(int error_code);//报错//函数定义//函数实现//压缩int Compress(char *SourceFilename,char *DestinationFilename){FILE *in,*out; //输入输出流int i; //计数变量float Compress_rate; //存放压缩率HFCODE hc[HUFCODE_SIZE]; //存放256个字符的huffman编码HTNODE ht[HUFCODE_SIZE*2-1]; //256个字符的huffman树需要2*256-1=511个节点。

数据结构哈夫曼编码加密文件数据结构哈夫曼编码加密文件引言数据结构是计算机科学中非常重要的一门课程，它研究了用于组织和存储数据的各种算法和数据结构。

在计算机科学中，编码是将信息从一种形式转化为另一种形式的过程。

在信息安全领域中，加密（encryption）是保护信息不被未经授权的人员访问的过程。

本文将介绍数据结构中一种常用的编码技术——哈夫曼编码，并且将其应用于文件加密中。

1. 哈夫曼编码哈夫曼编码是一种用于数据压缩的编码技术，由David A. Huffman在1952年提出。

这种编码技术基于树形结构，通过对出现频率较高的字符使用较短的编码，对出现频率较低的字符使用较长的编码，以实现对数据的高效压缩。

哈夫曼编码的构建过程主要分为两个步骤：构建哈夫曼树和哈夫曼编码。

1.1 构建哈夫曼树构建哈夫曼树的过程是通过不断合并权值最小的两个节点，直到只剩下一个根节点。

每个节点都有一个权值，该权值是根据字符在文件中的出现频率来确定的。

在构建哈夫曼树的过程中，节点的权值扮演着重要的作用。

1.2 哈夫曼编码哈夫曼编码的过程是根据哈夫曼树的结构，为每个字符对应的编码。

向左的路径被标记为0，向右的路径被标记为1。

对于每个字符，从根节点开始，通过路径上的0和1，就可以找到对应的编码。

2. 数据结构哈夫曼编码加密文件在文件加密中，可以利用哈夫曼编码对文件中的字符进行加密。

具体的步骤如下：2.1 统计字符出现频率首先，需要统计文件中各个字符的出现频率。

可以使用字典等数据结构来记录每个字符的出现次数。

2.2 构建哈夫曼树根据统计得到的字符出现频率，构建哈夫曼树。

构建哈夫曼树的过程可以使用优先队列等数据结构来辅助。

2.3 哈夫曼编码根据构建的哈夫曼树，为每个字符对应的哈夫曼编码。

可以使用递归或者栈等数据结构来遍历哈夫曼树，编码。

2.4 加密文件利用的哈夫曼编码，对文件中的字符进行加密。

将文件中的每个字符替换为对应的哈夫曼编码。

《数据结构》课程设计数学与应用数学一班胡耕岩 2012214147一、问题分析和任务定义1.1设计任务采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。

要求（1）运行时的压缩原文件的规模应不小于5K。

（2）提供恢复文件与原文件的相同性对比功能。

1.2问题分析本课题是利用哈夫曼编码思想，设计对一个文本文件（.txt）中的字符进行哈夫曼编码，生成编码压缩文件，并且还可将一个压缩后的文件进行解码还原为原始文本文件（.txt）。

在了解哈夫曼压缩解压缩原理之前，首先让我们来认识哈夫曼树。

哈夫曼树又称最优二叉树，是带权路径长度最小的二叉树。

在文本文件中多采用二进制编码。

为了使文件尽可能的缩短，可以对文件中每个字符出现的次数进行统计。

设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。

若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。

为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。

哈夫曼树中的左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。

统计字符中每个字符在文件中出现的平均概率（概率越大，要求编码越短）。

利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。

则概率越大的节点，路径越短。

哈夫曼译码是从二进制序列的头部开始，顺序匹配成共的部分替换成相应的字符，直至二进制转换为字符序列。

哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行压缩。

总之，该课题的任务应该是首先要打开要压缩的文本文件并读出其字符出现的频率，以其为权值构建哈夫曼树。

其次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，以外还有存储相应的哈夫曼编码，为解压缩做准备。

数据结构课程设计题目名称：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个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。

数据结构与程序设计实验实验报告哈尔滨工程大学实验报告四一、问题描述哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。

要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。

统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat 中。

根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt 文件中。

压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。

解压：将CodeFile.dat 文件利用哈夫曼树译码解压，恢复为源文件。

二、数据结构设计由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。

1.使用结构体数组统计词频，并存储:typedef struct Node{int weight; //叶子结点的权值char c; //叶子结点int num; //叶子结点的二进制码的长度}LeafNode[N];2.使用结构体数组存储哈夫曼树:typedef struct{unsigned int weight;//权值unsigned int parent, LChild, RChild;}HTNode,Huffman[M+1]; //huffman树3.使用字符指针数组存储哈夫曼编码表：typedef char *HuffmanCode[2*M]; //haffman编码表三、算法设计1.读取文件，获得字符串void read_file(char const *file_name, char *ch){FILE *in_file = Fopen(file_name, "r");unsigned int flag = fread(ch, sizeof(char), N, in_file);if(flag == 0){printf("%s读取失败\n", file_name);fflush(stdout);}printf("读入的字符串是: %s\n\n", ch);Fclose(in_file);int len = strlen(ch);。

《用哈夫曼编码实现文件压缩》实验报告课程名称数据结构（B）实验学期2009 至2010 学年第 1 学期学生所在系部计算机系年级2007 专业班级计算机B071学生姓名陆永芳学号200707014105任课教师盛建瓴实验成绩用哈夫曼编码实现文件压缩1、了解文件的概念。

2、掌握线性链表的插入、删除等算法。

3、掌握Huffman树的概念及构造方法。

4、掌握二叉树的存储结构及遍历算法。

5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。

微型计算机、Windows 系列操作系统、Visual C++6.0软件根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。

本次实验采用将字符用长度尽可能短的二进制数位表示方法，即对于文件中出现的字符，无须全部都用8位的ASCII码进行存储，根据他们在文件中出现色频率不同，我们利用Haffman算法使每个字符都能以最短的二进制字符进行存储，以达到节省存储空间，压缩文件的目的。

解决了压缩需采用的算法，程序的思路就清晰了：1.统计需压缩文件中每个字符出现的频率2.将每个字符的出现频率作为叶子结点构建Haffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径得到0、1的序列，这样便能完成了Haffman的编码，将每个字符用最短的二进制字符表示。

3.打开需压缩文件，再将需压缩文件中的每个ascii码对应的Haffman编码按bit单位输出。

4.文件压缩结束。

（1）构造Huffman树的方法——Haffman算法构造Huffman树步骤：I．根据给定的n个权值{w1,w2，……，wn}，构造n棵只有根结点的二叉树，令起权值为wj。

II．在森林中选取两棵根结点权值最小的树作为左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。

今天下午想把文件压缩写一下，因为我觉得这个还是比较锻炼技术的，对数据结构的要求应该比较高，权当练习了吧。

我采用的压缩方式是Huffman编码，不过比较囧的是，我拼写拼错了，我拼的是h affman，在后面的代码也是出尽洋相。

huffman是非常经典的一种编码形式，不过现在好像用的不多了，但是这种压缩编码的好处在于数据是无损压缩的，而且非常经典。

在构造huffman树，要做的步骤如下：1 对文件的元素进行统计，其实就是个计数，我这里的元素是以字节为单位的，毕竟任何文件都可以转化为字节流的形式，处理起来方便的很。

2 然后对统计结果进行一次由小到大的排序，排序的key值就是元素出现的次数。

3 接着取出来排好序的数组的前两个元素，求和，并且再其左右子树上创建这两个元素的副本，然后再扔回首部，此时扔回数组中的，就是包含子树的节点了。

在这里有个代码优化的小技巧，能在一定程度上提高效率，减少不必要的操作。

4 此时原来已经排好序的数组可能会遭到破坏，必须重新进行排序，因为数组大体是有序的，所以使用此时效率最高的一步插入排序，时间复杂度仅为O(n)，我专门写了个函数来实现这个功能，并且进行了简单的测试。

5 然后再取出首部的前两个元素，重复上面步骤3，直到数组中的元素个数为1.最终数组中仅存的元素，就是一棵二叉树的Root。

这样huffman树的构造就完成了。

在huffman树构造完成后，接着要做的就是根据huffman树获取其huffman编码，这个还是很简单的，就是使用递归，左树传入0，右树传入1，依次递归下去，遇到叶子节点就直接输出，当然了，如果需要添加到某个数据结构中，只要在递归函数中给个参数接口，或者设置一个全局的容器，都能解决，换言之，类似于输出重定向。

这样上面的步骤完成后，就能很好的获取到huffman编码了。

不过根据huffman 编码结果将字符型的0,1写入到二进制中的0，1还有一些比较关键的函数需要处理，还没想到比较好的点子，不过最基础的蛮力方法肯定是能写的，但是，效率就不好说了。

《数据结构》实验报告利用Huffman编码对文件进行压缩解压学生:XXX学号:XXXXXXXX联系:XXXXXX@(一)基本信息1.实验题目利用Huffman编码对文件进行压缩解压2.完成人（姓名、学号）姓名：XXX 学号：XXXXXXXX3.报告日期2007年12月12日星期二(二)实习内容简要描述1.实习目标学会对树的基本操作学会对文件进行操作利用Huffman编码对文件压缩解压2.实习要求实现最小堆模板类利用最小堆构建Huffman树实现Huffman编码和解码根据用户从键盘输入的报文文本,输出各字符的Huffman编码以及报文的编码根据用户从键盘输入一串报文文本，输出各字符的Huffman编码输出报文的Huffman编码及长度根据输入的Huffman编码，解码输出利用Huffman编码和解码对二进制文件的压缩和解压(三)报告主要内容1.设计思路开发环境：Microsoft Visual C++ 2005设计思路：1.设计Pack类储存字符的权值2.设计MinHeap模板类构建最小堆3.设计ExtBinTree模板类为带权二叉树4.设计Compress模板类以实现文件的压缩解压2.主要数据结构1.MinHeap.h: 头文件,包含MinHeap模板类的类界面以及定义;2.HuffmanTree.h:头文件,包含ExtBinTree模板类以及Compress模板类的类的的类界面以及定义3.main.cpp:调用上述头文件实现相关操作3.主要代码结构主要代码结构为见附件中各文件的代码注释4.主要代码段分析主要代码段分析，见附件中的代码注释(四)实习结果1.基本数据源程序代码行数：约800行完成该实习投入的时间：二十四小时(不包括写实验报告的时间)与其他同学讨论交流情况:感谢刘畅同学对程序的测试2.测试数据设计1.对屏幕输入字符进行Huffman编码2.根据Huffman树非唯一性,虽然和课件上有些许不同,但是还是正确的3.输入字符串:CASTCASTSATATATASA4.输出编码:A:0 C:110 S:111 T:105.输入霍夫曼编码:01110101101106.输出译码:ASATCC7.8.对”实验05.PPT”的压缩操作9.使用0秒(不足一秒按0秒计算),压缩率为56.1755%10.对”实验05.ppt.hfm”(即刚才生成的压缩文件)的解压操作11.使用0秒(不足一秒按0秒计算),解压后文件无异常12.对一个18M的EXE安装包前后进行压缩和解压操作,分别用时10秒和9秒3.测试结果分析A)程序运行的系统资源配置操作系统：Microsoft Windows XP Professional SP2CPU: AMD Athlon 3600+ 2.0GRAM: 1024M DDRII开发环境：Microsoft Visual C++ 2005B)对TXT文档进行压缩和解压后,通过WinMerge检验和原文件无差异C)对MP3和EXE文件压缩和解压后仍能正常使用D)对于中文名字和带有空格的路径均能正确无误识别E)文件名只能小于16个字符(包括后缀名),否则解压会出错(只预留了16个字节用于储存文件名)F)相对于不用文件块读写的程序,效率提高了三倍以上G)具有动态进度条,可以显示当前压缩和解压的进度百分比(当然消耗了一些系统资源)H)出错处理不够充分,特别是cin部分,如果误输入可能会造成死循环(五)实习体会1.实习过程中遇到问题及解决过程A)一开始时候的程序运行很慢,,压缩一个4M左右的文件需要七八秒,后来改用文件块缓存字节来读写后,压缩一个4M的文件只需要两秒左右的时间.本来是只想写一个进度条而已的,后来发现如果只读一个字节就判断一次进度条的话会很消耗系统资源,后来干脆麻烦点用文件块来缓存.不过至于一次缓存多少字节才能达到最好的效果还未知,现在设置的是一次缓存40KB 的数据B)本来一个一个字节读的时候对最后一个字节的操作基本没费什么劲,但是在文件块读写的时候就不是那么清晰明了了,后来经过仔细Debug,才找到错误的所在.许多问题都是这样C)对于中文名和带空格路径,用C++的fstream就不支持,但是C中的FILE*就支持,不知道为什么.还有C++中的fstream的成员函数read返回值很奇怪,不知道如何获取成功读入的项数.改用C中的FILE*文件指针后就解决掉了D)由于这次实验的各个步骤是一环套一环的,在哪里出错很难找得出来,所以这次实验调试消耗的时间特别多.最郁闷的一次错误是发现在取得字符C的第N位函数中,居然把0x40写成了0x30.有时候文件解压出来不对,但是又不清楚是压缩时候错了,还是解压时候错了,然后就要两个函数都要检查一遍.2. 实习体会和收获这次实验最大的特点在于难找错,很锻炼自己的Debug能力(六)自评成绩分数：90 //功能做得较齐全,程序的效率也不错(七)参考文献MSDN还有某网站上树的遍历算法(八)源程序见同一文件夹内.。

数据结构实验报告三——哈夫曼文件压缩实验题目：哈夫曼文件压缩实验目标：输入一个有10k单词的英文文档。

输出压缩后的二进制文件，并计算压缩比。

数据结构：栈和哈夫曼树。

1.定义栈（）typedef struct{char *elem;int stacksize;int top;}STACK;2.定义哈夫曼树（）typedef struct{int weight;int left,right;int parent;}HTNode;需要的操作有：1.初始化栈（Initstack）void Initstack(STACK *s){s->elem=(char *)malloc(sizeof(int)*1000);s->stacksize=1000;s->top=-1;}2.压栈（push）void push(STACK *s,int e){s->elem[++s->top]=e;}3.弹栈（pop）void pop(STACK *s,int *e){if(s->top!=-1)*e=s->elem[s->top--];}4.构造哈夫曼树（Inithuffman）void Inithuffman(int wset[n],int k,HuffTree HT[]){ //构造哈夫曼树int i,m;int s1,s2;m=k*2-1;for(i=0;i<m;i++){ //初始化HT数组HT[i]=(HuffTree)malloc(sizeof(HTNode));HT[i]->weight=(i<k?wset[i]:0);HT[i]->parent=-1;HT[i]->left=HT[i]->right=-1;}for(i=k;i<m;i++){ //主循环，完成n-1次合并select(HT,k,i,&s1,&s2); //在HT[1...i-1]中选择parent为0且weight为最小的两个结点，其下标分别为s1和s2HT[i]->left=s1;HT[i]->right=s2;HT[i]->weight=HT[s1]->weight+HT[s2]->weight;HT[s1]->parent=HT[s2]->parent=i;}}其中用到另一个基本操作：找到哈夫曼树中最小和次小的结点（select）5.找到哈夫曼树中最小和次小的结点（select）void select(HuffTree HT[255],int a,int i,int *p,int *q){int j=0,k=0,*HT1,temp;HT1=(int *)malloc(sizeof(int)*(i-1)); //存放权值for(j=0;j<i;j++){if(HT[j]->parent==-1){HT1[k]=HT[j]->weight; //把没有parent的结点的权值放在HT1中k++;}//printf("%4d%4d%4d%4d%4d\n",HT[j]->parent,HT[j]->left,HT[j]->right,HT[j]->we ight,HT1[k-1]);}j=0;while(j<2) { //找到权值最小和第二小的结点for(k=j;k<(i-(i-a)*2);k++){if(HT1[j]>HT1[k]){temp=HT1[k];HT1[k]=HT1[j];HT1[j]=temp;}}j++;}k=0;for(j=0;j<i;){if(HT[j]->parent==-1)if(HT[j]->weight==HT1[0]&&k<1){ //将最小的权值赋到*p中*p=j;k++;}j++;}for(j=0;j<i;){if(HT[j]->parent==-1)if(j!=*p)if(HT[j]->weight==HT1[1]&&k<2){ //将第二小的权值赋到*q 中*q=j;k++;}j++;//printf("%4d%4d%4d%4d\n",HT[i]->parent,HT[i]->left,HT[i]->right,HT[i]->weigh t);}}6.根据哈夫曼树得到各字符对应的哈夫曼编码（Huffman）void Huffman(HuffTree HT[2*n-1],int k,char str[][20]){int i,j,e,t1=0,t2=0;char c;STACK st;for(i=0;i<k;i++){if(HT[i]->right==-1&&HT[i]->left==-1){ //找一个叶子结点Initstack(&st);HT[i]->right=HT[i]->left==-2;j=i; //记录其下标while(HT[j]->parent!=-1){if(HT[HT[j]->parent]->right==j) //找到一个叶子结点，如果他是其parent结点的右结点，就将此边记为1push(&st,'1');elsepush(&st,'0'); //在左边记为0j=HT[j]->parent; //循环操作直到到达根结点}c=i;printf("\t%c ",c); //打印此字符for(;st.top!=-1;){pop(&st,&e);printf("%c",e); //打印其二进制编码str[t1][t2]=e; //将二进制编码存放在str中t2++;}putchar('\n');str[t1][t2]='\0';t2=0;t1++;}}}算法设计：1.从文件中逐个读取字符，记录其出现次数以及文件总字符数，由此确定其频率高低。

哈夫曼编码使用哈夫曼编码进行数据压缩与解压缩在信息技术发展的背景下，数据的传输和存储需求越来越大，如何高效地进行数据压缩成为了重要的课题之一。

哈夫曼编码是一种基于信息熵的编码技术，通过构建最优二叉树，实现了数据的高效压缩和解压缩。

在本文中，我们将探讨哈夫曼编码的原理和应用。

一、哈夫曼编码的原理哈夫曼编码是一种变长编码，它根据字符出现的频率构建一棵最优二叉树，频率较高的字符被赋予较短的编码，频率较低的字符则被赋予较长的编码。

这种编码方式具有无重复前缀码性质，即任意字符的编码都不是其他字符编码的前缀。

这样一来，在解码时就能够准确还原原始数据。

具体实现过程如下：1. 统计字符频率：对待编码的数据进行字符频率统计，得到每个字符出现的次数。

2. 构建哈夫曼树：根据字符频率构建一棵哈夫曼树。

树的每个节点表示一个字符，并且字符的频率决定节点的权重。

构建过程中，每次选择权重最小的两个节点合并形成新的节点，直到所有节点合并为一棵树。

3. 分配编码：从根节点出发，对哈夫曼树的每个子树进行遍历，左子树路径上追加0，右子树路径上追加1，直到到达叶节点。

这样，每个字符都能够找到对应的编码。

4. 进行数据压缩：根据字符的编码，将原始数据进行编码替换，形成压缩后的数据。

编码后的数据长度会变短，达到了数据压缩的目的。

二、哈夫曼编码的应用哈夫曼编码在数据压缩领域有着广泛的应用。

其中，最常见的应用场景是在无损压缩算法中。

通过哈夫曼编码，能够将原始数据进行高效压缩，并在解压缩时准确还原数据，但并不损失任何信息。

此外，哈夫曼编码还经常用于文件压缩、图像压缩和音频压缩等领域。

在文件压缩中，能够将大文件转换为更小的压缩文件，方便传输和存储。

在图像压缩中，通过对图像数据进行编码，能够减小图像文件的大小，提高传输效率。

在音频压缩中，通过压缩音频数据，减小文件大小，同时保持音频质量，实现高质量的音频传输。

三、哈夫曼编码的优缺点1. 优点：哈夫曼编码是一种高效的数据压缩技术，可以大幅度减小数据的存储和传输空间。

数据结构课程设计报告--Huffman编码与文件压缩课程设计报告题目：题目三哈夫曼编码与文件压缩课程名称：数据结构专业班级：计算机科学与技术1003班学号：姓名：鲁辰指导教师：报告日期：2012.09.26计算机科学与技术学院目录1任务书 (4)2 绪言 (5)2.1 课题背景 (5)2.2 课题研究的目的和意义 (5)2.3 国内外概况 (5)2.4 课题的主要研究工作 (5)3 系统设计方案的研究 (6)3.1 系统的控制特点与性能要求 (6)3.2 系统实现的原理 (6)3.2.1 Huffman算法 (6)3.2.2 Huffman编码 (6)3.2.3 压缩过程 (6)3.2.4 解压过程 (7)3.3 系统实现方案分析 (7)3.3.1 实现Huffman编码及压缩所需的变量 (7)3.3.2文件名处理 (9)3.3.3 实现Huffman编码及压缩过程所需要的函数 (10)3.3.4 实现解压缩过程所需要的函数 (13)3.3.5 输入输出 (13)4 基于Huffman编码的文件压缩程序的设计 (14)4.1 主模块功能介绍 (14)5 系统的实现 (15)5.1 目标程序运行截图 (15)5.2 测试及测试数据分析 (15)5.2.1 测试数据 (15)5.2.2 测试数据分析 (16)6 总结与展望 (18)参考文献 (19)附录英文缩写词 (20)1任务书题目三哈夫曼编码与文件压缩☐设计目的：掌握二叉树、哈夫曼树的概念，性质与存储结构，能够利用哈夫曼算法实现哈夫曼编码，并应用于文件压缩，从而提高学生综合运用知识的技能与实践能力。

☐设计内容：分析与设计哈夫曼树的存储结构，实现哈夫曼算法以及编码与译码基本功能，并对任意文本文件利用哈夫曼编码进行压缩得到压缩文件，然后进行解压缩得到解压文件。

有兴趣的同学可以查阅资料实现Lempel-Ziv sliding window压缩方法，并与之比较。

本科学生设计性实验报告软件工程技能实践Ⅰ项目组长陈启学号＿*******专业软件工程班级＿15软件7 班成员陈启杨林昌邓志远万胜实验项目名称＿指导教师及职称＿＿讲师＿＿开课学期2015 至2016 学年第二学期一、实验设计方案1、实验任务与目的（简单介绍实验内容，说明实验任务和目的）1.1实验内容根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。

对于给定的一组字符，可以根据其权值进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。

能够分析文件，统计文件中出现的字符，再对文件进行编码，实现文件的压缩和解压缩，能够对于文件的压缩，比例进行统计，能够打印文件。

分析与设计哈夫曼树的存储结构，实现哈夫曼算法以及编码与译码基本功能，并对任意文本文件利用哈夫曼编码进行压缩得到压缩文件，然后进行解压缩得到解压文件。

1.2实验任务和目的1.2.1了解文件的概念。

1.2.2掌握线性链表的插入、删除等算法。

1.3.3掌握Huffman树的概念及构造方法。

1.4.4掌握二叉树的存储结构及遍历算法。

1.5.5利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。

2、实验思路（详细描述解决问题的整体思路、涉及的算法思想及数据结构等）2.1整体思路2.2涉及的算法思想及数据结构：2.2.1输入要压缩的文件首先运行的时候，用户主界面上有菜单提示该如何使用软件，根据菜单提示选择所要执行的项，依次进行，因为各个环节之间有先后顺序。

第一步为输入压缩软件的名称，由键盘输入文件路径和文件名称，读入字符数组中，打开该文件，按照提示进行压缩。

若打不开，则继续输入。

2.2.2读文件并计算字符频率文件将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组空间，用读取的字符减去字符结束符作为下标记录字符的频率。

2.2.3根据字符的频率，利用Huffman编码思想创建Huffman树将所记录的字符的频率作为权值来创建Huffman树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结点。

数据结构哈夫曼编码加密文件一、介绍数据结构是计算机科学中的一个重要概念，它描述了如何组织和存储数据以便有效地访问和操作。

哈夫曼编码是一种常用的数据压缩算法，通过根据字符出现的频率来构建一个最优的编码方案，从而实现对数据的高效压缩。

本文将介绍如何使用数据结构中的哈夫曼编码算法来加密文件，以保护文件的安全性。

二、加密文件的步骤1. 文件读取：首先，需要从计算机的存储设备中读取要加密的文件。

可以使用文件输入流来实现文件的读取操作。

2. 字符频率统计：读取文件后，需要统计每个字符在文件中出现的频率。

可以使用哈希表来记录字符及其对应的频率。

3. 构建哈夫曼树：根据字符频率统计结果，构建哈夫曼树。

哈夫曼树是一种特殊的二叉树，其中字符的频率决定了字符在树中的位置。

4. 生成编码表：通过遍历哈夫曼树，可以生成每个字符对应的哈夫曼编码。

哈夫曼编码是由0和1组成的字符串，表示字符在哈夫曼树中的路径。

5. 文件加密：使用生成的哈夫曼编码，将原始文件中的字符替换为对应的哈夫曼编码。

这样可以实现对文件内容的加密。

6. 加密文件保存：将加密后的文件保存到计算机的存储设备中。

可以使用文件输出流来实现文件的保存操作。

三、示例为了更好地理解上述步骤，我们以一个简单的文本文件为例进行演示。

假设原始文件内容如下："This is a sample file for Huffman encoding."1. 文件读取：使用文件输入流读取文件内容。

2. 字符频率统计：统计每个字符在文件中出现的频率。

假设字符频率统计结果如下：{'T': 1, 'h': 2, 'i': 5, 's': 5, ' ': 6, 'a': 3, 'm': 2, 'p': 1, 'l': 1, 'e': 2, 'f': 2, 'o': 1, 'r': 2, 'u': 1, 'n': 2, 'c': 1, 'd': 2, 'g': 1, '.': 1}3. 构建哈夫曼树：根据字符频率统计结果，构建哈夫曼树。

基于哈夫曼（haffuman）算法的⽂件压缩的实现（C语⾔）（转）本⽂⾸先简要阐述哈夫曼算法的基本思想，然后介绍了使⽤哈夫曼算法进⾏⽂件压缩和解压缩的处理步骤，最后给出了C语⾔实现的⽂件压缩和解压缩的源代码。

哈夫曼算法的主要思想是：①⾸先遍历要处理的字符串，得到每个字符的出现的次数；②将每个字符（以其出现次数为权值）分别构造为⼆叉树（注意此时的⼆叉树只有⼀个节点）；③取所有⼆叉树种种字符出现次数最⼩的⼆叉树合并为⼀颗新的⼆叉树，新⼆叉树根节点的权值等于两个⼦节点的权值之和，新节点中的字符忽略；④重复过程③直到所有树被合并为同⼀棵⼆叉树⑤遍历最后得到的⼆叉树，⾃顶向下按路径编号，指向左节点的边编号0，指向右节点的边编号1，从根到叶节点的所有边上的0和1链接起来，就是叶⼦节点中字符的哈夫曼编码。

下图展⽰了哈夫曼编码的基本思想。

基于哈夫曼算法的⽂件压缩和解压缩过程分别说明如下：⼀、⽂件压缩：①统计词频：读取⽂件的每个字节，使⽤整数数组int statistic[MAX_CHARS]统计每个字符出现的次数，由于⼀个字节最多表⽰2^8-1个字符，所以MAX_CHARS=256就⾜够了。

在统计字符数的时候，对于每⼀个byte, 有statistic[(unsigned char)byte] 。

②构造哈夫曼树：根据statistic数组，基于哈夫曼树算法造哈夫曼树，由于构造的过程中每次都要取最⼩权值的字符，所以需要⽤优先队列来维护每棵树的根节点。

③⽣成编码：深度优先遍历哈弗曼树，得到每个叶⼦节点中的字符的编码并存⼊字符串数组char*dictionary[MAX_CHARS];④存储词频：新建存储压缩数据的⽂件，⾸先写⼊不同字符的个数，然后将每个字符及其对应的词频写⼊⽂件。

⑤存储压缩数据：再次读取待压缩⽂件的每个字节byte，由dictionary[(unsigned int)byte]得到对应的编码（注意每个字符编码的长度不⼀），使⽤位运算⼀次将编码中的每个位(BIT)设置到⼀个char类型的位缓冲中，可能多个编码才能填满⼀个位缓冲，每填满⼀次，将位缓冲区以单个字节的形式写⼊⽂件。

《用哈夫曼编码实现文件压缩》实验报告课程名称《数据结构B》实验学期2014至2014 学年第 1 学期学生所在系部计算机系年级2010 专业班级网络B10-3学生姓名学号任课教师实验成绩用哈夫曼编码实现文件压缩1、了解文件的概念。

2、掌握线性链表的插入、删除等算法。

3、掌握Huffman树的概念及构造方法。

4、掌握二叉树的存储结构及遍历算法。

5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。

微型计算机、Windows 系列操作系统、Visual C++6.0软件根据ASCII码文件中各ASCII字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。

在文件存储时，一个整型的字符要占用一个字节的空间，对于某些不常用的字符这样会造成空间的浪费，但如果用位来存储数据，可以将字符重新编码，使那些常用的字符存储空间相对短的，不常用的字符相对长些，可以节约空间。

哈夫曼编码即是这样一个过程。

用哈夫曼编码进行文件压缩，首先应对所用的字符进行哈夫曼变编码，在这之前应先对所用字符进行权值统计。

在编码哈夫曼树的时候，选取两个权值最小的依次构造哈夫曼树，进行哈夫曼编码时，使哈夫曼树的左孩子上的分支编码为0，右孩子上的分支编码为1。

然后对文件进行压缩。

压缩过程用到了文件的读写。

头文件的构造：头文件首先应用宏定义，对文件要用到的数据进行定义，然后定义了结构体类型，将所要到字符的权值，数据，双亲编号与孩子编号放在结构体中，使程序间的关系变得紧密。

定义第二个结构体，其中包含结构体数组和树根的编号。

定义指针，使其指向第二个结构体。

接着类型定义，定义了结构体，其中包含字符原码值，哈夫曼编码值和哈夫曼编码值的长度，并将其取名为HaffCode。

将程序所用到的函数包含在头文件里。

哈夫曼树的构造：在程序开头先对程序所用到的变量进行定义，包括指向结构体的指针，整型变量，权值最小的结点的编号，第二小的结点的编号，权值最小的结点的权值，第二小的结点的权值。

《用哈夫曼编码实现文件压缩》实验项目指导书《数据结构》实验教学改革课题组2006年12月一、实验题目用哈夫曼编码实现文件压缩二、实验目的1、了解文件的概念。

2、掌握线性链表的插入、删除等算法。

3、掌握Huffman树的概念及构造方法。

4、掌握二叉树的存储结构及遍历算法。

5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。

三、实验设备及环境微型计算机、Windows 系列操作系统、Visual C++6.0软件四、实验内容根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。

五、实验要求1、用C语言编程实现上述实验内容中的结构定义和算法。

2、要有main()函数，并且在main()函数中使用检测数据调用上述算法。

3、实验完成后撰写实验报告，实验报告的具体格式参见《实验报告样例》。

4、实验完成后把打印好的实验报告以及电子版的实验报告和源程序一并上交。

六、实验方法或或步骤1、实验的预备知识（1）构造Hufffman树的方法—Hufffman算法构造Huffman树步骤：I.根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令起权值为wj。

II.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。

III.在森林中删除这两棵树，同时将新得到的二叉树加入森林中。

IV.重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。

（2）Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。

（3）二叉树的存储结构typedef struct node{datatype data;struct node *lchild, *rchild;}BinTree;2、实验步骤（1）启动Visual c++6.0，如图 2-1所示。

数据结构中的压缩与解压缩算法在数据结构中，压缩与解压缩算法扮演着重要的角色。

它们可以显著减少数据存储和传输所需的空间和时间。

压缩算法使用各种技术来减少数据的大小，而解压缩算法则将压缩的数据还原到其原始状态。

本文将介绍几种常用的压缩与解压缩算法，并讨论它们的原理和应用。

一、哈夫曼编码哈夫曼编码是一种基于变长编码的压缩算法。

它通过根据输入数据中字符的频率来构建一棵哈夫曼树，并生成一个独特的编码表。

在哈夫曼编码中，频率较高的字符用较短的编码表示，而频率较低的字符用较长的编码表示。

这种编码方式可以大大减少数据的大小，并且可以在解压缩时快速还原原始数据。

二、LZW压缩LZW（Lempel-Ziv-Welch）压缩算法是一种基于字典的压缩算法。

它通过在压缩和解压缩过程中动态构建和更新字典，将输入数据中的字符串替换为对应的索引。

LZW压缩算法能够在保持数据质量的同时实现很高的压缩比。

它被广泛应用于图像、音频和视频等多媒体数据的压缩。

三、Run-Length编码Run-Length编码是一种简单但有效的压缩算法。

它通过将连续重复的字符或数据序列替换为一个标记和一个计数值来实现压缩。

例如，连续出现的字符 "AAAABBBCCD" 可以被编码为 "4A3B2C1D"。

Run-Length编码在处理包含大量连续重复数据的情况下非常有效，但对于非重复数据的压缩效果有限。

四、Burrows-Wheeler变换Burrows-Wheeler变换是一种用于数据压缩的重排和重新排列技术。

它通过对输入数据进行循环右移和排序，生成一个新的字符串。

然后，通过记录原始字符串的最后一个字符在排序后的字符串中的位置，以及排序后的字符串中的每个字符前一个字符的索引，可以实现数据的压缩。

解压缩时，通过逆向操作将压缩后的数据还原为原始数据。

以上介绍了几种常用的压缩与解压缩算法，它们在数据结构中起着重要的作用。