數(shù)據(jù)結(jié)構(gòu)(C語言版)實驗報告(哈夫曼樹)

《數(shù)據(jù)結(jié)構(gòu)與算法》實驗報告一、需求分析1.問題描述：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼(復(fù)原)。對于雙工通道（及可以雙向傳輸信息的通道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編/譯碼系統(tǒng)。2.基本要求一個完整的系統(tǒng)應(yīng)具有以下功能：（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。（2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中。（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。（5）T：印哈夫曼樹（Treeprinting）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示出，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。3.測試數(shù)據(jù)（1）利用教科書例6-2中的數(shù)據(jù)調(diào)試程序。（2）用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THISPROGRAMISMYFAVORITE”。字符ABCDEFGHIJKLM頻度6413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161

4,實現(xiàn)提示（1）編碼結(jié)果以文本方式存儲在文件CodeFile中。（2）用戶界面可以設(shè)計為“菜單”方式：顯示上述功能符號，再加上“Q”表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。（3）在程序的一次執(zhí)行過程中，第一次執(zhí)行I、D或C命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因為文件hfmTree可能早已建好。二、概要設(shè)計本程序的數(shù)據(jù)類型定義為:typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedef

char**HuffmanCode;所實現(xiàn)的功能函數(shù)為：voidinitHuffmanTree();//選擇初始化哈夫曼樹的方式intopenfileInit();//通過打開的data.txt文件初始化哈夫曼樹

該文件是為了測試數(shù)據(jù)2包涵26個字符intinputInit();//通過手動輸入字符初始化哈夫曼樹int

HuffmanCoding(int*w);//初始化哈夫曼數(shù)，按照哈夫曼規(guī)則建立二叉樹。此函數(shù)塊調(diào)用了Select（）函數(shù)。voidSelect(intj,int&s1,int&s2);//選擇parent為0，且weight最小的兩個節(jié)點序號為s1，s2voidencoding();//選擇哈夫曼編碼方式voidopenfileEnco();//通過打開文件encode.txt的方式進行編碼voidinputEnco();//通過手動輸入的方式進行編碼voiddecode();//選擇譯碼方式voidopenfileDeco();//通過打開文件CodeFile.txt的方式進行譯碼voidinputDeco();//通過手動輸入的方式進行譯碼voiddispHT(HuffmanTreenodeRoot,intlevel);//以縮進方式輸出哈夫曼樹直觀圖主函數(shù)：主函數(shù)主要設(shè)計的是一個分支語句，讓用戶挑選所實現(xiàn)的功能。如圖所示：三、詳細(xì)設(shè)計//程序的頭文件#include<iostream>#include<fstream>#include<cstring>usingnamespacestd;ofstreamoutstuf;typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedef

char**HuffmanCode;HuffmanTreeHT=NULL;intn=0;HuffmanCodeHC=NULL;char*ch=NULL;voidinitHuffmanTree();intopenfileInit();intinputInit();int

HuffmanCoding(int*w);voidSelect(intj,int&s1,int&s2);voidencoding();voidopenfileEnco();voidinputEnco();voiddecode();voidopenfileDeco();voidinputDeco();voiddispHT(HuffmanTreenodeRoot,intlevel);voidinitHuffmanTree(){//選擇初始化哈夫曼樹intsel=0;for(;;){cout<<"\t*********************************************************"<<endl;cout<<"\t*

"<<"字符集及權(quán)值來源\t\t\t\t\t*"<<endl;cout<<"\t*\t"<<"1.使用權(quán)值文件data.txt進行編碼\t\t\t*"<<endl;cout<<"\t*\t"<<"2.自行輸入字符集及權(quán)值\t\t\t\t*"<<endl;cout<<"\t*\t"<<"3.返回上層\t\t\t\t\t*"<<endl;cout<<"\t*********************************************************"<<endl;cout<<"請輸入您的選擇"<<endl<<"

";cin>>sel;if(sel==3)break;switch(sel){case1:openfileInit();break;case2:inputInit();break;default:cout<<"對不起，您輸入的數(shù)據(jù)有誤！請重新輸入。"<<endl;}};}intopenfileInit(){

//通過打開的data.txt文件初始化哈夫曼樹該文件是為了測試數(shù)據(jù)2包涵26個字符int*w=(int*)malloc(28*sizeof(int));ch=(char*)malloc(28*sizeof(char));n=27;ifstreaminfile("data.txt",ios::in);if(!infile){cerr<<"openerror!"<<endl;exit(1);}cout<<"

權(quán)值文件中的信息（#代表空格）"<<endl<<endl;for(inti=1;infile.eof()==0;i++){infile>>ch[i];infile>>w[i];

}cout<<endl;infile.close();

cout<<"

字符:";for(i=1;i<10;i++)cout<<ch[i]<<'\t';cout<<"

權(quán)值:";for(i=1;i<10;i++)cout<<w[i]<<'\t';cout<<"

字符:";for(i=10;i<19;i++)cout<<ch[i]<<'\t';cout<<"

權(quán)值:";for(i=10;i<19;i++)cout<<w[i]<<'\t';cout<<"

字符:";for(i=19;i<28;i++)cout<<ch[i]<<'\t';cout<<"

權(quán)值:";for(i=19;i<28;i++)cout<<w[i]<<'\t';cout<<endl;n=27;HuffmanCoding(w);cout<<"

各字符編碼如下："<<