2023年新版哈夫曼樹實驗報告

計算機科學與技術(shù)學院數(shù)據(jù)結(jié)構(gòu)實驗報告班級2023級計算機1班學號—姓名張建華成績實驗項目簡樸哈夫曼編/譯碼的設(shè)計與實現(xiàn)實驗日期一、實驗?zāi)康谋緦嶒灥哪康氖沁M一步理解哈夫曼樹的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，進一步提高使用理論知識指導(dǎo)解決實際問題的能力。二、實驗問題描述運用哈夫曼編碼進行通信可以大大提高信道運用率，縮短信息傳輸時間，減少傳輸成本。但是,這規(guī)定在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼,在接受端將傳來的數(shù)據(jù)進行譯碼,此實驗即設(shè)計這樣的一個簡樸編/碼系統(tǒng)。系統(tǒng)應(yīng)當具有如下的幾個功能：1、接受原始數(shù)據(jù)。從終端讀入字符集大小n,以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文獻hfmtree.dat中。2、編碼。，運用已建好的哈夫曼樹（如不在內(nèi)存，則從文獻hfmtree.dat中讀入），對文獻中的正文進行編碼,然后將結(jié)果存入文獻codefile,dat中。3、譯碼。運用已建好的哈夫曼樹將文獻codefile,dat中的代碼進行譯碼,結(jié)果存入文獻textfile,dat中。4、打印編碼規(guī)則。即字符與編碼的一一相應(yīng)關(guān)系。5、打印哈夫曼樹，。將已在內(nèi)存中的哈夫曼樹以直觀的方式顯示在終端上。三、實驗環(huán)節(jié)1、實驗問題分析1、構(gòu)造哈夫曼樹時使用靜態(tài)鏈表作為哈夫曼樹的存儲。。在構(gòu)造哈夫曼樹時，設(shè)計一個結(jié)構(gòu)體數(shù)組HuffNode保存哈夫曼樹中各結(jié)點的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個葉子結(jié)點的哈夫曼樹共有2n-1個結(jié)點，所以數(shù)組HuffNode的大小設(shè)立為2n-1,描述結(jié)點的數(shù)據(jù)類型為：Typedefstrcut（Intweight；/*結(jié)點權(quán)值*/Intparent;IntIchiId；IntrchiId；）HNodeType;2、求哈夫曼編碼時使用一維結(jié)構(gòu)數(shù)組HuffCode作為哈夫曼編碼信息的存儲。，求哈夫曼編碼，實質(zhì)上就是在已建立的哈夫曼樹中,從葉子結(jié)點開始，沿結(jié)點的雙親鏈域回退到根結(jié)點，沒回退一步，就走過了哈夫曼樹的一個分支,從而得到一位哈夫曼碼值，由于一個字符的哈夫曼編碼是從根結(jié)點到相應(yīng)葉子結(jié)點所通過的途徑上各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼,后得到的分支代碼位所求編碼的高位碼，所以設(shè)計如下數(shù)據(jù)類型：#defineMAXBIT10Typedefstruct（。Intbit[MAXBIT];?Intstart;}HCodeType;3、文獻hfmtree.datvcodefiIe.dat和textfiIe.dato2、功能（函數(shù)）設(shè)計（1）、初始化功能模塊。

此功能模塊的功能為從鍵盤接受字符集大小n，以及n個字符和n個權(quán)值。(2)、建立哈夫曼樹的功能模塊。此模塊功能為使用1中得到的數(shù)據(jù)按照教材中的構(gòu)造哈夫曼樹的算法構(gòu)造哈夫曼樹，即將HuffNode數(shù)組中的各個位置的各個域都添上相關(guān)的值，并將這個結(jié)構(gòu)體數(shù)組存于文獻hfmtree.dat中。(3)、建立哈夫曼編碼的功能模塊。此模塊功能為從文獻hfmtree.dat中讀入相關(guān)的字符信息進行哈夫曼編碼，然后將結(jié)果存入codefile.dat中,同時將字符與0、1代碼串的一一相應(yīng)關(guān)系打印到屏幕上。(4)、譯碼的功能模塊。此模塊功能為接受需要譯碼的0、1代碼串，按照3中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，存入文獻textfi1e.dat,同時將翻譯的結(jié)果在屏幕上打印輸出。(5)、打印哈夫曼樹的功能模塊。此模塊功能為從HuffNode數(shù)組中讀入相關(guān)的結(jié)點信息，以圖形的方式將各個結(jié)點以及葉子結(jié)點的權(quán)值和左分支上的0和右分支上的1畫出來。四、實驗結(jié)果(程序)及分析1、實驗重要代碼typedefstructtypedefstructtypedefstruct/*結(jié)點結(jié)構(gòu)體*/typedefstruct/*結(jié)點結(jié)構(gòu)體*/stringhfmstr;stringhfmstr;/*結(jié)點內(nèi)容*/?intweightstringhfmstr;/*結(jié)點內(nèi)容*/?intweight；/*結(jié)點權(quán)值*/intparent;intIchiId;]HNodeType;typedefstructtypedefstructtypedefstruct/*typedefstruct/*編碼結(jié)構(gòu)體*/intbit[MAXBIT];intstart;)HCodeType;/*創(chuàng)建哈夫曼樹*//*創(chuàng)建哈夫曼樹*/(，intm1,x1,m2,x2;inti,j;，for(i=0;i<2*n—1;i++)。(HFMTree[i].hfmstr="";?oHFMTree[i].weight=0;o?HFMTree[i].parent=-1;。HFMTree[i].Ichild=-1;?HFMTree[i].rchiId=—1;)afor(i=0;i<n;i++)。(cout<<"請輸入第"<Vi+1<<"個權(quán)值"V<endI;docin?HFMTree[i].weight；。cout〈V"請輸入相應(yīng)字符M?endI；?。cin>>HFMTree[i].hfmstr;。｝for(i=O;i<n-1;i++)(。x1=x2=MAXVALUE;oml=m2=0;?for(j=0；j<n+i;j++)?oif(HFMTree[j].parent=-1&&HFMTree[j].weight<x1)，。。x2=x1；?oom2=m1；?oox1=HFMTree[j].weight;…m1=j;，)。o。eIseif(HFMTree[j].parent=-1&&HFMTree[j].weight<x2)，｛。。x2=HFMTree[j].weight;?am2=j;do)d0)HFMTree[m1].parent=n+i;HFMTree[m2].parent=n+i；?oHFMTree[n+i].weight=HFMTree[ml],weight+HFMTree[m2].weight；?HFMTree[n+i].IchiId=m1;?。HFMTree[n4-i].rchiId=m2;)，coutv<”創(chuàng)建哈夫曼樹成功！"?endl；)voidHaffmanCode(HNodeTypeHFMTree[],HCodeTypeHuffCode[],intn)/*構(gòu)建哈夫曼編碼*/(?HCodeTypecd;inti,j,c,p;for(i=O;i<n;i++)cd.start=n-1;c=i;p=HFMTree[c].parent;whiIe(p!=-1){if(HFMTree[p].IchiId=c)cd.bit[cd.start]=0;eIsecd.bit[cd.start]=1；cd.start—;c=p；p=HFMTree[c].parent;}for(j=cd.start+1;j<n；J4"+)HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start；))/*解碼*//*解碼*/(inti,tmp=0,code[1024];intm=2*n-1；char*nump;charnum[1024]；for(i=O;i<strlen(string);i++)if(string[i]=='O')num[i]=0;eIsenum[i]=1;)i=0；nump=&num[0]；while(nump<(&num[strlen(string)]))(tmp=m-1;while((HFMTree[tmp].Ichild!=-1)&&(HFMTree[tmp].rchild!=-1))(if(*nump==0)(tmp=HFMTree[tmp].Ichild；。)elsetmp=HFMTree[tmp].rchiId;nump