文件的压缩与解压

u开发环境：vs2013

u开发技术：vector、堆、哈夫曼树、文件部分函数的操作

u项目描述：文件压缩是把一个占内存比较大的文件压缩成为一个占内存比较小的文件，节省了磁盘的空 间，传输时也比较方便。解压是把压缩的文件还原成原来的文件，读写比较方便。

√ 可以压缩与解压小文件，也可以压缩与解压大文件。

√ 在Debug下，压缩和解压6M左右文件，需要25s左右，在Release下，需要2s左右。

√ 有配置文件，压缩开发技术：vector、堆、哈夫曼树、文件部分函数的操作

u遇到的问题：√ 在压缩过程中不够8位会补零，但在解压过程中会把零读出来，这样就不对了。为了解决 这个问题。我在解压过程中定义了一个总长度，它写入一个字符，总长度就减1，当长度 减为0，就不进去了。

√ 有时解压大文件时，字数不想等。于是我就把’w’换成了’wb’，把’r'换了’rb’因 为用文本模式打开时，遇到’\n’，会多加’\r’，但用二进制模式打开就不会有这样的 问题。

√ 有时读大文件时，会读不全。因此我就把EOF换成了feof。因为EOF是以-1为结束标志 的，但文件中出现-1它就不会读下去了。如果换成feof的话，它是以“文件结束”为标 志。这样就不会出现读不完的情况。

compress.h中

#ifndef__Compress_H_#define__Compress_H_#include<string>typedeflonglongLongType;structCharInfo{unsignedchar_ch;//字符LongType_count;//出现次数string_code;//哈夫曼编码CharInfo(unsignedcharch='0'):_ch(ch),_count(0),_code(""){}CharInfo(LongTypecount):_count(count),_ch(0),_code(""){}//重载运算符“>”booloperator>(constCharInfo&com)const{return_count>com._count;}//重载运算符“!=”booloperator!=(CharInfocom)const{return_count!=com._count;}//重载运算符“+”CharInfooperator+(constCharInfo&com)const{returnCharInfo(_count+com._count);}};classFileCompress{public://压缩FileCompress(){for(size_ti=0;i<256;i++){_info[i]._ch=i;}}voidCompress(constchar*file){//读取文件FILE*fout=fopen(file,"rb");unsignedcharch=0;assert(fout);//统计每个字符出现的次数ch=fgetc(fout);while(!feof(fout)){_info[(unsignedchar)ch]._count++;ch=fgetc(fout);}//用次数建立哈夫曼树constCharInfoinvalid((unsignedchar)0);HaffmanTree<CharInfo>tree(_info,256,invalid);//生成哈夫曼编码stringtmp;_CreateHaffmanCode(tree.GetRoot(),tmp);//压缩fseek(fout,0,SEEK_SET);//从文件的首字符开始压缩//压缩后的文件名stringcomfile=file;comfile+=".haffman";FILE*fin=fopen(comfile.c_str(),"wb");assert(fin);unsignedcharvalue=0;size_tindex=0;//标记当前位ch=fgetc(fout);while(!feof(fout)){stringcode=_info[ch]._code;for(size_ti=0;i<code.size();i++){if(code[i]=='1'){value<<=1;value|=1;}else{value<<=1;}//满8个字节，将其写入到压缩文件中if(++index==8){fputc(value,fin);value=0;index=0;}}ch=fgetc(fout);}//如果写入完，value没有写满8位，把剩余的压入压缩文件中if(index!=0){value<<=(8-index);fputc(value,fin);}//配置文件stringconfigfile=file;configfile+=".config";FILE*finfo=fopen(configfile.c_str(),"wb");assert(finfo);//将字符的总个数写进配置文件charinfostr[32];//将出现的字符以及次数写进配置文件stringstr;for(size_tj=0;j<256;j++){if(_info[j]._count>0){str.push_back((unsignedchar)j);str.push_back(',');_itoa(_info[j]._count,infostr,10);str+=infostr;fputs(str.c_str(),finfo);fputc('\n',finfo);str.clear();}}fclose(fout);fclose(fin);fclose(finfo);}//解压voidUnCompress(constchar*file){unsignedcharch=0;stringfconfig=file;fconfig+=".config";//读压缩文件FILE*fout=fopen(fconfig.c_str(),"rb");assert(fout);stringtmp;//字符出现的次数while(ReadLine(fout,tmp)){if(!tmp.empty()){//那到字符ch=tmp[0];//获取字符的次数_info[(unsignedchar)ch]._count=atoi(tmp.substr(2).c_str());tmp.clear();}else{tmp='\n';}}//重建哈夫曼树CharInfoinvalid((unsignedchar)0);HaffmanTree<CharInfo>h(_info,256,invalid);HaffmanTreeNode<CharInfo>*root=h.GetRoot();//解压stringoutput=file;output+=".uncom";FILE*fin=fopen(output.c_str(),"wb");assert(fin);//根据压缩文件，还原文件stringHaffmanfile=file;Haffmanfile+=".haffman";FILE*fcom=fopen(Haffmanfile.c_str(),"rb");assert(fcom);HaffmanTreeNode<CharInfo>*cur=root;ch=fgetc(fcom);intpos=8;LongTypelen=root->_weight._count;while(len>0){while(cur->_left&&cur->_right){if(pos==0){ch=fgetc(fcom);pos=8;}--pos;//与1，走右树if(ch&(1<<pos)){cur=cur->_right;}//与0，走左树else{cur=cur->_left;}}if(cur){fputc(cur->_weight._ch,fin);//写进解压文件cur=root;}--len;}fclose(fout);fclose(fin);fclose(fcom);}protected://创建哈夫曼编码void_CreateHaffmanCode(HaffmanTreeNode<CharInfo>*root,stringtmp){//判空if(root==NULL){return;}if(root->_left==NULL&&root->_right==NULL){//找到下标，把编码写到_code中intindex=(root->_weight)._ch;_info[index]._code=tmp;}else{//左树写0if(root->_left){tmp.push_back('0');_CreateHaffmanCode(root->_left,tmp);tmp.pop_back();}//右树写1if(root->_right){tmp.push_back('1');_CreateHaffmanCode(root->_right,tmp);tmp.pop_back();}}}//读一行boolReadLine(FILE*file,string&tmp){assert(file);charch=fgetc(file);if(feof(file)){returnfalse;}while(ch!='\n'){tmp+=ch;ch=fgetc(file);}returntrue;}protected:CharInfo_info[256];};#endif//__Compress_H_

HaffmanTree.h中

#ifndef__HaffmanTree_H_#define__HaffmanTree_H_#include"Heap.h"template<classT>structHaffmanTreeNode{typedefHaffmanTreeNode<T>Node;T_weight;Node*_left;Node*_right;HaffmanTreeNode(constT&weight):_weight(weight),_left(NULL),_right(NULL){}};template<classT>classHaffmanTree{typedefHaffmanTreeNode<T>Node;public:HaffmanTree():_root(NULL){}HaffmanTree(constT*arr,size_tsize){_root=_Create(arr,size);}//构造函数HaffmanTree(constT*arr,size_tsize,constT&invalid){_root=_Create(arr,size,invalid);}~HaffmanTree(){if(_root){_Destroy(_root);}}Node*GetRoot(){return_root;}protected://创建哈夫曼树Node*_Create(constT*arr,size_tsize,constT&invalid){structcompare{booloperator()(constNode*left,constNode*right){returnleft->_weight>right->_weight;}};Heap<Node*,compare>_heap;//把值放到vector中for(size_ti=0;i<size;++i){if(arr[i]!=invalid){Node*tmp=newNode(arr[i]);_heap.Push(tmp);}}//构造哈夫曼树while(_heap.Size()>1){Node*left=_heap.Top();_heap.Pop();Node*right=_heap.Top();_heap.Pop();Node*parent=newNode(left->_weight+right->_weight);parent->_left=left;parent->_right=right;_heap.Push(parent);}return_heap.Top();}//释放节点void_Destroy(Node*root){if(root->_left==NULL&&root->_right==NULL){deleteroot;root=NULL;}else{_Destroy(root->_left);_Destroy(root->_right);}}private:Node*_root;};#endif//__HaffmanTree_H_

Heap.h中

#ifndef__Heap_H_#define__Heap_H_#include<vector>#include<assert.h>template<classT>//比较器classLess{public:booloperator()(constT&left,constT&right){returnleft>right;}};template<classT>classGreater{public:booloperator()(constT&left,constT&right){returnleft<right;}};template<classT,classCompare=Less<T>>classHeap{public://构造函数Heap():_arr(NULL){}Heap(constT*arr,intsize){assert(arr);_arr.reserve(size);for(inti=0;i<size;i++){_arr.push_back(arr[i]);}intbegin=_arr.size()/2-1;while(begin>=0){_AdjustDown(begin);begin--;}}//拷贝构造Heap(vector<T>&s){_arr=s;intbegin=_arr.size()/2-1;while(begin>=0){_AdjustDown(begin);begin--;}}voidPush(constT&x){_arr.push_back(x);intbegin=_arr.size();_AdjustUp(begin);}voidPop(){_arr[0]=_arr[_arr.size()-1];_arr.pop_back();_AdjustDown(0);}voidClear(){_arr.clear();}boolEmpty(){return_arr.empty();}T&Top(){if(!Empty()){return_arr[0];}exit(1);}size_tSize(){return_arr.size();}protected://下调void_AdjustDown(intparent){//从根节点向下调整intsize=_arr.size();intleft=parent*2+1;intright=left+1;intkey=left;while(left<size){//Compare()仿函数//if(right<size&&array[left]>array[right])if(right<size&&Compare()(_arr[left],_arr[right]))//右边小{key=right;}else{key=left;}//if((array[key]>array[parent]))if(Compare()(_arr[key],_arr[parent])){break;}//elseif(array[parent]>array[key])elseif(Compare()(_arr[parent],_arr[key]))//左边小{swap(_arr[key],_arr[parent]);}parent=key;left=parent*2+1;right=left+1;}}//上调void_AdjustUp(intchild){//从叶子节点或子节点向上调整intsize=_arr.size();if(size==0||size==1){return;}intparent=(child-2)/2;intleft=parent*2+1;intright=left+1;intkey=0;while(parent>=0){//if(right<size&&array[left]>array[right])if(right<size&&Compare()(_arr[left],_arr[right])){key=right;}else{key=left;}//if(array[parent]>array[key])if(Compare()(_arr[parent],_arr[key])){swap(_arr[parent],_arr[key]);}else{break;}if(parent==0){break;}parent=(parent-1)/2;left=parent*2+1;right=left+1;}}private:vector<T>_arr;};#endif//__Heap_H_

test.cpp中

#define_CRT_SECURE_NO_WARNINGS1#include<time.h>#include<iostream>usingnamespacestd;#include"HaffmanTree.h"#include"Compress.h"voidTest(){doublet1;doublet2;FileCompressf;//f.Compress("input.txt");f.Compress("mnt.txt");t1=clock();printf("压缩文件需要的时间:%fs\n",t1/CLOCKS_PER_SEC);//f.UnCompress("input.txt");f.UnCompress("mnt.txt");t2=clock();printf("解压缩文件需要的时间:%fs\n",t2/CLOCKS_PER_SEC);}intmain(){Test();system("pause");return0;}