哈夫曼樹試驗(yàn)評(píng)測(cè)報(bào)告+源程序

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

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

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

4、ing）里面用了字符串的匹配進(jìn)行譯碼，在decode）里進(jìn)行了重新遍歷樹的過(guò)程，在算法的效率以及如何更為節(jié)省空間的存儲(chǔ)數(shù)據(jù)上都要進(jìn)一步改進(jìn)。本實(shí)驗(yàn)的關(guān)鍵環(huán)節(jié)及改進(jìn)措施做好本實(shí)驗(yàn)需要把握的關(guān)鍵環(huán)節(jié)若重做本實(shí)驗(yàn)，為實(shí)現(xiàn)預(yù)期效果，實(shí)驗(yàn)步驟應(yīng)如何改善對(duì)實(shí)驗(yàn)的自我評(píng)價(jià):指導(dǎo)老師評(píng)語(yǔ)及得分：簽名：年月曰頭文件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歡迎進(jìn)入哈夫曼編碼/譯碼器coutt*coutt*endlcouttt1.構(gòu)建哈夫曼樹tttttendl。couttt2.輸出哈夫曼樹tttttendl。couttt3.編碼ttttttendl。couttt4.譯碼ttttttendl。couttt5.退出ttttttendl。endlcoutt*coutendlsel。if(sel=5break。switch(sel存在！請(qǐng)先建立哈夫曼樹。outstuf.close(。break。case3:encoding(。break。cout

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

8、。coutt*t1.使用權(quán)值文件data.txt進(jìn)行編碼ttt*endl。coutt*t2.自行輸入字符集及權(quán)值tttt*endl。coutt*t3.返回上層ttttt*endl。coutt*1endlcout請(qǐng)輸入您的選擇endlsel。if(sel=3break。switch(selcase1:openfileInit(。break。case2:inputInit(。break。default:cout對(duì)不起，您輸入的數(shù)據(jù)有誤！請(qǐng)重新輸入。intopenfileInit(/通過(guò)打開的data.txt文件初始化哈夫曼樹該文件是為了測(cè)試數(shù)據(jù)2包涵26個(gè)字符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權(quán)值文件中的信息#代表空格)endl=0。i+infilechi。infilewi。cout。cout字符:。for(i=1。icoutchit。cout權(quán)值:。for(i=1。icoutwit。cout字符:。for(i=10。icoutchit。cout權(quán)值:。for(i=10。icoutwit。cout字符:。for(i=19。icoutchit。cou

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

11、i=1。icinwi。/outstuf.close(。outstuf.open(hfmTree.txt,ios:out。for(i=1。ioutstufchi。outstufwi。/將各個(gè)字符的權(quán)值寫入文件hfmTree.txtcout。cout各字符編碼如下：。for(i=1。icoutchit。cout。outstuf.open(code.txt,ios:out。for(i=1。ioutstufchi。outstufHCi。/將各個(gè)字符的編碼寫入文件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最小的兩個(gè)節(jié)點(diǎn)序號(hào)為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對(duì)不起，哈夫曼樹不存在！請(qǐng)先建立哈夫曼樹。endl。endlcoutt*coutt*要編碼的文件來(lái)源ttttt*endl。coutt*t1.使用已有文件encode.txt進(jìn)行編碼tt*endl。coutt*t2.自行輸入文件進(jìn)行編碼tttt*endl。coutt*t3.返回上層ttttt*endl。coutt*1endlcout請(qǐng)輸入

16、您的選擇endlsel。if(sel=3break。switch(selcase1:openfileEnco(。break。case2:inputEnco(。break。default:cout對(duì)不起，您輸入的數(shù)據(jù)有誤！請(qǐng)重新輸入。voidopenfileEnco(/通過(guò)打開文件encode.txt的方式進(jìn)行編碼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)錯(cuò)誤，含有不可編碼的字符！endl。break。cout。system(cls。voidinputEnco(/通過(guò)手動(dòng)輸入的方式進(jìn)行編碼system(cls

18、。cout請(qǐng)輸入您要編碼的文章以$作為文章結(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)錯(cuò)誤，含有不可編碼的字符！endl。b

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

20、1:openfileDeco(。break。case2:inputDeco(。break。default:cout。voidinputDeco(/通過(guò)手動(dòng)輸入的方式進(jìn)行譯碼system(cls。intm=2*n-1。malloc(200*sizeof(char。cout請(qǐng)輸入要譯碼的文件(以$結(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)錯(cuò)誤！此處不可譯碼！endl。for(intp=1。pif(!strcmp(record,HCpoutstufchp。cout。m=2*n-1。cout。system(cls。voidopenfileDeco(/通過(guò)打開文件CodeFile.txt的方式進(jìn)行譯碼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