数据结构实验报告利用Huffman编码对文件进行压缩解压

Huffman的应用之文件压缩与解压缩最近这段时间一直在学习树的这种数据结构,也接触到了Huffman树以及了解了什仫是Huffman编码,而我们常用的zip压缩也是利用的Huffman编码的特性，那仫是不是可以自己实现一个文件压缩呢？当然可以了.在文件压缩中我实现了Huffman树和建堆Heap的代码，zip压缩的介绍>下面开始介绍自己实现的文件压缩的思路和问题...1).统计>读取一个文件统计这个文件中字符出现的次数.2).建树>以字符出现的次数作为权值使用贪心算法构建Huffman树(根据Huffman树的特性>字符出现次数多的一定靠近根结点，出现次数少的一定远离根结点).3).生成Huffman编码>规则左0右1.4).压缩>再次读取文件,根据生成的Huffman编码压缩文件.5).生成配置文件>将字符以及字符出现的次数写进配置文件中.6).解压缩>利用配置文件还原出Huffman树,根据压缩文件还原出原文件.7).测试>判断解压是否正确需要判断原文件和解压缩之后的文件是否相同,利用Beyond Compare软件进行对比.下面是我举的一个简单的范例，模拟压缩和解压缩的过程，希望有读者有帮助利用Beyond Compare软件进行对比>在实现中出现了很多的问题,下面我提出几个容易犯的问题,仅供参考1).在使用贪心算法构建Huffman树的时候,如果我们以unsigned char一个字节来存储它总共有2^8=256个字符,如果将所有的字符都构建Huffman树,这不仅降低了效率还将分配极大的内存.所以我设立了非法值这个概念,只有当字符出现的次数不为0的时候才将该字符构建到Huffman树中.2).在写压缩文件的时候我们是将字符对应的Huffman编码转化为对应的位,每当填满一个字节(8位)后再写入压缩文件中.如果最后一个字节没有填满我们就将已经填的位移位空出后几个位置,将未满的位置补0补满一个字节再写入压缩文件中.3).如果我们将源文件压缩之后再去解压,因为你的Huffman树和Huffman编码都是在压缩函数中得到的,此时再去解压那仫你的Huffman编码以及不存在了该如何去还原文件呢？这就是为什仫要生成配置文件的原因了,在配置文件中写入了字符以及字符出现的次数.在解压缩中根据配置文件构建新的Huffman树.4).由压缩文件还原文件的时候如何知道压了多少个字符呢？也就是说因为我们在压缩的时候最后一个字节是补了0的在解压缩的时候可能会把这个补的位当成字符的编码来处理.一种想法是在统计字符出现的次数的时候设置一个变量,每读取一个字符该变量就加1,最后将该变量写进配置文件中.另外一种想法就是根据根结点的权值,通过上述简单的实例观察可知根结点权值中的_count就是字符出现的次数.解决了以上几个问题,我的程序已经可以压缩那256个字符并正确的还原了,那仫如果是大文件或者是汉字，图片以及音频视频呢？1).因为有些特殊的字符编码，所以我们统计字符出现的次数的时候应该用的是unsigned char,刚开始我用的文件结束标志是EOF在ASII中它的编码是-1此时已经不可以用EOF来判断是否文件结束了，所以我用了feof这个函数来判断文件是否结束.2).统计字符出现次数应该用的类型是long long,这就解决了大文件的压缩和解压缩的问题了.3).因为汉字，图片，视频这些在内存中是以二进制的形式存在的,所以我们将以文本形式打开读或者写的修改为以二进制的形式读或者写.为了验证大文件的压缩我找了一个8.09M的文件压缩之后是6.50M,并且可以正确还原.1).测试效率>2).利用Beyond Compare软件进行对比，如果一样说明压缩成功>[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片#define _CRT_SECURE_NO_W ARNINGS 1#pragma once#include "Heap.h"template<class T>struct HuffmanTreeNode{T _weight;HuffmanTreeNode<T> *_left;HuffmanTreeNode<T> *_right;HuffmanTreeNode<T> *_parent;HuffmanTreeNode(const T& w=T()):_weight(w),_left(NULL),_right(NULL),_parent(NULL){}};template<class T>class HuffmanTree{typedef HuffmanTreeNode<T> Node;public:HuffmanTree():_root(NULL){}HuffmanTree(const T* a,size_t size):_root(NULL){_root=_CreatHuffmanTree(a,size);}//将未出现的字符过滤出来，不构造堆HuffmanTree(const T* a,size_t size,const T& invalid){_root=_CreatHuffmanTree(a,size,invalid);}Node* GetRoot(){return _root;}~HuffmanTree(){_Destroy(_root);}protected:Node *_CreatHuffmanTree(const T* a,size_t size){struct NodeLess{bool operator()(Node *l,Node *r)const{return l->_weight < r->_weight;}};Heap<Node *,NodeLess> minHeap;//建立结点并放入vector中for (size_t i=0;i<size;++i){Node *tmp=new Node(a[i]);minHeap.Push(tmp);}//取出较小的两个结点作为左右孩子并构建父结点while (minHeap.Size() > 1){Node *left=minHeap.Top();minHeap.Pop();Node *right=minHeap.Top();minHeap.Pop();Node *parent=new Node(left->_weight + right->_weight);parent->_left=left;parent->_right=right;left->_parent=parent;right->_parent=parent;minHeap.Push(parent);}return minHeap.Top();}//思路类似不带过滤功能的Node *_CreatHuffmanTree(const T* a,size_t size,const T& invalid) {struct NodeLess{bool operator()(Node *l,Node *r)const{return l->_weight < r->_weight;}};Heap<Node *,NodeLess> minHeap;//建立结点并放入vector中for (size_t i=0;i<size;++i){if(a[i] != invalid){Node *tmp=new Node(a[i]);minHeap.Push(tmp);}}//取出较小的两个结点作为左右孩子并构建父结点while (minHeap.Size() > 1){Node *left=minHeap.Top();minHeap.Pop();Node *right=minHeap.Top();minHeap.Pop();Node *parent=new Node(left->_weight + right->_weight);parent->_left=left;parent->_right=right;left->_parent=parent;right->_parent=parent;minHeap.Push(parent);}return minHeap.Top();}void _Destroy(Node *&root)if(root == NULL)return ;Node *cur=root;if(cur){_Destroy(cur->_left);_Destroy(cur->_right);delete cur;cur=NULL;return ;}}protected:Node *_root;};void testHuffmanTree(){int a[]={0,1,2,3,4,5,6,7,8,9};int size=sizeof(a)/sizeof(a[0]);HuffmanTree<int> ht(a,size);}[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片#define _CRT_SECURE_NO_W ARNINGS 1#pragma once//利用仿函数的特性实现代码的复用性template<class T>struct Small{bool operator()(const T& l,const T& r){return l < r;}};template<class T>struct Large{bool operator()(const T& l,const T& r)return l > r;}};template<class T,class Compare=Large<T>> //缺省是建小堆class Heap{public:Heap(){}Heap(const T *a,int size){assert(a);_a.reserve(size);for (int i=0;i<size;++i){_a.push_back(a[i]);}//建堆的时候从倒数第一个非叶子结点开始.for (int j=(size-2)/2;j>=0;--j){_AdjustDown(j);}}void Push(const T& x){_a.push_back(x);_AdjustUp(_a.size()-1);}void Pop(){assert(!_a.empty());swap(_a[0],_a[_a.size()-1]);_a.pop_back();_AdjustDown(0);}size_t Size(){return _a.size();}bool Empty(){return _a.empty();const T& Top()const{assert(!_a.empty());return _a[0];}void Display(){for (size_t i=0;i<_a.size();++i){cout<<_a[i]<<" ";}cout<<endl;}protected:void _AdjustDown(int root){int parent=root;size_t child=2*root+1;while (child < _a.size()){Compare com;//child指向左右孩子中较大的那个数//if (child+1 < _a.size()// && _a[child+1] > _a[child])if(child+1 < _a.size()&& com(_a[child+1],_a[child])){child++;}//if (_a[child] > _a[parent])if(com(_a[child],_a[parent])){swap(_a[child],_a[parent]);parent=child;//初始的child默认指向左孩子child=2*parent+1;}elsebreak;}}void _AdjustUp(int child){while (child > 0){int parent=(child-1)/2;Compare com;//if (_a[child] > _a[parent])if(com(_a[child],_a[parent])){swap(_a[child],_a[parent]);child=parent;}else//插入的数据比父节点的数据域小break;}}protected:vector<T> _a;};//利用堆解决优先级队列的问题template<class T,class Compare=Large<T>>class PriorityQueue{public:PriorityQueue(int *a,int size):_pq(a,size){}void Push(const T& x){_pq.Push(x);}void Pop(){_pq.Pop();}const T& Top()const{return _pq.Top();}void Display(){_pq.Display();}protected:Heap<T,Compare> _pq;};[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片#define _CRT_SECURE_NO_W ARNINGS 1#pragma once#include "HuffmanTree.h"typedef long long Type;struct CharInfo{unsigned char _ch; //出现的字符Type _count; //统计次数string _code; //Huffman编码CharInfo(Type count=0):_ch(0),_count(count),_code(""){}//重载对应的操作符CharInfo operator + (const CharInfo& fc)const{return CharInfo(_count + fc._count);}bool operator != (const CharInfo fc)const{return _count != fc._count;}bool operator < (const CharInfo& fc)const{return _count < fc._count;}};class FileCompress{public://默认的构造函数FileCompress(){for(size_t i=0;i<256;++i){_infos[i]._ch=i;}}string Compress(const char *filename){assert(filename);FILE *pf=fopen(filename,"rb");assert(pf);unsigned char ch=fgetc(pf);//统计字符出现的次数while (!feof(pf)){_infos[ch]._count++;ch=fgetc(pf);}//以该字符出现的次数构建一颗HuffmanTree.CharInfo invalid; //非法值HuffmanTree<CharInfo> ht(_infos,256,invalid);//生成Huffman编码string code;_CreatHuffmanCode(ht.GetRoot(),code);//_CreatHuffmanCode(ht.GetRoot());//压缩文件fseek(pf,0,SEEK_SET); //回到文件头string compressfile=filename;compressfile += ".compress"; //压缩后的文件名FILE *fin=fopen(compressfile.c_str(),"wb");assert(fin);size_t pos=0; //记录位数unsigned char value=0;ch=fgetc(pf);while (!feof(pf)){string &code=_infos[ch]._code;for (size_t i=0;i<code.size();++i){value <<= 1;if(code[i] == '1')value |= 1;elsevalue |= 0; //do-nothing++pos;if(pos == 8) //满一个字节{fputc(value,fin);value=0;pos=0;}}ch=fgetc(pf);}if(pos) //解决不足8位的情况.{value <<= (8-pos);fputc(value,fin);}//配置文件--便于重建Huffman树string ename=filename;configfilename += ".config";FILE *finconfig=fopen(configfilename.c_str(),"wb");assert(finconfig);string line;char buff[128];for (size_t i=0;i<256;++i){//一行一行的读if (_infos[i]._count){line += _infos[i]._ch;line += ",";line += _itoa(_infos[i]._count,buff,10);line += "\n";//fputs(line.c_str(),finconfig);fwrite(line.c_str(),1,line.size(),finconfig);line.clear();}}fclose(pf);fclose(fin);fclose(finconfig);return compressfile;}string UnCompress(const char *filename){assert(filename);string configfilename=filename;size_t index=configfilename.rfind(".");configfilename=configfilename.substr(0,index); configfilename += ".config";FILE *foutconfig=fopen(configfilename.c_str(),"rb"); assert(foutconfig);string line;//读取配置文件--获取字符出现的次数unsigned char ch=0;while (ReadLine(foutconfig,line)){if(line.empty()){line += '\n';continue;}//读到空行ch=line[0];_infos[ch]._count = atoi(line.substr(2).c_str());line.clear();}//构建Huffman树CharInfo invalid;HuffmanTree<CharInfo> hft(_infos,256,invalid);//根结点的权值也就是字符出现的次数总和HuffmanTreeNode<CharInfo> *root=hft.GetRoot(); Type charcount=root->_weight._count;//解压缩string uncompressfilename=filename;index=uncompressfilename.rfind("."); uncompressfilename=uncompressfilename.substr(0,index); uncompressfilename += ".uncompress";FILE *fin=fopen(uncompressfilename.c_str(),"wb"); assert(fin);//由压缩文件还原文件string compressfilename=filename;FILE *fout=fopen(compressfilename.c_str(),"rb");assert(fout);HuffmanTreeNode<CharInfo> *cur=root;int pos=7;ch=fgetc(fout);while (charcount > 0){while (cur){if(cur->_left == NULL && cur->_right == NULL){//叶子结点fputc(cur->_weight._ch,fin);cur=root;--charcount;if (charcount == 0) //所有的字符都处理完成break;}if (ch & (1 << pos)) //检查字符的每个位cur=cur->_right; //1向右走elsecur=cur->_left; //0向左走--pos;if(pos < 0) //一个字节解压完成{ch=fgetc(fout);pos=7;}}}fclose(foutconfig);fclose(fin);fclose(fout);return uncompressfilename;}//读取一行字符并放在line中bool ReadLine(FILE *fout,string& line){int ch=fgetc(fout);if(ch == EOF)return false;while (ch != EOF && ch != '\n'){line += ch;ch=fgetc(fout);}return true;}protected://递归的方法求HuffmanTreeCodevoid _CreatHuffmanCode(HuffmanTreeNode<CharInfo> *root,string &code) {if(root == NULL)return ;_CreatHuffmanCode(root->_left,code+'0');_CreatHuffmanCode(root->_right,code+'1');if(root->_left == NULL && root->_right == NULL) //叶子结点{_infos[root->_weight._ch]._code=code;}}//非递归求HuffmanTreeCodevoid _CreatHuffmanCode(HuffmanTreeNode<CharInfo> *root){if(root == NULL)return ;_CreatHuffmanCode(root->_left);_CreatHuffmanCode(root->_right);if(root->_left == NULL && root->_right == NULL) //叶子结点{string& code=_infos[root->_weight._ch]._code;HuffmanTreeNode<CharInfo> *cur=root;HuffmanTreeNode<CharInfo> *parent=root->_parent;while (parent){if(parent->_left == cur)code.push_back('0'); //左0elsecode.push_back('1'); //右1cur=parent;parent=cur->_parent;}//编码是从根到叶子结点的，需要逆置reverse(code.begin(),code.end());}}protected:CharInfo _infos[256];};void testFileCompress(){FileCompress fc;cout<<"开始压缩"<<endl;cout<<"压缩用时:";int start=GetTickCount();press("2.png"); //input input.BIG 3.mp3int end=GetTickCount();cout<<end-start<<endl;cout<<"开始解压"<<endl;cout<<"解缩用时:";start=GetTickCount();fc.UnCompress("press"); //press press 3.mp3end=GetTickCount();cout<<end-start<<endl;}void testFileUncompress(){FileCompress fc;cout<<"开始解压"<<endl;cout<<"解缩用时:";int start=GetTickCount();fc.UnCompress("2.png");int end=GetTickCount();cout<<end-start<<endl;}经过测试这个小项目已经可以压缩并还原一些文件了，目前还没有发现什仫大的Bug,如果有童鞋发现请第一时间告诉我哦...。

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

第1篇一、实验目的1. 了解数据压缩的基本原理和方法。

2. 掌握常用数据压缩算法的应用。

3. 分析不同数据压缩算法的性能和适用场景。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3. 数据压缩工具：Huffman编码、LZ77、LZ78、RLE、JPEG、PNG三、实验内容1. Huffman编码2. LZ77编码3. LZ78编码4. RLE编码5. 图像压缩：JPEG、PNG四、实验步骤1. Huffman编码（1）设计Huffman编码树，计算每个字符的频率。

（2）根据频率构建Huffman编码树，为每个字符分配编码。

（3）将原始数据按照Huffman编码进行编码，得到压缩数据。

（4）解压缩：根据编码表还原原始数据。

2. LZ77编码（1）设计LZ77编码算法，查找匹配的字符串。

（2）将原始数据按照LZ77编码进行编码，得到压缩数据。

（3）解压缩：根据编码表还原原始数据。

3. LZ78编码（1）设计LZ78编码算法，查找匹配的字符串。

（2）将原始数据按照LZ78编码进行编码，得到压缩数据。

（3）解压缩：根据编码表还原原始数据。

4. RLE编码（1）设计RLE编码算法，统计连续字符的个数。

（2）将原始数据按照RLE编码进行编码，得到压缩数据。

（3）解压缩：根据编码表还原原始数据。

5. 图像压缩：JPEG、PNG（1）使用JPEG和PNG工具对图像进行压缩。

（2）比较压缩前后图像的质量和大小。

五、实验结果与分析1. Huffman编码（1）压缩前后数据大小：原始数据大小为100KB，压缩后大小为25KB。

（2）压缩效率：压缩比约为4:1。

2. LZ77编码（1）压缩前后数据大小：原始数据大小为100KB，压缩后大小为35KB。

（2）压缩效率：压缩比约为3:1。

3. LZ78编码（1）压缩前后数据大小：原始数据大小为100KB，压缩后大小为30KB。

（2）压缩效率：压缩比约为3.3:1。

用Huffman编码实现文档压缩实验目的1.了解有关文件的基本概念和操作2.掌握哈夫曼树的概念及其构造方法3.运用哈夫曼树及其编码实验环境Windows 7 Professional Service Park 1 ,64bitMicrosoft Visual Studio 2010实验内容输入需要压缩的文本文件名，对该文件中的各个字符出现的频度进行统计，然后构建Huffman编码树及Huffman编码表。

读入源文件，将源文件翻译成Huffman编码文件，输出到文件1.huf，最后读入1.huf文件，将Huffman编码文件翻译成文本文件，输出到_1.txt。

要求计算压缩比输出：压缩比是编码后文件字符数除以编码前文件中含有字符数。

设计概要压缩部分1.构造哈夫曼树，对其进行前缀编码（1）扫描待压缩文件，得出各字符出现频率。

（2）根据给定的n个权值{W1,W2,...Wn}构成n棵二叉树的集合F={T1，T2，…，Tn}，每棵二叉树Ti中只有一个带权为Wi的根节点，其左右子树均空。

（3）在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且值新的二叉树的根节点的权值为其左右子树上根节点的全值之和。

（4）在F中删除这两棵树。

同时将新得到的二叉树加入F中。

重置（2）和（3），直到F只含一棵树为止。

这棵树便是哈夫曼树。

2.由Huffman树得到各字符前缀编码。

3.根据前缀编码，对文件中各个字符进行编码，并按每八位一次写入压缩文件。

4.处理剩余不到八位部分，写入压缩文件。

5.将前缀编码及相关信息写入压缩文件。

6.关闭指针，完成压缩。

计算压缩率。

解压部分1.读入压缩文件长度和源文件长度、读入前缀编码。

2.对文件中各字符解码，写入解压文件。

源码：#include<stdio.h>#include<malloc.h>#include<string.h>#include <stdlib.h>struct hufflist{unsigned char asc;long weight;char code;int par,lch,rch;hufflist(){asc=-1;weight=0;par=lch=rch=-1;}; //初始化};//缓冲队列typedef struct temp{int n,fr,be;char ctemp[1200];temp(){n=fr=be=0;};int push(char ch){if(n>1024)return 1;ctemp[be]=ch;be++;be=be%1024;n++;return 0;};char pop(void){char ch;if(n==0)return 0;ch=ctemp[fr];fr++;fr=fr%1024;n--;return ch;};}temp;void main(){FILE *fp1,*fp2,*fp3;int ch=0;float ra;char infile[256];char outfile[256];float compress(FILE *infile,FILE *outfile);void uncompress(FILE *infile,FILE *outfile);while(ch!=3){system("cls");printf("==================文档压缩&解压工具================== \n\n\n");printf("① >> 压缩文档\n\n② >> 解压文档\n\n③ >> 退出程序\n\n\n");printf("请输入要进行的操作：\n");scanf("%d",&ch);switch(ch){case 1:{printf("请输入原文件路径：");getchar();gets(infile);if((fp1=fopen(infile,"r"))==NULL){printf("ERROR！文件打开失败！\n");getchar();break;}printf("请输入输出文件路径：");gets(outfile);if((fp2=fopen(outfile,"wb"))==NULL){printf("ERROR！文件打开失败！\n");getchar();break;}if(strcmp(infile,outfile)==0){printf("ERROR！文件路径冲突！\n");getchar();break;}ra=compress(fp1,fp2);printf("文件压缩完成！\n");printf("压缩比率为%.4f%%\n",ra*100);getchar();break;}case 2:{printf("请输入原文件路径：");getchar();gets(infile);if((fp2=fopen(infile,"rb"))==NULL){printf("ERROR！文件打开失败！\n");getchar();break;}printf("请输入输出文件路径：");gets(outfile);if((fp3=fopen(outfile,"w"))==NULL){printf("ERROR！文件打开失败！\n");getchar();break;}if(strcmp(infile,outfile)==0){printf("ERROR！文件路径冲突！\n");getchar();break;}uncompress(fp2,fp3);printf("文件解压完毕！\n");getchar();break;}default:{ch=3;printf("程序关闭！\n");break;}}}return;}float compress(FILE *infile,FILE *outfile){struct hufflist HT[513];char **HC;int ROOT,i,j,k,s,node_count=0,lnode_count,lnode_count_t,ad1,ad2;//node_count 总结点个数 lnode_count没有父节点的节点个数long weight2=0;float sv,a,b;unsigned char ch;temp mytemp;char *ct=NULL;//先统计输入文本infile中字符信息ch=fgetc(infile);while(!feof(infile)){for(i=0;i<=513;i++){if(HT[i].asc==ch){HT[i].weight++;break;}if(HT[i].weight==0){HT[i].asc=ch;HT[i].weight++;node_count++;break;}}ch=fgetc(infile);}lnode_count=node_count;lnode_count_t=lnode_count;while(lnode_count_t>1){//找到权值最小节点for(i=0;i<node_count;i++){if(HT[i].par==-1)break;}ad1=i;for(j=i+1;j<node_count;j++){if(HT[j].par==-1&&HT[j].weight<HT[i].weight)ad1=j;}HT[ad1].par=1;//找到权值次小节点for(i=0;i<=node_count;i++){if(HT[i].par==-1)break;}ad2=i;for(j=i+1;j<node_count;j++){if(HT[j].par==-1&&HT[j].weight<HT[i].weight)ad2=j;}HT[ad2].par=1;HT[ad1].par=HT[ad2].par=node_count;HT[node_count].lch=ad1;HT[node_count].rch=ad2;HT[ad1].code=0;HT[ad2].code=1;HT[node_count].weight=HT[ad1].weight+HT[ad2].weight;node_count++;lnode_count_t--;}ROOT=node_count-1;fwrite(HT,sizeof(struct hufflist),513,outfile);//建立编码表HC=(char **)malloc(256*sizeof(char *));ct=(char *)malloc((lnode_count+1)*sizeof(char));ct[lnode_count]=-1;for(i=0;i<=255;i++){HC[i]=NULL;}for(i=0;i<lnode_count;i++){for(k=i,j=lnode_count-1;HT[k].par!=-1;k=HT[k].par,j--){ct[j]=HT[k].code;}HC[HT[i].asc]=(char*)malloc(lnode_count*sizeof(char));for(s=0,j++;ct[j]!=-1;s++,j++){HC[HT[i].asc][s]=ct[j];}HC[HT[i].asc][s]=-1;}rewind(infile);//重编码ch=fgetc(infile);while(!feof(infile)){for(i=0;HC[ch][i]!=-1;i++){mytemp.push(HC[ch][i]);}while(mytemp.n>=8){ch=128*mytemp.pop()+64*mytemp.pop()+32*mytemp.pop()+16*mytemp.pop()+8*mytemp.pop()+4*my temp.pop()+2*mytemp.pop()+mytemp.pop();fwrite(&ch,1,1,outfile);weight2++;}ch=fgetc(infile);}while(mytemp.n>0){ch=128*mytemp.pop()+64*mytemp.pop()+32*mytemp.pop()+16*mytemp.pop()+8*mytemp.pop()+4*my temp.pop()+2*mytemp.pop()+mytemp.pop();fwrite(&ch,1,1,outfile);weight2++;}fclose(infile);fclose(outfile);a=weight2+513*sizeof(struct hufflist);b=HT[ROOT].weight;sv=a/b;return(sv);}void uncompress(FILE *infile,FILE *outfile){struct hufflist HT[513];int ROOT,i=0;unsigned char ch;temp mytemp;fread(HT,sizeof(struct hufflist),513,infile);while(HT[i].par!=-1){i=HT[i].par;}ROOT=i;fread(&ch,1,1,infile);while(!feof(infile)){while(mytemp.n<=768&&(!feof(infile))){for(i=0;i<=7;i++){mytemp.push((ch<<i&128)/128);}fread(&ch,1,1,infile);}i=ROOT;do{if(mytemp.pop())i=HT[i].rch;elsei=HT[i].lch;}while(HT[i].lch!=-1);fputc(HT[i].asc,outfile);}while(mytemp.n>0){i=ROOT;do{if(mytemp.pop())i=HT[i].rch;elsei=HT[i].lch;}while(HT[i].lch!=-1&& mytemp.n>0);fputc(HT[i].asc,outfile);}fclose(infile);fclose(outfile);return;}数据测试文件： D:\1.txt(英文原著《飘》) 大小：2.25MB 程序运行界面：压缩后实际文件大小对比：解压后文件对比：进一步测试了多个文本文件，程序运行正常，未发现错误。

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

《用哈夫曼编码实现文件压缩》实验报告课程名称数据结构（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编码对文件进行压缩解压学生: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还有某网站上树的遍历算法(八)源程序见同一文件夹内.。

数据结构课程设计报告--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压缩方法，并与之比较。

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

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

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

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

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

三、实验设备与环境：微型计算机、Windows 系列操作系统、Visual C++四、实验内容：根据输入小写英文字母和输入的对应权值创建哈夫曼树，可以求出每个小写英文字母的哈夫曼编码，将文本中的字母对应的哈夫曼编码写入文本中，实现对文本的编码。

五、概要设计：（1）构造Hufffman树的Hufffman算法构造Huffman树步骤：1.根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，起权值为wj。

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

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

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

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

(3) 文本编码读取存放在文本中的字母，一对一的进行编译，将对应的编码存放到另一个文本中。

#include<>#include<>#include<>//树结点定义typedef struct{int weight;int parent;int lchild;int rchild;}HTNode,*HuffmanTree;static char N[100];//用于保存字符//赫夫曼编码，char型二级指针typedef char **HuffmanCode;//封装最小权结点和次小权结点typedef struct{int s1;int s2;}MinCode;//函数声明void Error();HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n);MinCode Select(HuffmanTree HT,int n);//当输入1个结点时的错误提示void Error(){printf("一个字符不进行编码!\n");exit(1);}//构造赫夫曼HT，编码存放在HC中,w为权值,n为结点个数HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n){int i,s1=0,s2=0;HuffmanTree p;char *cd;int f,c,start,m;MinCode min;if(n<=1){Error();//只有一个结点不进行编码，直接exit(1)退出}m=2*n-1;//赫夫曼码需要开辟的结点大小为2n-1HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//开辟赫夫曼树结点空间m+1//初始化n个叶子结点for(p=HT,i=0;i<=n;i++,p++,w++){p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}//将n-1个非叶子结点的初始化for(;i<=m;i++,p++){p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}//构造赫夫曼树for(i=n+1;i<=m;i++){min=Select(HT,i-1);//找出最小和次小的两个结点s1= ; //最小结点下标s2=;//次小结点下标HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//赋权和}//打印赫夫曼树printf("HT List:\n");printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");for(i=1;i<=m;i++){printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\t\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);}//从叶子结点到根节点求每个字符的赫夫曼编码HC=(HuffmanCode)malloc((n+1)*sizeof(char *));cd=(char *)malloc(n*sizeof(char *));//为赫夫曼编码动态分配空间cd[n-1]='\0';//编码结束符//求叶子结点的赫夫曼编码for(i=1;i<=n;i++){start=n-1;//定义左子树为0，右子树为1/*从最下面的1号节点开始往顶部编码(逆序存放)，然后编码2号节点，3号......*/for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent){if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';}//为第i个字符分配编码空间HC[i]=(char *)malloc((n-start)*sizeof(char *));//将当前求出结点的赫夫曼编码复制到HCstrcpy(HC[i],&cd[start]);}free(cd);return HC;}MinCode Select(HuffmanTree HT,int n){int min,secmin;int temp = 0;int i,s1,s2,tempi = 0;MinCode code ;s1=1;s2=1;min = 999999;//足够大//找出权值weight最小的结点，下标保存在s1中for(i=1;i<=n;i++){if(HT[i].weight<min && HT[i].parent==0){min=HT[i].weight;s1=i;}}secmin = 999999;//足够大//找出权值weight次小的结点，下标保存在s2中for(i=1;i<=n;i++){if((HT[i].weight<secmin) && (i!=s1) && HT[i].parent==0){secmin=HT[i].weight;s2=i;}}//放进封装中=s1;=s2;return code;}void Compression(HuffmanCode HC) //翻译原文档字符为赫夫曼编码FILE *fp1,*fp2;char ch;if((fp1 = fopen("","r")) == NULL)exit(0);if((fp2 = fopen("","a")) == NULL)exit(0);ch = fgetc(fp1);while((int)ch!= -1){switch(ch){case 'a': fputs(HC[1],fp2); break;case 'b': fputs(HC[2],fp2); break;case 'c': fputs(HC[3],fp2); break;case 'd': fputs(HC[4],fp2); break;case 'e': fputs(HC[5],fp2); break;case 'f': fputs(HC[6],fp2); break;case 'g': fputs(HC[7],fp2); break;case 'h': fputs(HC[8],fp2); break;case 'i': fputs(HC[9],fp2); break;case 'j': fputs(HC[10],fp2); break;case 'k': fputs(HC[11],fp2); break;case 'l': fputs(HC[12],fp2); break;case 'm': fputs(HC[13],fp2); break;case 'n': fputs(HC[14],fp2); break;case 'o': fputs(HC[15],fp2); break;case 'p': fputs(HC[16],fp2); break;case 'q': fputs(HC[17],fp2); break;case 'r': fputs(HC[18],fp2); break;case 's': fputs(HC[19],fp2); break;case 't': fputs(HC[20],fp2); break;case 'u': fputs(HC[21],fp2); break;case 'v': fputs(HC[22],fp2); break;case 'w': fputs(HC[23],fp2); break;case 'x': fputs(HC[24],fp2); break;case 'y': fputs(HC[25],fp2); break;case 'z': fputs(HC[26],fp2); break;default: printf(" 没有编码！\n");}ch = fgetc(fp1);}fclose(fp1);fclose(fp2);void main(){HuffmanTree HT=NULL;HuffmanCode HC=NULL;int *w=NULL;int i,n;printf("输入字符：");gets(N);n = strlen(N);w=(int *)malloc((n+1)*sizeof(int *));//开辟n+1个长度的int指针空间w[0]=0;printf("输入结点权值：\n");//输入结点权值for(i=1;i<=n;i++){printf("w[%d]=",i);scanf("%d",&w[i]);}//构造赫夫曼树HT，编码存放在HC中,w为权值,n为结点个数HC=HuffmanCoding(HT,HC,w,n);//输出赫夫曼编码printf("赫夫曼:\n");printf("Number\t\tWeight\t\tCode\n");for(i=1;i<=n;i++){printf("%c\t\t%d\t\t%s\n",N[i-1],w[i],HC[i]);}Compression(HC);}选取权值最小的结点的算法：选取权值次小的结点的算法：哈夫曼树建立的算法：哈夫曼编码的算法：七、测试结果及分析：4.输出哈夫曼树：5.字符对应编码：6.要编码的文本：7.编译后的文本：价。

第1篇一、实验目的1. 理解霍夫曼编码的基本原理和实现方法。

2. 掌握霍夫曼编码在数据压缩中的应用。

3. 通过实验，加深对数据压缩技术的理解。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 20194. 数据源：文本文件三、实验原理霍夫曼编码是一种常用的数据压缩算法，适用于无损数据压缩。

它通过使用变长编码表对数据进行编码，频率高的数据项使用短编码，频率低的数据项使用长编码。

霍夫曼编码的核心是构建一棵霍夫曼树，该树是一种最优二叉树，用于表示编码规则。

霍夫曼编码的步骤如下：1. 统计数据源中每个字符的出现频率。

2. 根据字符频率构建一棵最优二叉树，频率高的字符位于树的上层，频率低的字符位于树下层。

3. 根据最优二叉树生成编码规则，频率高的字符分配较短的编码，频率低的字符分配较长的编码。

4. 使用编码规则对数据进行编码，生成压缩后的数据。

5. 在解码过程中，根据编码规则恢复原始数据。

四、实验步骤1. 读取文本文件，统计每个字符的出现频率。

2. 根据字符频率构建最优二叉树。

3. 根据最优二叉树生成编码规则。

4. 使用编码规则对数据进行编码，生成压缩后的数据。

5. 将压缩后的数据写入文件。

6. 读取压缩后的数据，根据编码规则进行解码，恢复原始数据。

7. 比较原始数据和恢复后的数据，验证压缩和解码的正确性。

五、实验结果与分析1. 实验数据实验中，我们使用了一个包含10000个字符的文本文件作为数据源。

在统计字符频率时，我们发现字符“e”的出现频率最高，为2621次，而字符“z”的出现频率最低，为4次。

2. 实验结果根据实验数据，我们构建了最优二叉树，并生成了编码规则。

使用编码规则对数据源进行编码，压缩后的数据长度为7800个字符。

将压缩后的数据写入文件，文件大小为78KB。

接下来，我们读取压缩后的数据，根据编码规则进行解码，恢复原始数据。

比较原始数据和恢复后的数据，发现两者完全一致，验证了压缩和解码的正确性。