基于哈夫曼编码的文件压缩实现(C++)

//本例用数组形式存储最优二叉树（哈夫曼树）#includevector//标准向量操作#includefstream//标准文件IO#includeiostream#includecstringusingnamespacestd;structfileInfo{//文件信息__int64size;//记录文件大小，供以后扩展多文件和文件夹功能charname[200];};structnode{intparent,lchild,rchild;__int64percent;//权值};//定义哈夫曼树结点的结构vectorintcode[256];//存储0~255的哈夫曼编码nodesource[512];//存储哈夫曼树（忽略零下标）vectorintcodes;//存储整个待编（解）码文件的哈夫曼编码序列vectorintchecks;//解码时记录当前的匹配boolencrypt;//压（解）码的标记chartemp[1024];//write缓冲区fileInfofileIn;//输入文件路径fileInfofileOut;//输出文件名intfindName(char*a){inti;for(i=0;i!=200;++i)if(!a[i])break;for(intj=i;j!=0;--j)if(a[j]=='\\')returnj;}intcheck(intindex){//解码时的匹配解码过程for(inti=0;i!=checks.size();++i){if(code[checks[i]][index]!=codes[index]){checks.erase(i+checks.begin());--i;}}if(checks.size()==1){if(index+1code[checks[0]].size())codes.erase(0+codes.begin(),code[checks[0]].size()-index-1+codes.begin());returnchecks[0];}return256;}voidadd(intk,ofstream&out){if(!encrypt){intcount=0;intretur;intm=0;for(inti=0;i!=8;++i)//依次取出字节的八位至codes中if((1(8-i-1))&k)codes.push_back(1);elsecodes.push_back(0);if(codes.size()=1024*2){checks.clear();for(intj=0;j!=256;++j)checks.push_back(j);for(inti=0;i!=1024;++i){if((retur=check(m++))!=256){checks.clear();for(intj=0;j!=256;++j)checks.push_back(j);temp[count++]=retur;codes.erase(0+codes.begin(),m+codes.begin());m=0;}}out.write((char*)&temp,count);}}else{chartemp[1024];for(inti=0;i!=code[k].size();++i)codes.push_back(code[k][i]);if(codes.size()=1024*8){for(inti=0;i!=1024;++i){temp[i]=0;for(intj=0;j!=8;++j)//依次写入字节的八位至codes中{temp[i]=1;if(codes[i*8+j])temp[i]|=1;}}codes.erase(0+codes.begin(),1024*8+codes.begin());out.write(temp,1024);}}}voidcreateCode(){//根据哈夫曼树生成0~255的哈夫曼编码intk;for(inti=0;i!=256;++i){k=i+1;while(source[k].parent){code[i].insert(0+code[i].begin(),k==source[source[k].parent].lchild?0:1);k=source[k].parent;}}if(!encrypt){intexcrescent;localeloc=locale::global(locale());ofstreamout(fileOut.name,ios_base::out|ios_base::binary);locale::global(loc);loc=locale::global(locale());ifstreamin(fileIn.name,ios_base::in|ios_base::binary);locale::global(loc);in.seekg(-4,fstream::end);in.read((char*)&excrescent,sizeof(int));//读取该压缩文件的末端添补位数（由压缩时写入）in.seekg(sizeof(__int64)*257+200);charkk;in.read(&kk,1);while(!in.eof()){add(255&kk,out);in.read(&kk,1);}codes.erase(codes.size()-excrescent-sizeof(int)*8+codes.begin(),codes.size()+codes.begin());//忽略压缩文件的末端添补位数excrescent=codes.size();intm=0;chartemp[3024];intcount=0;intretur;for(inti=0;i!=excrescent;++i){if((retur=check(m++))!=256){checks.clear();for(intj=0;j!=256;++j)checks.push_back(j);temp[count++]=retur;codes.erase(0+codes.begin(),m+codes.begin());m=0;}}out.write((char*)&temp,count);out.flush();out.close();}else{localeloc=locale::global(locale());ofstreamout(fileOut.name,ios_base::out|ios_base::binary);locale::global(loc);charname[200];strcpy(name,fileIn.name+findName(fileIn.name)+1);out.write(name,200);//写入文件信息loc=locale::global(locale());ifstreamin(fileIn.name,ios_base::in|ios_base::binary);locale::global(loc);for(inti=0;i!=257;++i)//将所建哈夫曼树各结点权值信息写入压缩文件中为解压提供必要信息out.write((char*)&source[i].percent,sizeof(__int64));charkk;in.read(&kk,1);while(!in.eof()){add(255&kk,out);in.read(&kk,1);}while(codes.size()7){kk=0;inti;for(i=0;i!=8;++i){kk=1;if(codes[i])kk|=1;}codes.erase(0+codes.begin(),8+codes.begin());out.write(&kk,1);}k=8-codes.size();//记录末端添补的位数kk=0;while(codes.size())//末端补齐一个字节即八位{kk=1;if(codes[0])kk|=1;codes.erase(0+codes.begin());}out.write(&kk,1);if(k!=8)out.write((char*)&k,sizeof(int));//将末端添补的位数写入压缩文件中为解压提供必要的信息out.flush();out.close();out.clear();}}voidfindMin(int*a,int*b,inti){//查找两个权值最小的结点生成一个新的结点*a=*b=0;for(intj=1;j!=i;++j){if(source[j].parent)continue;elseif(*a==0)*a=j;elseif(*b==0){if(source[j].percentsource[*a].percent){*b=*a;*a=j;}else*b=j;}elseif(source[j].percentsource[*a].percent){*b=*a;*a=j;}elseif(source[j].percentsource[*b].percent){*b=j;}}}voidcreateSource(){//根据0~255在待压缩文件中出现的概率构建最优二叉树（哈夫曼树）intk=0;intmin1,min2;for(inti=257;i!=512;++i){findMin(&min1,&min2,i);source[min1].parent=source[min2].parent=i;source[i].lchild=min1;source[i].rchild=min2;source[i].percent=source[min1].percent+source[min2].percent;}}intmain(void){intkk=3;encrypt=false;while(kk!=1&&kk!=2){printf(请选择你要进行的操作：\n1、编码\n2、解码\n);scanf(%d,&kk);if(kk==1)encrypt=true;}if(!encrypt){printf(请输入要解码的文件：\n);scanf(%s,fileIn.name);__int64temp[257];chartem[200];strcpy(tem,fileIn.name);tem[findName(tem)+1]='\0';localeloc=locale::global(locale());ifstreamin(fileIn.name,ios_base::in|ios_base::binary);locale::global(loc);in.read((char*)fileOut.name,200);//读取原文件信息strcat(tem,fileOut.name);strcpy(fileOut.name,tem);in.read((char*)&temp,257*sizeof(__int64));//读取该压缩文件的必要信息以构建最优二叉树（由压缩时写入）for(inti=1;i!=257;++i)source[i].percent=temp[i];in.close();in.clear();createSource();//构建最优二叉树createCode();//生成0~255的哈夫曼编码return0;}chark;printf(请输入要编码的文件：\n);scanf(%s,fileIn.name);chartem[200];printf(请输入压缩后的文件名：\n);scanf(%s,fileOut.name);strcpy(tem,fileIn.name);tem[findName(tem)+1]='\0';strcat(tem,fileOut.name);strcat(tem,.hfm