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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上【詳細(xì)設(shè)計(jì)】具體代碼實(shí)現(xiàn)如下：/HaffmanTree.h#include<iostream>#include<fstream>#include<string>struct HuffmanNode /哈夫曼樹(shù)的一個(gè)結(jié)點(diǎn) int weight; int parent; int lchild,rchild; ;class HuffmanTree /哈夫曼樹(shù) private: HuffmanNode *Node; /Node存放哈夫曼樹(shù) char *Info; /Info存放源文用到的字符源碼，如'a','b

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

3、reeFromKeyboard(); void CreateHuffmanTreeFromFile(); void Encoder(); /*使用建立好的哈夫曼樹(shù)（如果不在內(nèi)存，則從文件hfmTree中讀入并建立內(nèi)存里的哈夫曼樹(shù)）， 對(duì)文件ToBeTran中的正文進(jìn)行編碼，并將碼文寫(xiě)入文件CodeFile中。 ToBeTran的內(nèi)容可以用記事本等程序編輯產(chǎn)生。*/ void Decoder(); /*待譯碼的碼文存放在文件CodeFile中，使用建立好的哈夫曼樹(shù)（如果不在內(nèi)存， 則從文件hfmTree中讀入并建立內(nèi)存里的哈夫曼樹(shù)）將碼文譯碼， 得到的源文寫(xiě)入文件TextFile中，并同時(shí)輸出到

4、屏幕上。*/ void PrintCodeFile(); /*將碼文文件CodeFile顯示在屏幕上*/ void PrintHuffmanTree(); /*將哈夫曼樹(shù)以直觀的形式（凹入表示法，或廣義表，或其他樹(shù)形表示法）顯示在屏幕上， 同時(shí)寫(xiě)入文件TreePrintFile中*/ void PrintHuffmanTree_aoru(int T,int layer=1); /*凹入表示法顯示哈夫曼樹(shù)，由PrintHuffmanTree()調(diào)用*/;/HuffmanTree.cpp#include<string>#include<limits> /為使用整型最大值#i

5、nclude"HuffmanTree.h"using namespace std;/*HuffmanTree:HuffmanTree()Node=NULL;/*HuffmanTree:HuffmanTree()deleteNode;/*void HuffmanTree:CreateHuffmanTree() char Choose; cout<<"你要從文件中讀入哈夫曼樹(shù)(按1)，還是從鍵盤(pán)輸入哈夫曼樹(shù)(按2)？"cin>>Choose;if(Choose='2') /鍵盤(pán)輸入建立哈夫曼樹(shù)CreateHuffman

6、TreeFromKeyboard();/choose='2'else /從哈夫曼樹(shù)文件hfmTree.dat中讀入信息并建立哈夫曼樹(shù)CreateHuffmanTreeFromFile();/*void HuffmanTree:CreateHuffmanTreeFromKeyboard()int Num;cout<<"n請(qǐng)輸入源碼字符集個(gè)數(shù)："cin>>Num;if (Num<=1)cout<<"無(wú)法建立少于2個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)。nn"return;LeafNum=Num;Node=new Huf

7、fmanNode2*Num-1; Info=new char2*Num-1;for(int i=0;i<Num;i+) /讀入哈夫曼樹(shù)的葉子結(jié)點(diǎn)信息cout<<"請(qǐng)輸入第"<<i+1<<"個(gè)字符值"getchar(); Infoi=getchar(); /源文的字符存入字符數(shù)組Info getchar();cout<<"請(qǐng)輸入該字符的權(quán)值或頻度"cin>>Nodei.weight; /源文的字符權(quán)重存入Node.weight Nodei.parent=-1; Nodei

8、.lchild=-1; Nodei.rchild=-1; for(i=Num;i<2*Num-1;i+) /循環(huán)建立哈夫曼樹(shù)內(nèi)部結(jié)點(diǎn)int pos1=-1,pos2=-1;int max1=32767,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;

9、 Nodepos1.parent=i; Nodepos2.parent=i; Nodei.lchild=pos1; Nodei.rchild=pos2; Nodei.parent=-1; Nodei.weight=Nodepos1.weight+Nodepos2.weight; /forcout<<"哈夫曼樹(shù)已成功構(gòu)造完成。n"/把建立好的哈夫曼樹(shù)寫(xiě)入文件hfmTree.datchar ch;cout<<"是否要替換原來(lái)的哈夫曼樹(shù)文件(Y/N):"cin>>ch;if (ch!='y'&&

10、;ch!='Y') return;elseofstream fop; fop.open("hfmTree.dat",ios:out|ios:binary|ios:trunc); /打開(kāi)文件 if(fop.fail() cout<<"n哈夫曼樹(shù)文件打開(kāi)失敗，無(wú)法將哈夫曼樹(shù)寫(xiě)入hfmTree.dat文件。n" return;fop.write(char*)&Num,sizeof(Num); /先寫(xiě)入哈夫曼樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)for(i=0;i<Num;i+) /再寫(xiě)入源文字符集的所有字符（存儲(chǔ)在Info中）fop.wri

11、te(char*)&Infoi,sizeof(Infoi);flush(cout);for(i=0;i<2*Num-1;i+) /最后寫(xiě)入哈夫曼樹(shù)的各個(gè)結(jié)點(diǎn)（存儲(chǔ)在Node中）fop.write(char*)&Nodei,sizeof(Nodei);flush(cout);fop.close(); /關(guān)閉文件cout<<"n哈夫曼樹(shù)已成功寫(xiě)入hfmTree.dat文件。n"/*void HuffmanTree:CreateHuffmanTreeFromFile()ifstream fip; fip.open("hfmTree.da

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

13、;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<<"哈夫曼樹(shù)已成功構(gòu)造完成。n"/*void HuffmanTree:Encoder()if(Node=NULL)/內(nèi)存沒(méi)有哈夫曼樹(shù)，則從哈夫曼樹(shù)文件hfmTree.dat中讀入信息并建立哈夫曼樹(shù)CreateHuffmanTreeFromFile();if

14、 (LeafNum<=1)cout<<"內(nèi)存無(wú)哈夫曼樹(shù)。操作撤銷。nn"return;/if char *SourceText; /字符串?dāng)?shù)組，用于存放源文 /讓用戶選擇源文是從鍵盤(pán)輸入，還是從源文文件ToBeTran.txt中讀入char Choose; cout<<"你要從文件中讀入源文(按1)，還是從鍵盤(pán)輸入源文(按2)？"cin>>Choose;if(Choose='1')ifstream fip1("ToBeTran.txt");if(fip1.fail() cout

15、<<"源文文件打開(kāi)失敗!無(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");/第二次讀源文文件，把內(nèi)容寫(xiě)入SourceTextk=0; while(fip2.get(ch) SourceTextk+=ch; fip2.close();SourceTextk='0

16、' cout<<"需編碼的源文為："cout<<SourceText<<endl;else /從鍵盤(pán)輸入源文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(SourceBuffk!='0

17、') SourceTextk=SourceBuffk;k+;SourceTextk='0'cout<<"覆蓋已有的編碼原文件?（Y/N）"char ch;cin>>ch;if(ch='y'|ch='Y')ofstream fip2;fip2.open("ToBeTran.txt");if(!fip2)cerr<<"文件打開(kāi)失??！"<<endl;abort();fip2<<SourceText<<endl;fi

18、p2.close();cout<<"需編碼的源文已寫(xiě)入ToBeTran.txt中"<<endl; /開(kāi)始編碼ofstream fop("CodeFile.dat",ios:trunc); /打開(kāi)碼文存放文件char *code; code=new charLeafNum; /存放一個(gè)源文字符的編碼 int k=0;while(SourceTextk!='0') /源文串中從第一個(gè)字符開(kāi)始逐個(gè)編碼 int star=0;char ch=SourceTextk;for(int i=0;i<LeafNum;i+)i

19、f(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;i<star/2;i+)int j=codei;codei=codestar-i-1;codestar-i-1=j; i=0; /將源文的當(dāng)前字符的對(duì)應(yīng)編碼寫(xiě)入碼文文件while(codei!='0') fop&l

20、t;<codei;i+;k+; /源文串中的字符后移一個(gè)fop.close();cout<<"已完成編碼，碼文已寫(xiě)入文件CodeFile.dat中。nn" /*void HuffmanTree:Decoder()/如果內(nèi)存沒(méi)有哈夫曼樹(shù)，則從哈夫曼樹(shù)文件hfmTree.dat中讀入信息并建立哈夫曼樹(shù)if(Node=NULL) CreateHuffmanTreeFromFile();if (LeafNum<=1)cout<<"內(nèi)存無(wú)哈夫曼樹(shù)。操作撤銷。nn"return;/將碼文從文件CodeFile.dat中讀入 Cod

21、eStrifstream 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' c

22、out<<"經(jīng)譯碼得到的源文為："ofstream fop("TextFile.dat"); int j=LeafNum*2-1-1; /j指向哈夫曼樹(shù)的根 int i=0; /碼文從第一個(gè)符號(hào)開(kāi)始，順著哈夫曼樹(shù)由根下行，按碼文的當(dāng)前符號(hào)決定下行到左孩子還是右孩子while(CodeStri!='0') /下行到哈夫曼樹(shù)的葉子結(jié)點(diǎn)處，則譯出葉子結(jié)點(diǎn)對(duì)應(yīng)的源文字符if(CodeStri='0') j=Nodej.lchild;else j=Nodej.rchild;if(Nodej.rchild=-1)cout&

23、lt;<Infoj;fop<<Infoj;j=LeafNum*2-1-1;i+; fop.close(); cout<<"n譯碼成功且已存到文件TextFile.dat中。nn"/*void HuffmanTree:PrintCodeFile()char ch;int i=1;ifstream fip("CodeFile.dat"); ofstream fop("CodePrin.dat"); if(fip.fail()cout<<"沒(méi)有碼文文件，無(wú)法顯示碼文文件內(nèi)容。n"

24、return;while(fip.get(ch)cout<<ch; fop<<ch; if(i=50) cout<<endl;fop<<endl;i=0;i+;cout<<endl;fop<<endl;fip.close(); fop.close(); /*void HuffmanTree:PrintHuffmanTree()/如果內(nèi)存沒(méi)有哈夫曼樹(shù)，則從哈夫曼樹(shù)文件hfmTree.dat中讀入信息并建立哈夫曼樹(shù)if(Node=NULL) CreateHuffmanTreeFromFile();if (LeafNum<

25、=1) cout<<"內(nèi)存無(wú)哈夫曼樹(shù)。操作撤銷。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;i<layer;i+) cout<<"_"cout<<NodeT.weight<

26、<endl;if(NodeT.lchild!=-1) PrintHuffmanTree_aoru(NodeT.lchild,+layer);if(NodeT.rchild!=-1) PrintHuffmanTree_aoru(NodeT.rchild,layer-);/main.cpp#include<string.h>#include<stdlib.h>using namespace std;int main()HuffmanTree huftree; char Choose;while(1)cout<<"nn*歡迎使用哈夫曼編碼/譯碼系統(tǒng)*"<<endl;cout<<"您可以進(jìn)行以下操作:"<<endl;cout<<"1 建立哈夫曼樹(shù) 3 譯碼(碼文已在文件CodeFile中) 5 顯示哈夫曼樹(shù)"<<endl;cout<<"2 編碼(源文已在文件ToBeT