哈夫曼樹試驗評測報告+源程序

1、項目組長學號成員專業(yè)班級實驗項目名稱哈夫曼樹指導教師及職稱開課學期20182018學年第一學期上課時間2018年9月1日一2018年12月29日、實驗設計方案實驗名稱：哈夫曼樹實驗時間：2018年12月1日小組合作：是否O小組成員：1、實驗目的利用赫夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼復原）。對于雙工信道即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個赫夫曼碼的編/譯碼系統(tǒng)。2、實驗思路實驗內(nèi)容、數(shù)據(jù)處理方法及實驗步驟等）（1I:初始化1

2、nitialization）。從終端讀入字符集大小n,以及n個字符和n個權值，建立赫夫曼樹，并將它存于文件hfmTree中。（2E：編碼Encoding）。利用已建好的赫夫曼樹如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。（3D:譯碼Decoding）。利用已建好的赫夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件Textfile中（4P:印代碼文件vPrint）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。（5T：印赫夫曼樹vTreep

3、rinting）。將已在內(nèi)存中的赫夫曼樹以直觀的方式比如樹）顯示在終端上，同時將此字符形式的赫夫曼樹寫入文件TreePrint中。指導老師對實驗設計方案的意見指導老師簽名：年月曰二、實驗結(jié)果與分析1、實驗目的、實驗思路清輸入您舸選擇=丄|&342801567612、實驗現(xiàn)象、數(shù)據(jù)及結(jié)果權值文件中的信息0代表空格47Q1Z1*事HXMa口亠a口昭魁出陽碼出夫AP1FO1EDMBTA.b84R21180H7J027s字權字權字權222321412M3、對實驗現(xiàn)象、數(shù)據(jù)及觀察結(jié)果的分析與討論4、結(jié)論5、實驗總結(jié)整體而言，整個程序主要使用了HuffmanCoding（的方式進行哈夫曼編碼，在encod

4、ing）里面用了字符串的匹配進行譯碼，在decode）里進行了重新遍歷樹的過程，在算法的效率以及如何更為節(jié)省空間的存儲數(shù)據(jù)上都要進一步改進。本實驗的關鍵環(huán)節(jié)及改進措施做好本實驗需要把握的關鍵環(huán)節(jié)若重做本實驗，為實現(xiàn)預期效果，實驗步驟應如何改善對實驗的自我評價:指導老師評語及得分：簽名：年月曰頭文件typedefstructunsignedintweight。unsignedintparent,lchild,rchild。HTNode,*HuffmanTree。typedefchar*HuffmanCode。HuffmanTreeHT=NULL。intn=0。HuffmanCodeHC=NULL

5、。char*ch=NULL。voidinitHuffmanTree(。intopenfileInit(。intinputInit(。intHuffmanCoding(int*w。voidSelect(intj,int&s1,int&s2。voidencoding(。voidopenfileEnco(。voidinputEnco(。voiddecode(。voidopenfileDeco(。voidinputDeco(。voiddispHT(HuffmanTreenodeRoot,intlevel#include#include#include哈夫曼樹river.husingnamespaces

6、tc。ofstreamoutstuf。voidmain(system(cls。intsel=0。coutttt歡迎進入哈夫曼編碼/譯碼器coutt*coutt*endlcouttt1.構建哈夫曼樹tttttendl。couttt2.輸出哈夫曼樹tttttendl。couttt3.編碼ttttttendl。couttt4.譯碼ttttttendl。couttt5.退出ttttttendl。endlcoutt*coutendlsel。if(sel=5break。switch(sel存在！請先建立哈夫曼樹。outstuf.close(。break。case3:encoding(。break。cout

7、endlsel。if(sel=5break。switch(sel存在！請先建立哈夫曼樹。outstuf.close(。break。case3:encoding(。break。case1:initHuffmanTree(。break。case2:if(HC=NULLcoutcase4:decode(。break。default:cout對不起，您輸入的數(shù)據(jù)不在1-5內(nèi)！請重新輸入。cout感謝使用本系統(tǒng)！。voidinitHuffmanTree(/選擇初始化哈夫曼樹intsel=0。system(cls。for(。coutt*coutt*1endlcoutt*字符集及權值來源ttttt*endl

8、。coutt*t1.使用權值文件data.txt進行編碼ttt*endl。coutt*t2.自行輸入字符集及權值tttt*endl。coutt*t3.返回上層ttttt*endl。coutt*1endlcout請輸入您的選擇endlsel。if(sel=3break。switch(selcase1:openfileInit(。break。case2:inputInit(。break。default:cout對不起，您輸入的數(shù)據(jù)有誤！請重新輸入。intopenfileInit(/通過打開的data.txt文件初始化哈夫曼樹該文件是為了測試數(shù)據(jù)2包涵26個字符int*w=(int*malloc(2

9、8*sizeof(intch=(char*malloc(28*sizeof(char。n=27。ifstreaminfile(data.txt,ios:in。system(cls。if(!infilecerropenerror!。cout權值文件中的信息#代表空格)endl=0。i+infilechi。infilewi。cout。cout字符:。for(i=1。icoutchit。cout權值:。for(i=1。icoutwit。cout字符:。for(i=10。icoutchit。cout權值:。for(i=10。icoutwit。cout字符:。for(i=19。icoutchit。cou

10、t權值:。for(i=19。icoutwit。cout。cout各字符編碼如下：endl。for(i=1。icoutchit。coutHCi。for(i=1。ioutstufchi。outstuf。return0。system(cls。intinputInit(/通過手動輸入字符初始化哈夫曼樹system(cls。coutn。int*w=(int*malloc(n+1*sizeof(int。if(!wcoutmalloc(n+1*sizeof(char。if(!chcoutERROR。return0。cout請輸入各字符t。for(inti=1。icinchi。cout請輸入各權值t。for(

11、i=1。icinwi。/outstuf.close(。outstuf.open(hfmTree.txt,ios:out。for(i=1。ioutstufchi。outstufwi。/將各個字符的權值寫入文件hfmTree.txtcout。cout各字符編碼如下：。for(i=1。icoutchit。cout。outstuf.open(code.txt,ios:out。for(i=1。ioutstufchi。outstufHCi。/將各個字符的編碼寫入文件code.txtcout。return0。system(cls。intHuffmanCoding(int*w/哈夫曼編碼system(cls。

12、if(nreturn1。intm=2*n-1。HT=(HuffmanTreemalloc(m+1*sizeof(HTNode。if(!HTcoutERROR。return0。for(inti=1。iHTi.weight=wi。HTi.parent=HTi.lchild=HTi.rchild=0。for(。iHTi.weight=HTi.parent=HTi.lchild=HTi.rchild=0。ints1=0。ints2=0。for(i=n+1。iSelect(i-1,s1,s2。HTs1.parent=i。HTs2.parent=i。HTi.lchild=s1。HTi.rchild=s2。

13、HTi.weight=HTs1.weight+HTs2.weight。HC=(HuffmanCodemalloc(n+1*sizeof(char*。char*cd=(char*malloc(n*sizeof(char。if(!cdcoutERROR。return0。cdn-1=0。intstart。for(i=1。istart=n-1。for(intc=i,unsignedintf=HTi.parent。f!=0。c=f,f=HTf.parentif(HTf.lchild=ccd-start=0。elsecd-start=1。HCi=(char*malloc(n-start*sizeof(ch

14、ar。strcpy(HCi,&cdstart。free(cd。return0。system(cls。voidSelect(intj,int&s1,int&s2/選擇parent為0，且weight最小的兩個節(jié)點序號為s1，s2system(cls。for(inth=1。hif(HTh.parent=0s1=h。break。h+。for(。hif(HTh.parent=0s2=h。break。intm。if(HTs1.weightHTs2.weightm=s1。s1=s2。s2=m。h+。for(。hif(HTs1.weightHTh.weight&HTh.parent=0s1=h。for(m=

15、1。mif(HTs2.weightHTm.weight&m!=s1&HTm.parent=0s2=msystem(cls。voidencoding(/選擇哈夫曼編碼方式system(cls。intsel=0。for(。break。break。if(!HTcout對不起，哈夫曼樹不存在！請先建立哈夫曼樹。endl。endlcoutt*coutt*要編碼的文件來源ttttt*endl。coutt*t1.使用已有文件encode.txt進行編碼tt*endl。coutt*t2.自行輸入文件進行編碼tttt*endl。coutt*t3.返回上層ttttt*endl。coutt*1endlcout請輸入

16、您的選擇endlsel。if(sel=3break。switch(selcase1:openfileEnco(。break。case2:inputEnco(。break。default:cout對不起，您輸入的數(shù)據(jù)有誤！請重新輸入。voidopenfileEnco(/通過打開文件encode.txt的方式進行編碼system(cls。coutencode.txt文件內(nèi)容如下#代表空格)：。if(!infilecerropenerror!。char*file=(char*malloc(200*sizeof(char。for(inti=1。infile.eof(=0&i!=200。i+infile

17、filei。coutfile=(char*realloc(file,(200+80*sizeof(char。for(。infile.eof(=0&i!=280。i+infilefilei。cout。coutendl。intm=i。cout編碼結(jié)果是：。outstuf.open(CodeFile.txt,ios:out。for(i=1。ifor(intj=1。jif(filei=chjcoutHCj。outstufcoutendl此處編碼出現(xiàn)錯誤，含有不可編碼的字符！endl。break。cout。system(cls。voidinputEnco(/通過手動輸入的方式進行編碼system(cls

18、。cout請輸入您要編碼的文章以$作為文章結(jié)尾)malloc(200*sizeof(char。for(inti=1。icinfilei。if(filei=$break。if(i=200file=(char*realloc(file,(200+80*sizeof(char。for(。icinfilei。if(filei=$break。intm=i。cout編碼結(jié)果是：。outstuf.open(CodeFile.txt,ios:out。for(i=1。ifor(intj=1。jif(filei=chjcoutHCj。outstufcoutendl此處編碼出現(xiàn)錯誤，含有不可編碼的字符！endl。b

19、reak。cout。system(cls。voiddecode(/選擇譯碼方式system(cls。intsel=0。for(。endl。break。cout對不起，哈夫曼樹不存在！請先建立哈夫曼樹。endlcoutt*coutt*要譯碼的文件來源ttttt*endl。coutt*t1.使用已有文件CodeFile.txt進行譯碼tt*endl。coutt*t2.自行輸入文件進行譯碼tttt*endl。coutt*t3.返回上層ttttt*endl。coutt*1endlcout請輸入您的選擇endlcout請輸入您的選擇endlsel。if(sel=3break。switch(selcase

20、1:openfileDeco(。break。case2:inputDeco(。break。default:cout。voidinputDeco(/通過手動輸入的方式進行譯碼system(cls。intm=2*n-1。malloc(200*sizeof(char。cout請輸入要譯碼的文件(以$結(jié)束)endl。for(inti=1。icinpasswordi。if(i=200password=(char*realloc(password,(200+80*sizeof(char。for(。icinpasswordi。cout譯碼結(jié)果為#代表空格)。outstuf.open(TextFile.txt

21、,ios:out。for(i=1。passwordi!=$。charrecord20。for(intj=0,q=i。passwordq!=$。j+,q+if(passwordq=0recordj=0。m=HTm.lchild。elserecordj=1。m=HTm.rchild。if(HTm.rchild=0recordj+1=0。break。if(HTm.rchild!=0coutendl譯碼在此處出現(xiàn)錯誤！此處不可譯碼！endl。for(intp=1。pif(!strcmp(record,HCpoutstufchp。cout。m=2*n-1。cout。system(cls。voidopenfileDeco(/通過打開文件CodeFile.txt的方式進行譯碼system(cls。intm=2*n-1。break。coutCodeFile.txt文件內(nèi)容如下：。if(!infilecerropenerror!。char*password=(char*malloc(200*sizeof(char。for(inti=1。infile.eof(=0&i!=200。i+infilepasswordi。cou