數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)文本壓縮

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 實(shí)驗(yàn)二：文本文件壓縮一、設(shè)計(jì)要求1、問題描述：根據(jù)huffman編碼以及二叉樹的相關(guān)知識(shí)實(shí)現(xiàn)文本文件的壓縮（即將輸入的字符串轉(zhuǎn)換為二進(jìn)制編碼）和解壓（即將二進(jìn)制編碼轉(zhuǎn)換為字符串）2、輸入：文本文件（壓縮文件）。3、 輸出：壓縮文件（文本文件）。 知識(shí)點(diǎn)：堆、霍夫曼樹、二叉樹遍歷實(shí)際輸入輸出情況：源文件為文本文件，內(nèi)容如下：輸出的文件是以.zl0010為擴(kuò)展名的二進(jìn)制文件，將其用記事本以文本方式打開得到如下文件：解壓過程如下：解壓獲得的文件比較發(fā)現(xiàn)源文件與解壓縮后文件內(nèi)容相同。1、 數(shù)據(jù)結(jié)構(gòu)與算法描述1. 對(duì)輸入文件的處理創(chuàng)建文件輸入流，將源文本文件以二進(jìn)制方式打開，建立

2、保存每個(gè)Byte頻率的數(shù)組count256，并通過對(duì)文件的第一次遍歷，完成對(duì)Byte頻率的統(tǒng)計(jì)。其中bytecount變量記錄輸入的字節(jié)數(shù)，關(guān)鍵代碼如下：string filename;/文件名int count256;/每個(gè)字符的頻率for(int i=0;i256;i+)counti=0;std:ifstream ifs;/輸入流std:cout請(qǐng)輸入需要壓縮的文件路徑filename;ifs.open(filename,std:ifstream:binary);if(!ifs)std:cout文件打開錯(cuò)誤std:endl;system(pause);exit(0);char buf;in

3、t bytecount=0;/計(jì)算總共輸入了多少字節(jié)std:cout正在計(jì)算頻率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. 哈夫曼樹的建立及編碼過程以第一步中統(tǒng)計(jì)的Byte出現(xiàn)頻率為每個(gè)樹節(jié)點(diǎn)的權(quán)值，進(jìn)行哈夫曼樹的構(gòu)建，并通過構(gòu)建的哈夫曼樹，獲取std:string類型的哈夫曼編碼。關(guān)鍵代碼如下：std:cout正在編碼std:endl;B

4、Tree tree=HuffmanTree(count,256);string* codes;/保存的是每個(gè)字符的編碼codes=Getcode(count,256,tree);其中HuffmanTree方法得到以count數(shù)組為權(quán)值的哈夫曼樹，Getcode方法返回的是std:string類的數(shù)組，這種編碼需要后面進(jìn)一步處理輸出二進(jìn)制文件。3. 輸出壓縮文件過程該過程的思路如下：將哈夫曼編碼每8位作為一個(gè)新的字符，將該字符的ASCII碼輸出到二進(jìn)制文件中。由于在源文件中得到的Bytes是-128到127之間的值，需要建立該域與數(shù)組索引0到255間的映射。將得到的字符串形式的編碼進(jìn)行轉(zhuǎn)換，成為

5、對(duì)應(yīng)該編碼的二進(jìn)制串，因?yàn)槎M(jìn)制串在C+語言中無法直接輸出，所以先將其轉(zhuǎn)換為Int型，再轉(zhuǎn)為char型進(jìn)行二進(jìn)制輸出。以下為該過程的代碼：int bstringtoint(const string& str)if(str.size()!=8)std:cout轉(zhuǎn)碼錯(cuò)誤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+;還要考慮的一個(gè)問題是最后的一個(gè)byte

6、可能不到8位，我在這里用0補(bǔ)全8位進(jìn)行最后一位的輸出，關(guān)鍵代碼如下：if(!outbuf.empty()outbuf.append(8-outbuf.size(),0);intbuf=bstringtoint(outbuf)-128;ofs.write(char*)&intbuf,1);byteoutcount+;如果僅考慮壓縮，該過程到此結(jié)束。而為了進(jìn)行解壓縮，我們必須要在壓縮文件中保存字典，在這里我的思路是將計(jì)算好的字符頻率保存在文件中，而在解壓縮時(shí)利用他們重新構(gòu)建哈夫曼樹，關(guān)鍵代碼如下：for(int i=0;i256;i+)ofs.write(char*)&counti,sizeof(

7、int);/輸出字符出現(xiàn)頻率,即字典ofs.write(char*)&bytecount,sizeof(int);/輸出原文件字節(jié)數(shù)目，方便解壓時(shí)使用這樣整個(gè)壓縮過程就結(jié)束了4. 解壓縮過程解壓縮過程中利用.zl0010文件中的byte頻率重建哈夫曼樹，該過程除頻率的獲取過程外與壓縮時(shí)相同，關(guān)鍵代碼如下：std:cout讀取數(shù)據(jù)std:endl;for(int i=0;i256;i+)ifs.read(char*)&counti,sizeof(int);tree=HuffmanTree(count,256);然后獲取壓縮時(shí)輸出的字節(jié)數(shù)，并保存在bytecount變量中，代碼如下：ifs.rea

8、d(char*)&bytecount,sizeof(int);與壓縮過程對(duì)應(yīng)，解壓縮時(shí)需要將獲取的byte轉(zhuǎn)換為string的編碼，并且利用指針對(duì)哈夫曼樹進(jìn)行追蹤，逐步輸出整篇被壓縮文本。主要代碼如下：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文件中/兩個(gè)程序公用treeNode.cpp treeNode.h BTree.h三個(gè)文件/這是壓縮器#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轉(zhuǎn)碼錯(cuò)誤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;/每個(gè)字符的頻率for(int i=0;i256;i+)counti=0;std:ifstream ifs;/輸入流std:cout請(qǐng)輸入需要壓縮的文件路徑filename;ifs.open(fil

15、ename,std:ifstream:binary);if(!ifs)std:cout文件打開錯(cuò)誤std:endl;system(pause);exit(0);char buf;int bytecount=0;/計(jì)算總共輸入了多少字節(jié)std:cout正在計(jì)算頻率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;/保存的是每個(gè)字符的編碼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個(gè)字節(jié)，輸出byteoutcount個(gè)字節(jié)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轉(zhuǎn)碼錯(cuò)誤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請(qǐng)輸入解壓文件路徑：filename;ifs.ope