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

《數(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 #include struct HuffmanNode //哈夫曼樹的一個(gè)結(jié)點(diǎn) { int weight; int parent; int lchild,rchild; }; class HuffmanTree //哈夫曼樹 { private: HuffmanNode *Node; //Node[]存放哈夫曼樹 char *Info; //

2、Info[]存放源文用到的字符——源碼，如a,b,c,d,e，此內(nèi)容可以放入結(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(); void Encoder(); /*使用建立好的哈夫曼樹（如果不在內(nèi)存，則從文件hfmTree中讀入并建立內(nèi)存里的哈夫曼樹）， 對(duì)文件ToBeTran中的正文進(jìn)行編碼，并將碼文寫入文件CodeFile中。 ToBeTran的內(nèi)容可以用記事本等程序編輯產(chǎn)生。*/ void Decoder(); /*待譯碼的碼文存放在文件CodeFile中，使用建立好的哈夫曼樹（如

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

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

6、ee::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::CreateHuffmanTreeFromKey

8、board() { int Num; cout<<"\n請(qǐng)輸入源碼字符集個(gè)數(shù)："; cin>>Num; if (Num<=1) { cout<<"無(wú)法建立少于2個(gè)葉子結(jié)點(diǎn)的哈夫曼樹。\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<<"請(qǐng)輸入該字符的權(quán)值或頻度"; cin>>Node[i].weight; //源文的字符權(quán)重存入Node[].weight Node[i].parent=-1; Node[i].lchild=-1; Node[i].rchild=-1; } for(i=Num;i<2*Num-1;i++) {//循環(huán)建立哈夫曼樹內(nèi)部結(jié)點(diǎn)

10、int 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<<"哈夫曼樹已成功構(gòu)造完成。

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

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

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

15、:binary|ios::in); if(fip.fail()) { cout<<"哈夫曼樹文件hfmTree.dat打開(kāi)失敗，無(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 char[LeafNum]; Node=new

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

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

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

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

20、鍵盤輸入源文 string SourceBuff; cin.ignore(); cout<<"請(qǐng)輸入需要編碼的源文(可輸入任意長(zhǎng)，按回車鍵結(jié)束):\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++; }

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

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

23、eafNum;i++) if(Info[i]==ch)//求出該文字所在的單元編號(hào) 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、de[i]=code[star-i-1]; code[star-i-1]=j; } i=0; //將源文的當(dāng)前字符的對(duì)應(yīng)編碼寫入碼文文件 while(code[i]!=\0) { fop<

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

26、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 char[k+1]; ifstream fip2("CodeFile.dat"); k=0; while(fip2.get(ch)) CodeStr[k++]=ch; fip2.cl

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

28、.lchild; 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<<"沒(méi)有碼文文件，無(wú)法顯示碼文文件內(nèi)容。\n"; return; } while(fip.get(ch)) { cout<

30、<

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

32、ffmanTree_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();

35、 break; 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 【用戶手冊(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ǔ)