數(shù)據(jù)結(jié)構(gòu)哈夫曼樹編碼譯碼實(shí)驗(yàn)報(bào)告

1、WORD格式【詳細(xì)設(shè)計(jì)】具體代碼實(shí)現(xiàn)如下：專業(yè)資料整理WORD格式/HaffmanTree.h#include<iostream>#include<fstream>#include<string>struct HuffmanNode /int weight;int parent;int lchild,rchild;哈夫曼樹的一個(gè)結(jié)點(diǎn)專業(yè)資料整理WORD格式class HuffmanTree /哈夫曼樹private:HuffmanNode *Node; /Node存放哈夫曼樹char *Info;/Info存放源文用到的字符源碼，如'a',&

2、#39;b','c','d','e'，此內(nèi)專業(yè)資料整理WORD格式容可以放入結(jié)點(diǎn)中，不單獨(dú)設(shè)數(shù)組存放int LeafNum;/哈夫曼樹的葉子個(gè)數(shù)，也是源碼個(gè)數(shù)public:HuffmanTree();HuffmanTree();void CreateHuffmanTree(); /*在內(nèi)存中建立哈夫曼樹，存放在Node 中。讓用戶從兩種建立哈夫曼樹的方法中選擇：1. 從鍵盤讀入源碼字符集個(gè)數(shù)，每個(gè)字符， 和每個(gè)字符的權(quán)重，建立哈夫曼樹，并將哈夫曼樹寫入文件hfmTree 中。2. 從文件 hfmTree 中讀入哈夫曼樹信息，建立哈夫曼樹*

3、/void CreateHuffmanTreeFromKeyboard();void CreateHuffmanTreeFromFile();專業(yè)資料整理WORD格式void Encoder();/*使用建立好的哈夫曼樹如果不在內(nèi)存，那么從文件并建立內(nèi)存里的哈夫曼樹，對(duì)文件 ToBeTran 中的正文進(jìn)展編碼， 并將碼文寫入文件hfmTree 中讀入CodeFile中。專業(yè)資料整理WORD格式voidDecoder();/*ToBeTran的內(nèi)容可以用記事本等程序編輯產(chǎn)生。*/待譯碼的碼文存放在文件CodeFile中，使用建立好的哈夫曼樹如專業(yè)資料整理WORD格式果不在內(nèi)存，那么從文件hfmT

4、ree 中讀入并建立內(nèi)存里的哈夫曼樹將碼文譯碼，得到的源文寫入文件TextFile中，并同時(shí)輸出到屏幕上。*/專業(yè)資料整理WORD格式void PrintCodeFile();/*將碼文文件CodeFile顯示在屏幕上 */void PrintHuffmanTree(); /*將哈夫曼樹以直觀的形式凹入表示法，或廣義表，或其他樹形表示法顯示在屏幕上，專業(yè)資料整理WORD格式同時(shí)寫入文件TreePrintFile中 */專業(yè)資料整理WORD格式voidPrintHuffmanTree_aoru(int T,int layer=1);PrintHuffmanTree()調(diào)用 */;/*凹入表示法顯

5、示哈夫曼樹，由專業(yè)資料整理WORD格式/HuffmanTree.cpp#include<string>#include<limits> /為使用整型最大值專業(yè)資料整理WORD格式#include"HuffmanTree.h"using namespace std;/*HuffmanTree:HuffmanTree()Node=NULL;/*HuffmanTree:HuffmanTree()deleteNode;/*void HuffmanTree:CreateHuffmanTree()專業(yè)資料整理WORD格式char Choose;cout<&

6、lt;" 你要從文件中讀入哈夫曼樹( 按 1) ，還是從鍵盤輸入哈夫曼樹cin>>Choose;if(Choose='2') /鍵盤輸入建立哈夫曼樹CreateHuffmanTreeFromKeyboard();/choose='2'( 按2)？"專業(yè)資料整理WORD格式else /從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹專業(yè)資料整理WORD格式CreateHuffmanTreeFromFile();/*void HuffmanTree:CreateHuffmanTreeFromKeyboard()int Nu

7、m;cout<<"n請(qǐng)輸入源碼字符集個(gè)數(shù)："cin>>Num;if (Num<=1)專業(yè)資料整理WORD格式cout<<"無法建立少于2 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹。nn"專業(yè)資料整理WORD格式return;專業(yè)資料整理WORD格式LeafNum=Num;Node=new HuffmanNode2*Num-1;Info=new char2*Num-1;for(int i=0;i<Num;i+) /讀入哈夫曼樹的葉子結(jié)點(diǎn)信息cout<<" 請(qǐng)輸入第 "<<i+1<

8、<" 個(gè)字符值 "getchar();Infoi=getchar(); /源文的字符存入字符數(shù)組Infogetchar();專業(yè)資料整理WORD格式cout<<" 請(qǐng)輸入該字符的權(quán)值或頻度"cin>>Nodei.weight; /源文的字符權(quán)重存入Nodei.parent=-1;Nodei.lchild=-1;Node.weight專業(yè)資料整理WORD格式Nodei.rchild=-1;for(i=Num;i<2*Num-1;i+)/循環(huán)建立哈夫曼樹內(nèi)部結(jié)點(diǎn)int pos1=-1,pos2=-1;int max1=32

9、767,max2=32767;for(int j=0;j<i;j+)/在根節(jié)點(diǎn)中選出權(quán)值最小的兩個(gè)if(Nodej.parent=-1)/是否為根結(jié)點(diǎn)if(Nodej.weight<max1)max2=max1;max1=Nodej.weight;pos2=pos1;pos1=j;elseif(Nodej.weight<max2)max2=Nodej.weight;pos2=j;Nodepos1.parent=i;Nodepos2.parent=i;Nodei.lchild=pos1;Nodei.rchild=pos2;Nodei.parent=-1;Nodei.weight

10、=Nodepos1.weight+Nodepos2.weight; /forcout<<" 哈夫曼樹已成功構(gòu)造完成。n"專業(yè)資料整理WORD格式/ 把建立好的哈夫曼樹寫入文件hfmTree.datchar ch;cout<<" 是否要替換原來的哈夫曼樹文件(Y/N):"cin>>ch;if (ch!='y'&&ch!='Y') return;elseofstream fop;fop.open("hfmTree.dat",ios:out|ios:bina

11、ry|ios:trunc); / 翻開文件 if(fop.fail()cout<<"n哈夫曼樹文件翻開失敗，無法將哈夫曼樹寫入hfmTree.dat文件。 n"return;專業(yè)資料整理WORD格式fop.write(char*)&Num,sizeof(Num); /for(i=0;i<Num;i+)先寫入哈夫曼樹的葉子結(jié)點(diǎn)個(gè)數(shù)專業(yè)資料整理WORD格式 /再寫入源文字符集的所有字符存儲(chǔ)在Info中專業(yè)資料整理WORD格式fop.write(char*)&Infoi,sizeof(Infoi);flush(cout);for(i=0;i<

12、;2*Num-1;i+)專業(yè)資料整理WORD格式 /最后寫入哈夫曼樹的各個(gè)結(jié)點(diǎn)存儲(chǔ)在Node中專業(yè)資料整理WORD格式fop.write(char*)&Nodei,sizeof(Nodei);flush(cout);專業(yè)資料整理WORD格式fop.close(); /關(guān)閉文件cout<<"n哈夫曼樹已成功寫入hfmTree.dat文件。 n"專業(yè)資料整理WORD格式/*void HuffmanTree:CreateHuffmanTreeFromFile()ifstream fip;fip.open("hfmTree.dat",ios:

13、binary|ios:in);if(fip.fail()cout<<" 哈夫曼樹文件 hfmTree.dat 翻開失敗，無法建立哈夫曼樹。 n" return;fip.read(char*)&LeafNum,sizeof(LeafNum);if (LeafNum<=1)專業(yè)資料整理WORD格式cout<<" 哈夫曼樹文件中的數(shù)據(jù)有誤，葉子結(jié)點(diǎn)個(gè)數(shù)少于2 個(gè)，無法建立哈夫曼樹。n"fip.close();return;Info=new charLeafNum;Node=new HuffmanNode2*LeafNum-

14、1;for(int i=0;i<LeafNum;i+)fip.read(char*)&Infoi,sizeof(Infoi);for(i=0;i<2*LeafNum-1;i+)fip.read(char*)&Nodei,sizeof(Nodei);fip.close();cout<<" 哈夫曼樹已成功構(gòu)造完成。n"/*void HuffmanTree:Encoder()if(Node=NULL)/內(nèi)存沒有哈夫曼樹，那么從哈夫曼樹文件 hfmTree.dat 中讀入信息并建立哈夫曼樹 CreateHuffmanTreeFromFile(

15、);if (LeafNum<=1)cout<<" 內(nèi)存無哈夫曼樹。操作撤銷。nn"return;/if專業(yè)資料整理WORD格式char *SourceText; /字符串?dāng)?shù)組，用于存放源文專業(yè)資料整理WORD格式/ 讓用戶選擇源文是從鍵盤輸入，還是從源文文件ToBeTran.txt中讀入專業(yè)資料整理WORD格式char Choose;專業(yè)資料整理WORD格式cout<<" 你要從文件中讀入源文( 按 1) ，還是從鍵盤輸入源文( 按 2) ？ "cin>>Choose;if(Choose='1')

16、ifstream fip1("ToBeTran.txt");if(fip1.fail()cout<<" 源文文件翻開失敗! 無法繼續(xù)執(zhí)行。n"return;char ch;int k=0;專業(yè)資料整理WORD格式while(fip1.get(ch) k+; /第一次讀文件只統(tǒng)計(jì)文件中有多少個(gè)字符，將字符數(shù)存入 kfip1.close();專業(yè)資料整理WORD格式SourceText=new chark+1; / ifstream fip2("ToBeTran.txt");/申請(qǐng)存放源文的字符數(shù)組空間第二次讀源文文件， 把內(nèi)

17、容寫入SourceText專業(yè)資料整理WORD格式k=0;while(fip2.get(ch) SourceTextk+=ch;fip2.close();SourceTextk='0'cout<<" 需編碼的源文為："cout<<SourceText<<endl;else / 從鍵盤輸入源文 string SourceBuff;cin.ignore();cout<<" 請(qǐng)輸入需要編碼的源文( 可輸入任意長，按回車鍵完畢):n"getline(cin,SourceBuff,'n'

18、;);int k=0;while(SourceBuffk!='0')k+;SourceText=new chark+1;k=0;while(SourceBuffk!='0')SourceTextk=SourceBuffk;k+;SourceTextk='0'cout<<" 覆蓋已有的編碼原文件" Y/N "char ch;cin>>ch;if(ch='y'|ch='Y')ofstream fip2;fip2.open("ToBeTran.txt&quo

19、t;);if(!fip2)cerr<<" 文件翻開失?。?quot;<<endl;abort();fip2<<SourceText<<endl;fip2.close();專業(yè)資料整理WORD格式cout<<" 需編碼的源文已寫入ToBeTran.txt中 "<<endl;/ 開場編碼ofstream fop("CodeFile.dat",ios:trunc); /翻開碼文存放文件char *code;專業(yè)資料整理WORD格式code=new charLeafNum;/存放一

20、個(gè)源文字符的編碼專業(yè)資料整理WORD格式int k=0;while(SourceTextk!='0')/源文串中從第一個(gè)字符開場逐個(gè)編碼int star=0;char ch=SourceTextk;for(int i=0;i<LeafNum;i+)if(Infoi=ch)/求出該文字所在的單元編號(hào)break;int j=i;while(Nodej.parent!=-1)j=Nodej.parent;if(InfoNodej.lchild=Infoi) codestar+='0'else codestar+='1'i=j;codestar=&

21、#39;0'for(i=0;i<star/2;i+)int j=codei;codei=codestar-i-1;codestar-i-1=j;i=0; /將源文的當(dāng)前字符的對(duì)應(yīng)編碼寫入碼文文件while(codei!='0')fop<<codei;i+;k+; /源文串中的字符后移一個(gè)fop.close();cout<<" 已完成編碼，碼文已寫入文件CodeFile.dat中。 nn"專業(yè)資料整理WORD格式/*void HuffmanTree:Decoder()/ 如果內(nèi)存沒有哈夫曼樹， 那么從哈夫曼樹文件 hfmT

22、ree.dat 中讀入信息并建立哈夫曼樹if(Node=NULL)CreateHuffmanTreeFromFile();if (LeafNum<=1)cout<<" 內(nèi)存無哈夫曼樹。操作撤銷。nn"return;/ 將碼文從文件 CodeFile.dat 中讀入 CodeStr ifstream fip1("CodeFile.dat");if(fip1.fail()cout<<" 沒有碼文，無法譯碼。 n" return;char* CodeStr;int k=0;char ch;while(fip1.

23、get(ch)k+;fip1.close();CodeStr=new chark+1;ifstream fip2("CodeFile.dat");k=0;while(fip2.get(ch) CodeStrk+=ch;fip2.close();CodeStrk='0'cout<<" 經(jīng)譯碼得到的源文為："ofstream fop("TextFile.dat");專業(yè)資料整理WORD格式int j=LeafNum*2-1-1; /j指向哈夫曼樹的根專業(yè)資料整理WORD格式inti=0; /碼文從第一個(gè)符號(hào)開場

24、，順著哈夫曼樹由根下行，按碼文的當(dāng)前符號(hào)決定下行到左孩子還是右孩子while(CodeStri!='0') / 下行到哈夫曼樹的葉子結(jié)點(diǎn)處，那么譯出葉子結(jié)點(diǎn)對(duì)應(yīng)的源文字符 if(CodeStri='0') j=Nodej.lchild;else j=Nodej.rchild;if(Nodej.rchild=-1)cout<<Infoj;fop<<Infoj;j=LeafNum*2-1-1;i+;fop.close();cout<<"n譯碼成功且已存到文件TextFile.dat中。 nn"/*void Hu

25、ffmanTree:PrintCodeFile()char ch;int i=1;ifstream fip("CodeFile.dat");ofstream fop("CodePrin.dat");if(fip.fail()cout<<" 沒有碼文文件，無法顯示碼文文件內(nèi)容。n"return;while(fip.get(ch)cout<<ch;fop<<ch;if(i=50)cout<<endl;fop<<endl;i=0;i+;cout<<endl;專業(yè)資料整理

26、WORD格式fop<<endl;fip.close();fop.close();/*void HuffmanTree:PrintHuffmanTree()/ 如果內(nèi)存沒有哈夫曼樹， 那么從哈夫曼樹文件 hfmTree.dat 中讀入信息并建立哈夫曼樹if(Node=NULL)CreateHuffmanTreeFromFile();if (LeafNum<=1)cout<<" 內(nèi)存無哈夫曼樹。操作撤銷。nn"return;ofstream fop("TreePrint.dat",ios_base:trunc);fop.clos

27、e();PrintHuffmanTree_aoru(2*LeafNum-1-1,0);return;/*void HuffmanTree:PrintHuffmanTree_aoru(int T,int layer)for(int i=0;i<layer;i+) cout<<"_"cout<<NodeT.weight<<endl;if(NodeT.lchild!=-1) PrintHuffmanTree_aoru(NodeT.lchild,+layer);if(NodeT.rchild!=-1) PrintHuffmanTree_ao

28、ru(NodeT.rchild,layer-);/main.cpp#include<string.h>#include<stdlib.h>using namespace std;int main()HuffmanTree huftree;char Choose;while(1)專業(yè)資料整理WORD格式cout<<"nn*歡迎使用哈夫曼編碼/譯碼系統(tǒng)*"<<endl;cout<<" 您可以進(jìn)展以下操作 :"<<endl;cout<<"1建立哈夫曼樹3譯碼 ( 碼文已在文件CodeFile 中 )5顯示哈夫曼樹 "<<endl;cout<<"2編碼 ( 源文已在文件ToBeTran 中，或鍵盤輸入 )4顯示碼文6退出&quo