數(shù)據(jù)結構哈夫曼樹編碼譯碼實驗報告

《數(shù)據(jù)結構哈夫曼樹編碼譯碼實驗報告》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構哈夫曼樹編碼譯碼實驗報告（15頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、【詳細設計】 具體代碼實現(xiàn)如下： //HaffmanTree.h #include #include #include struct HuffmanNode //哈夫曼樹的一個結點 { int weight; int parent; int lchild,rchild; }; class HuffmanTree //哈夫曼樹 { private: HuffmanNode *Node; //Node[]存放哈夫曼樹 char *Info; //In

2、fo[]存放源文用到的字符——源碼，如a,b,c,d,e，此內容可以放入結點中，不單獨設數(shù)組存放 int LeafNum; //哈夫曼樹的葉子個數(shù)，也是源碼個數(shù) public: HuffmanTree(); ~HuffmanTree(); void CreateHuffmanTree(); /*在內存中建立哈夫曼樹，存放在Node[]中。 讓用戶從兩種建立哈夫曼樹的方法中選擇： 1.從鍵盤讀入源碼字符集個數(shù)，每個字符，和每個字符的權重，建立哈夫曼樹， 并將哈夫曼樹寫入文件hfmTree中。2.從文件hfmTree中讀入哈夫

3、曼樹信息，建立哈夫曼樹*/ void CreateHuffmanTreeFromKeyboard(); void CreateHuffmanTreeFromFile(); void Encoder(); /*使用建立好的哈夫曼樹（如果不在內存，則從文件hfmTree中讀入并建立內存里的哈夫曼樹）， 對文件ToBeTran中的正文進行編碼，并將碼文寫入文件CodeFile中。 ToBeTran的內容可以用記事本等程序編輯產生。*/ void Decoder(); /*待譯碼的碼文存放在文件CodeFile中，使用建立好的哈夫曼樹（如果不

4、在內存， 則從文件hfmTree中讀入并建立內存里的哈夫曼樹）將碼文譯碼， 得到的源文寫入文件TextFile中，并同時輸出到屏幕上。*/ void PrintCodeFile(); /*將碼文文件CodeFile顯示在屏幕上*/ void PrintHuffmanTree(); /*將哈夫曼樹以直觀的形式（凹入表示法，或廣義表，或其他樹形表示法）顯示在屏幕上， 同時寫入文件TreePrintFile中*/ void PrintHuffmanTree_aoru(int T,int laye

5、r=1); /*凹入表示法顯示哈夫曼樹，由PrintHuffmanTree()調用*/ }; ///////////////////////////////////////////////////////////////////HuffmanTree.cpp #include #include //為使用整型最大值 #include"HuffmanTree.h" using namespace std; //****************************************************** HuffmanTree

6、::HuffmanTree() { Node=NULL; } //****************************************************** HuffmanTree::~HuffmanTree() { delete[]Node; } //****************************************************** void HuffmanTree::CreateHuffmanTree() { char Choose; cout<<"你要從文件中讀入哈夫曼樹(按1)，

7、還是從鍵盤輸入哈夫曼樹(按2)？"; cin>>Choose; if(Choose==2) {//鍵盤輸入建立哈夫曼樹 CreateHuffmanTreeFromKeyboard(); }//choose==2 else { //從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹 CreateHuffmanTreeFromFile(); } } //****************************************************** void HuffmanTree::CreateHuffmanTreeFromKeybo

8、ard() { int Num; cout<<"\n請輸入源碼字符集個數(shù)："; cin>>Num; if (Num<=1) { cout<<"無法建立少于2個葉子結點的哈夫曼樹。\n\n"; return; } LeafNum=Num; Node=new HuffmanNode[2*Num-1]; Info=new char[2*Num-1]; for(int i=0;i

9、 Info[i]=getchar(); //源文的字符存入字符數(shù)組Info[] getchar(); cout<<"請輸入該字符的權值或頻度"; cin>>Node[i].weight; //源文的字符權重存入Node[].weight Node[i].parent=-1; Node[i].lchild=-1; Node[i].rchild=-1; } for(i=Num;i<2*Num-1;i++) {//循環(huán)建立哈夫曼樹內部結點 in

10、t pos1=-1,pos2=-1; int max1=32767,max2=32767; for(int j=0;j

11、 { max2=Node[j].weight; pos2=j; } Node[pos1].parent=i; Node[pos2].parent=i; Node[i].lchild=pos1; Node[i].rchild=pos2; Node[i].parent=-1; Node[i].weight=Node[pos1].weight+Node[pos2].weight; } //for cout<<"哈夫曼樹已成功構造完成。\n

12、"; //把建立好的哈夫曼樹寫入文件hfmTree.dat char ch; cout<<"是否要替換原來的哈夫曼樹文件(Y/N):"; cin>>ch; if (ch!=y&&ch!=Y) return; else { ofstream fop; fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //打開文件 if(fop.fail()) { cout<<"\n哈夫曼樹文件打開失敗，無法將哈夫曼

13、樹寫入hfmTree.dat文件。\n"; return; } fop.write((char*)&Num,sizeof(Num)); //先寫入哈夫曼樹的葉子結點個數(shù) for(i=0;i

14、p.write((char*)&Node[i],sizeof(Node[i])); flush(cout); } fop.close(); //關閉文件 cout<<"\n哈夫曼樹已成功寫入hfmTree.dat文件。\n"; } } //****************************************************** void HuffmanTree::CreateHuffmanTreeFromFile() { ifstream fip; fip.open("hfmTree.dat",ios::b

15、inary|ios::in); if(fip.fail()) { cout<<"哈夫曼樹文件hfmTree.dat打開失敗，無法建立哈夫曼樹。\n"; return; } fip.read((char*)&LeafNum,sizeof(LeafNum)); if (LeafNum<=1) { cout<<"哈夫曼樹文件中的數(shù)據(jù)有誤，葉子結點個數(shù)少于2個，無法建立哈夫曼樹。\n"; fip.close(); return; } Info=new char[LeafNum]; Node=new H

16、uffmanNode[2*LeafNum-1]; for(int i=0;i

17、*** void HuffmanTree::Encoder() { if(Node==NULL) {//內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹 CreateHuffmanTreeFromFile(); if (LeafNum<=1) { cout<<"內存無哈夫曼樹。操作撤銷。\n\n"; return; } }//if char *SourceText; //字符串數(shù)組，用于存放源文 //讓用戶選擇源文是從鍵盤輸入，還是從源文文件ToBeTran.txt中讀入 c

18、har Choose; cout<<"你要從文件中讀入源文(按1)，還是從鍵盤輸入源文(按2)？"; cin>>Choose; if(Choose==1) { ifstream fip1("ToBeTran.txt"); if(fip1.fail()) { cout<<"源文文件打開失敗!無法繼續(xù)執(zhí)行。\n"; return; } char ch; int k=0; while(fip1.get(ch)) k++; //第一次讀文件只統(tǒng)計文件中有多少個字符，將字符數(shù)存入k fi

19、p1.close(); SourceText=new char[k+1]; //申請存放源文的字符數(shù)組空間 ifstream fip2("ToBeTran.txt");//第二次讀源文文件，把內容寫入SourceText[] k=0; while(fip2.get(ch)) SourceText[k++]=ch; fip2.close(); SourceText[k]=\0; cout<<"需編碼的源文為："; cout<

20、輸入源文 string SourceBuff; cin.ignore(); cout<<"請輸入需要編碼的源文(可輸入任意長，按回車鍵結束):\n"; getline(cin,SourceBuff,\n); int k=0; while(SourceBuff[k]!=\0) k++; SourceText=new char[k+1]; k=0; while(SourceBuff[k]!=\0) { SourceText[k]=SourceBuff[k]; k++; } So

21、urceText[k]=\0; cout<<"覆蓋已有的編碼原文件?（Y/N）"; char ch; cin>>ch; if(ch==y||ch==Y) { ofstream fip2; fip2.open("ToBeTran.txt"); if(!fip2) { cerr<<"文件打開失?。?<

22、 } } //開始編碼 ofstream fop("CodeFile.dat",ios::trunc); //打開碼文存放文件 char *code; code=new char[LeafNum]; //存放一個源文字符的編碼 int k=0; while(SourceText[k]!=\0) //源文串中從第一個字符開始逐個編碼 { int star=0; char ch=SourceText[k]; for(int i=0;i

23、fNum;i++) if(Info[i]==ch)//求出該文字所在的單元編號 break; int j=i; while(Node[j].parent!=-1) { j=Node[j].parent; if(Info[Node[j].lchild]==Info[i]) code[star++]=0; else code[star++]=1; i=j; } code[star]=\0; for(i=0;i

24、[i]=code[star-i-1]; code[star-i-1]=j; } i=0; //將源文的當前字符的對應編碼寫入碼文文件 while(code[i]!=\0) { fop<

25、 void HuffmanTree::Decoder() { //如果內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹 if(Node==NULL) { CreateHuffmanTreeFromFile(); if (LeafNum<=1) { cout<<"內存無哈夫曼樹。操作撤銷。\n\n"; return; } } //將碼文從文件CodeFile.dat中讀入 CodeStr[] ifstream fip1("CodeFile.dat"); if

26、(fip1.fail()) { cout<<"沒有碼文，無法譯碼。\n"; return; } char* CodeStr; int k=0; char ch; while(fip1.get(ch)) { k++; } fip1.close(); CodeStr=new char[k+1]; ifstream fip2("CodeFile.dat"); k=0; while(fip2.get(ch)) CodeStr[k++]=ch; fip2.clos

27、e(); CodeStr[k]=\0; cout<<"經(jīng)譯碼得到的源文為："; ofstream fop("TextFile.dat"); int j=LeafNum*2-1-1; //j指向哈夫曼樹的根 int i=0; //碼文從第一個符號開始，順著哈夫曼樹由根下行，按碼文的當前符號決定下行到左孩子還是右孩子 while(CodeStr[i]!=\0) { //下行到哈夫曼樹的葉子結點處，則譯出葉子結點對應的源文字符 if(CodeStr[i]==0) j=Node[j].l

28、child; else j=Node[j].rchild; if(Node[j].rchild==-1) { cout<

29、 char ch; int i=1; ifstream fip("CodeFile.dat"); ofstream fop("CodePrin.dat"); if(fip.fail()) { cout<<"沒有碼文文件，無法顯示碼文文件內容。\n"; return; } while(fip.get(ch)) { cout<

30、endl; i=0; } i++; } cout<

31、TreeFromFile(); if (LeafNum<=1) { cout<<"內存無哈夫曼樹。操作撤銷。\n\n"; return; } } ofstream fop("TreePrint.dat",ios_base::trunc); fop.close(); PrintHuffmanTree_aoru(2*LeafNum-1-1,0); return; } //****************************************************** void HuffmanTree::PrintHuff

32、manTree_aoru(int T,int layer) { for(int i=0;i

33、///////////////////////main.cpp #include #include using namespace std; int main() { HuffmanTree huftree; char Choose; while(1) { cout<<"\n\n**********************歡迎使用哈夫曼編碼/譯碼系統(tǒng)***********************"<

34、樹 3 譯碼(碼文已在文件CodeFile中) 5 顯示哈夫曼樹"<>Choose; switch(Choose) { case 1: huftree.CreateHuffmanTree(); break; case 2: huftree.Encoder(); b

35、reak; case 3: huftree.Decoder(); break; case 4: huftree.PrintCodeFile(); break; case 5: huftree.PrintHuffmanTree(); break; case 6: cout<<"\n*************************感謝使用本系統(tǒng)!***********************\n\n"; system("pause"); return 0; }/

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