数据结构课程设计文本压缩

1、 数据结构课程设计报告 实验二：文本文件压缩一、设计要求1、问题描述：根据huffman编码以及二叉树的相关知识实现文本文件的压缩（即将输入的字符串转换为二进制编码）和解压（即将二进制编码转换为字符串）2、输入：文本文件（压缩文件）。3、 输出：压缩文件（文本文件）。 知识点：堆、霍夫曼树、二叉树遍历实际输入输出情况：源文件为文本文件，内容如下：输出的文件是以.zl0010为扩展名的二进制文件，将其用记事本以文本方式打开得到如下文件：解压过程如下：解压获得的文件比较发现源文件与解压缩后文件内容相同。1、 数据结构与算法描述1. 对输入文件的处理创建文件输入流，将源文本文件以二进制方式打开，建立

2、保存每个Byte频率的数组count256，并通过对文件的第一次遍历，完成对Byte频率的统计。其中bytecount变量记录输入的字节数，关键代码如下：string filename;/文件名int count256;/每个字符的频率for(int i=0;i256;i+)counti=0;std:ifstream ifs;/输入流std:cout请输入需要压缩的文件路径filename;ifs.open(filename,std:ifstream:binary);if(!ifs)std:cout文件打开错误std:endl;system(pause);exit(0);char buf;in

3、t bytecount=0;/计算总共输入了多少字节std:cout正在计算频率std:endl;while(!ifs.eof()ifs.read(char*)&buf,1);/*buf+=128;countbuf+;*/if(ifs.eof()break;count(int)buf+128+;bytecount+;/*std:cout(int)bufstd:endl;*/2. 哈夫曼树的建立及编码过程以第一步中统计的Byte出现频率为每个树节点的权值，进行哈夫曼树的构建，并通过构建的哈夫曼树，获取std:string类型的哈夫曼编码。关键代码如下：std:cout正在编码std:endl;B

4、Tree tree=HuffmanTree(count,256);string* codes;/保存的是每个字符的编码codes=Getcode(count,256,tree);其中HuffmanTree方法得到以count数组为权值的哈夫曼树，Getcode方法返回的是std:string类的数组，这种编码需要后面进一步处理输出二进制文件。3. 输出压缩文件过程该过程的思路如下：将哈夫曼编码每8位作为一个新的字符，将该字符的ASCII码输出到二进制文件中。由于在源文件中得到的Bytes是-128到127之间的值，需要建立该域与数组索引0到255间的映射。将得到的字符串形式的编码进行转换，成为

5、对应该编码的二进制串，因为二进制串在C+语言中无法直接输出，所以先将其转换为Int型，再转为char型进行二进制输出。以下为该过程的代码：int bstringtoint(const string& str)if(str.size()!=8)std:cout转码错误std:endl;exit(0);int result=0;for(int i=0;i=8)intbuf=bstringtoint(outbuf.substr(0,8)-128;ofs.write(char*)&intbuf,1);outbuf.erase(0,8);byteoutcount+;还要考虑的一个问题是最后的一个byte

6、可能不到8位，我在这里用0补全8位进行最后一位的输出，关键代码如下：if(!outbuf.empty()outbuf.append(8-outbuf.size(),0);intbuf=bstringtoint(outbuf)-128;ofs.write(char*)&intbuf,1);byteoutcount+;如果仅考虑压缩，该过程到此结束。而为了进行解压缩，我们必须要在压缩文件中保存字典，在这里我的思路是将计算好的字符频率保存在文件中，而在解压缩时利用他们重新构建哈夫曼树，关键代码如下：for(int i=0;i256;i+)ofs.write(char*)&counti,sizeof(

7、int);/输出字符出现频率,即字典ofs.write(char*)&bytecount,sizeof(int);/输出原文件字节数目，方便解压时使用这样整个压缩过程就结束了4. 解压缩过程解压缩过程中利用.zl0010文件中的byte频率重建哈夫曼树，该过程除频率的获取过程外与压缩时相同，关键代码如下：std:cout读取数据std:endl;for(int i=0;i256;i+)ifs.read(char*)&counti,sizeof(int);tree=HuffmanTree(count,256);然后获取压缩时输出的字节数，并保存在bytecount变量中，代码如下：ifs.rea

8、d(char*)&bytecount,sizeof(int);与压缩过程对应，解压缩时需要将获取的byte转换为string的编码，并且利用指针对哈夫曼树进行追踪，逐步输出整篇被压缩文本。主要代码如下：while(!ifs.eof()ifs.read(char*)&buf,1);if(ifs.eof()break;outbuf=inttobstring(int)buf+128);/std:coutoutbufgetleft();else p=p-getright();if (p-getdata()!=-1)bufdata=p-getdata()-128;/std:coutgetdata()da

9、ta=data;this-left=left;this-right=right;文件三：BTree.h#pragma once#include treeNode.h#include#includeclass BTreefriend class Huffman;friend std:string* Getcode(int a,int n,const BTree& HTree);friend int main();private:treeNode* root;public:BTree();void MakeTree(const int& data,BTree& left,BTree& right)

10、;/BTree HuffmanTree(int a,int n);class Huffmanfriend class BTree;friend BTree HuffmanTree(int,int);private:BTree tree;int weight;public:bool operatorweight)(H.weight);文件四：BTree.cpp(压缩)/coded by cs3_zhanglin/压缩器和解压缩器写在了不同的cpp文件中/两个程序公用treeNode.cpp treeNode.h BTree.h三个文件/这是压缩器#include BTree.h#include#

11、include#includeusing std:string;BTree:BTree()this-root=0;void BTree:MakeTree(const int& data,BTree& left,BTree& right)this-root=new treeNode(data,left.root,right.root);left.root=right.root=0;BTree HuffmanTree(int a,int n)Huffman* w=new Huffmann;BTree z,zero;for(int i=0;in;i+)z.MakeTree(i,zero,zero);

12、wi.weight=ai;wi.tree=z;std:priority_queue pq;for(int i=0;igetdata()=goal)return true;if(findcode(goal,HTree-getleft(),result)result.insert(0,0);return true;if(findcode(goal,HTree-getright(),result)result.insert(0,1);return true;return false;string* Getcode(int a,int n,const BTree& HTree)string* code

13、=new stringn;for(int i=0;in;i+)codei=;for(int i=0;in;i+)if(ai!=0)findcode(i,HTree.root,codei);return code;int bstringtoint(const string& str)if(str.size()!=8)std:cout转码错误std:endl;exit(0);int result=0;for(int i=0;i8;i+)result+=(stri-0)*pow(2,7-i);return result;string inttobstring(int codeint)string s

14、tr;while(codeint!=0)if(codeint%2=1)str=str.insert(0,1);elsestr=str.insert(0,0);codeint=codeint/2;if(str.size()!=8)str.insert(0,8-str.size(),0);return str;int main()/压缩器string filename;/文件名int count256;/每个字符的频率for(int i=0;i256;i+)counti=0;std:ifstream ifs;/输入流std:cout请输入需要压缩的文件路径filename;ifs.open(fil

15、ename,std:ifstream:binary);if(!ifs)std:cout文件打开错误std:endl;system(pause);exit(0);char buf;int bytecount=0;/计算总共输入了多少字节std:cout正在计算频率std:endl;while(!ifs.eof()ifs.read(char*)&buf,1);/*buf+=128;countbuf+;*/if(ifs.eof()break;count(int)buf+128+;bytecount+;/*std:cout(int)bufstd:endl;*/for(int i=0;i256;i+)/

16、std:couti:countistd:endl;/std:cout正在编码std:endl;BTree tree=HuffmanTree(count,256);string* codes;/保存的是每个字符的编码codes=Getcode(count,256,tree);/*for(int i=0;i256;i+)std:couti:codesistd:endl;*/std:cout正在压缩std:endl;std:ofstream ofs;/输出流ifs.clear();ofs.open(filename+.zl0010,std:ofstream:out|std:ofstream:bina

17、ry);for(int i=0;i=8)intbuf=bstringtoint(outbuf.substr(0,8)-128;ofs.write(char*)&intbuf,1);outbuf.erase(0,8);byteoutcount+;if(!outbuf.empty()outbuf.append(8-outbuf.size(),0);intbuf=bstringtoint(outbuf)-128;ofs.write(char*)&intbuf,1);byteoutcount+;std:cout输入bytecount个字节，输出byteoutcount个字节std:endl;doubl

18、e yasuolv=byteoutcount/(double)bytecount;std:cout压缩成功,压缩率是yasuolv*100%std:endl;system(pause);文件五：BTree.cpp(解压缩)#include BTree.h#include#include#includeusing std:string;BTree:BTree()this-root=0;void BTree:MakeTree(const int& data,BTree& left,BTree& right)this-root=new treeNode(data,left.root,right.ro

19、ot);left.root=right.root=0;BTree HuffmanTree(int a,int n)Huffman* w=new Huffmann;BTree z,zero;for(int i=0;in;i+)z.MakeTree(i,zero,zero);wi.weight=ai;wi.tree=z;std:priority_queue pq;for(int i=0;igetdata()=goal)return true;if(findcode(goal,HTree-getleft(),result)result.insert(0,0);return true;if(findc

20、ode(goal,HTree-getright(),result)result.insert(0,1);return true;return false;string* Getcode(int a,int n,const BTree& HTree)string* code=new stringn;for(int i=0;in;i+)codei=;for(int i=0;in;i+)if(ai!=0)findcode(i,HTree.root,codei);return code;int bstringtoint(const string& str)if(str.size()!=8)std:co

21、ut转码错误std:endl;exit(0);int result=0;for(int i=0;i8;i+)result+=(stri-0)*pow(2,7-i);return result;string inttobstring(int codeint)string str;while(codeint!=0)if(codeint%2=1)str=str.insert(0,1);elsestr=str.insert(0,0);codeint=codeint/2;if(str.size()!=8)str.insert(0,8-str.size(),0);return str;int main()int count256;int bytecount;char buf;std:ifstream ifs;std:ofstream ofs;string filename;BTree tree;string outbuf;std:cout请输入解压文件路径：filename;ifs.ope