《數(shù)據(jù)結(jié)構(gòu)哈夫曼樹編碼譯碼實(shí)驗(yàn)報(bào)告.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)哈夫曼樹編碼譯碼實(shí)驗(yàn)報(bào)告.doc（15頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、【詳細(xì)設(shè)計(jì)】具體代碼實(shí)現(xiàn)如下：/HaffmanTree.h#include#include#includestruct HuffmanNode /哈夫曼樹的一個(gè)結(jié)點(diǎn) int weight; int parent; int lchild,rchild; ;class HuffmanTree /哈夫曼樹 private: HuffmanNode *Node; /Node存放哈夫曼樹 char *Info; /Info存放源文用到的字符源碼，如a,b,c,d,e，此內(nèi)容可以放入結(jié)點(diǎn)中，不單獨(dú)設(shè)數(shù)組存放 int LeafNum; /哈夫曼樹的葉子個(gè)數(shù)，也是源碼個(gè)數(shù)public: HuffmanTree

2、(); HuffmanTree(); void CreateHuffmanTree(); /*在內(nèi)存中建立哈夫曼樹，存放在Node中。 讓用戶從兩種建立哈夫曼樹的方法中選擇：1.從鍵盤讀入源碼字符集個(gè)數(shù)，每個(gè)字符，和每個(gè)字符的權(quán)重，建立哈夫曼樹，并將哈夫曼樹寫入文件hfmTree中。2.從文件hfmTree中讀入哈夫曼樹信息，建立哈夫曼樹*/ void CreateHuffmanTreeFromKeyboard(); void CreateHuffmanTreeFromFile(); void Encoder(); /*使用建立好的哈夫曼樹（如果不在內(nèi)存，則從文件hfmTree中讀入并建立內(nèi)存

3、里的哈夫曼樹）， 對(duì)文件ToBeTran中的正文進(jìn)行編碼，并將碼文寫入文件CodeFile中。 ToBeTran的內(nèi)容可以用記事本等程序編輯產(chǎn)生。*/ void Decoder(); /*待譯碼的碼文存放在文件CodeFile中，使用建立好的哈夫曼樹（如果不在內(nèi)存， 則從文件hfmTree中讀入并建立內(nèi)存里的哈夫曼樹）將碼文譯碼， 得到的源文寫入文件TextFile中，并同時(shí)輸出到屏幕上。*/ void PrintCodeFile(); /*將碼文文件CodeFile顯示在屏幕上*/ void PrintHuffmanTree(); /*將哈夫曼樹以直觀的形式（凹入表示法，或廣義表，或其他樹形

4、表示法）顯示在屏幕上， 同時(shí)寫入文件TreePrintFile中*/ void PrintHuffmanTree_aoru(int T,int layer=1); /*凹入表示法顯示哈夫曼樹，由PrintHuffmanTree()調(diào)用*/;/HuffmanTree.cpp#include#include /為使用整型最大值#includeHuffmanTree.husing namespace std;/*HuffmanTree:HuffmanTree()Node=NULL;/*HuffmanTree:HuffmanTree()deleteNode;/*void HuffmanTree:Cre

5、ateHuffmanTree() char Choose; coutChoose;if(Choose=2) /鍵盤輸入建立哈夫曼樹CreateHuffmanTreeFromKeyboard();/choose=2else /從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹CreateHuffmanTreeFromFile();/*void HuffmanTree:CreateHuffmanTreeFromKeyboard()int Num;coutNum;if (Num=1)cout無(wú)法建立少于2個(gè)葉子結(jié)點(diǎn)的哈夫曼樹。nn;return;LeafNum=Num;Node=new H

6、uffmanNode2*Num-1; Info=new char2*Num-1;for(int i=0;iNum;i+) /讀入哈夫曼樹的葉子結(jié)點(diǎn)信息cout請(qǐng)輸入第i+1個(gè)字符值;getchar(); Infoi=getchar(); /源文的字符存入字符數(shù)組Info getchar();coutNodei.weight; /源文的字符權(quán)重存入Node.weight Nodei.parent=-1; Nodei.lchild=-1; Nodei.rchild=-1; for(i=Num;i2*Num-1;i+) /循環(huán)建立哈夫曼樹內(nèi)部結(jié)點(diǎn)int pos1=-1,pos2=-1;int max

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

8、odepos1.weight+Nodepos2.weight; /forcout哈夫曼樹已成功構(gòu)造完成。n;/把建立好的哈夫曼樹寫入文件hfmTree.datchar ch;coutch;if (ch!=y&ch!=Y) return;elseofstream fop; fop.open(hfmTree.dat,ios:out|ios:binary|ios:trunc); /打開文件 if(fop.fail() coutn哈夫曼樹文件打開失敗，無(wú)法將哈夫曼樹寫入hfmTree.dat文件。n; return;fop.write(char*)&Num,sizeof(Num); /先寫入哈夫曼樹的

9、葉子結(jié)點(diǎn)個(gè)數(shù)for(i=0;iNum;i+) /再寫入源文字符集的所有字符（存儲(chǔ)在Info中）fop.write(char*)&Infoi,sizeof(Infoi);flush(cout);for(i=0;i2*Num-1;i+) /最后寫入哈夫曼樹的各個(gè)結(jié)點(diǎn)（存儲(chǔ)在Node中）fop.write(char*)&Nodei,sizeof(Nodei);flush(cout);fop.close(); /關(guān)閉文件coutn哈夫曼樹已成功寫入hfmTree.dat文件。n;/*void HuffmanTree:CreateHuffmanTreeFromFile()ifstream fip; fi

10、p.open(hfmTree.dat,ios:binary|ios:in);if(fip.fail() cout哈夫曼樹文件hfmTree.dat打開失敗，無(wú)法建立哈夫曼樹。n;return; fip.read(char*)&LeafNum,sizeof(LeafNum); if (LeafNum=1) cout哈夫曼樹文件中的數(shù)據(jù)有誤，葉子結(jié)點(diǎn)個(gè)數(shù)少于2個(gè)，無(wú)法建立哈夫曼樹。n;fip.close();return; Info=new charLeafNum; Node=new HuffmanNode2*LeafNum-1;for(int i=0;iLeafNum;i+) fip.read(

11、char*)&Infoi,sizeof(Infoi);for(i=0;i2*LeafNum-1;i+) fip.read(char*)&Nodei,sizeof(Nodei);fip.close();cout哈夫曼樹已成功構(gòu)造完成。n;/*void HuffmanTree:Encoder()if(Node=NULL)/內(nèi)存沒(méi)有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹CreateHuffmanTreeFromFile();if (LeafNum=1)cout內(nèi)存無(wú)哈夫曼樹。操作撤銷。nn;return;/if char *SourceText; /字符串?dāng)?shù)組，用于

12、存放源文 /讓用戶選擇源文是從鍵盤輸入，還是從源文文件ToBeTran.txt中讀入char Choose; coutChoose;if(Choose=1)ifstream fip1(ToBeTran.txt);if(fip1.fail() cout源文文件打開失敗!無(wú)法繼續(xù)執(zhí)行。n;return; char ch;int k=0;while(fip1.get(ch) k+; /第一次讀文件只統(tǒng)計(jì)文件中有多少個(gè)字符，將字符數(shù)存入kfip1.close(); SourceText=new chark+1; /申請(qǐng)存放源文的字符數(shù)組空間ifstream fip2(ToBeTran.txt);/第二

13、次讀源文文件，把內(nèi)容寫入SourceTextk=0; while(fip2.get(ch) SourceTextk+=ch; fip2.close();SourceTextk=0; cout需編碼的源文為：;coutSourceTextendl;else /從鍵盤輸入源文string SourceBuff; cin.ignore();cout請(qǐng)輸入需要編碼的源文(可輸入任意長(zhǎng)，按回車鍵結(jié)束):n;getline(cin,SourceBuff,n); int k=0;while(SourceBuffk!=0)k+;SourceText=new chark+1;k=0;while(SourceBu

14、ffk!=0) SourceTextk=SourceBuffk;k+;SourceTextk=0;coutch;if(ch=y|ch=Y)ofstream fip2;fip2.open(ToBeTran.txt);if(!fip2)cerr文件打開失??！endl;abort();fip2SourceTextendl;fip2.close();cout需編碼的源文已寫入ToBeTran.txt中endl; /開始編碼ofstream fop(CodeFile.dat,ios:trunc); /打開碼文存放文件char *code; code=new charLeafNum; /存放一個(gè)源文字符的

15、編碼 int k=0;while(SourceTextk!=0) /源文串中從第一個(gè)字符開始逐個(gè)編碼 int star=0;char ch=SourceTextk;for(int i=0;iLeafNum;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=0;for(i=0;istar/2;i+)int j=codei;codei=codestar-

16、i-1;codestar-i-1=j; i=0; /將源文的當(dāng)前字符的對(duì)應(yīng)編碼寫入碼文文件while(codei!=0) fopcodei;i+;k+; /源文串中的字符后移一個(gè)fop.close();cout已完成編碼，碼文已寫入文件CodeFile.dat中。nn; /*void HuffmanTree:Decoder()/如果內(nèi)存沒(méi)有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹if(Node=NULL) CreateHuffmanTreeFromFile();if (LeafNum=1)cout內(nèi)存無(wú)哈夫曼樹。操作撤銷。nn;return;/將碼文從文件Cod

17、eFile.dat中讀入 CodeStrifstream fip1(CodeFile.dat); if(fip1.fail()cout沒(méi)有碼文，無(wú)法譯碼。n;return;char* CodeStr;int k=0;char ch;while(fip1.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.

18、dat); int j=LeafNum*2-1-1; /j指向哈夫曼樹的根 int i=0; /碼文從第一個(gè)符號(hào)開始，順著哈夫曼樹由根下行，按碼文的當(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)coutInfoj;fopInfoj;j=LeafNum*2-1-1;i+; fop.close(); coutn譯碼成功且已存到文件TextFile.dat中。nn;/*void H

19、uffmanTree:PrintCodeFile()char ch;int i=1;ifstream fip(CodeFile.dat); ofstream fop(CodePrin.dat); if(fip.fail()cout沒(méi)有碼文文件，無(wú)法顯示碼文文件內(nèi)容。n;return;while(fip.get(ch)coutch; fopch; if(i=50) coutendl;fopendl;i=0;i+;coutendl;fopendl;fip.close(); fop.close(); /*void HuffmanTree:PrintHuffmanTree()/如果內(nèi)存沒(méi)有哈夫曼樹，則

20、從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹if(Node=NULL) CreateHuffmanTreeFromFile();if (LeafNum=1) cout內(nèi)存無(wú)哈夫曼樹。操作撤銷。nn;return;ofstream fop(TreePrint.dat,ios_base:trunc);fop.close();PrintHuffmanTree_aoru(2*LeafNum-1-1,0);return;/*void HuffmanTree:PrintHuffmanTree_aoru(int T,int layer)for(int i=0;ilayer;i+) cout_

21、;coutNodeT.weightendl;if(NodeT.lchild!=-1) PrintHuffmanTree_aoru(NodeT.lchild,+layer);if(NodeT.rchild!=-1) PrintHuffmanTree_aoru(NodeT.rchild,layer-);/main.cpp#include#includeusing namespace std;int main()HuffmanTree huftree; char Choose;while(1)coutnn*歡迎使用哈夫曼編碼/譯碼系統(tǒng)*endl;cout您可以進(jìn)行以下操作:endl;cout1 建立

22、哈夫曼樹 3 譯碼(碼文已在文件CodeFile中) 5 顯示哈夫曼樹endl;cout2 編碼(源文已在文件ToBeTran中，或鍵盤輸入) 4 顯示碼文 6 退出 endl;coutChoose;switch(Choose)case 1:huftree.CreateHuffmanTree(); break;case 2:huftree.Encoder();break;case 3:huftree.Decoder();break;case 4:huftree.PrintCodeFile();break;case 5:huftree.PrintHuffmanTree();break;case

23、6:coutn*感謝使用本系統(tǒng)!*nn;system(pause); return 0;/switch /while/main【用戶手冊(cè)】 進(jìn)入哈弗曼樹系統(tǒng)，出現(xiàn)以下界面：1建立弗曼樹 2、編碼（源文中讀入，鍵盤輸入） 3、譯碼 4、顯示碼文 5、顯示哈弗曼樹 6、退出 用戶根據(jù)該提示，選擇前面數(shù)字，就能進(jìn)入各個(gè)功能函數(shù)，實(shí)現(xiàn)函數(shù)功能?！具\(yùn)行結(jié)果】截圖一： 截圖二：截圖三：截圖四：【心得體會(huì)】本實(shí)驗(yàn)是搜集相關(guān)資料，然后自己增加功能函數(shù)的代碼實(shí)現(xiàn)的。因此，在完成未完成的功能函數(shù)之前還必須要細(xì)心閱讀所給出代碼，整體觀察各個(gè)部分之前的聯(lián)系，搞清楚已給出和未完成的代碼功能之后，才根據(jù)算法，設(shè)計(jì)出該功能的函數(shù)代碼。在完成實(shí)驗(yàn)時(shí)，有發(fā)現(xiàn)代碼也有紕漏的地方，如在源文件讀入的時(shí)候，多出了一個(gè)值，得要增加下表減這個(gè)代碼來(lái)去掉。還有就是在譯碼的時(shí)候，由于變量定義的混淆，在編譯的時(shí)候通過(guò)，但執(zhí)行時(shí)卻出現(xiàn)意料不到的結(jié)果，在自己細(xì)心觀察、思考之前也還沒(méi)找出錯(cuò)誤之處。后來(lái)通過(guò)請(qǐng)教老師，在和老師討論檢查之后才知道了錯(cuò)誤之所在，最后改正錯(cuò)誤。實(shí)驗(yàn)成功完成。【參考文獻(xiàn)】 數(shù)據(jù)結(jié)構(gòu)與算法（課本） C+語(yǔ)言基礎(chǔ)