2023年新版哈夫曼樹(shù)實(shí)驗(yàn)報(bào)告

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

此功能模塊的功能為從鍵盤(pán)接受字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值。(2)、建立哈夫曼樹(shù)的功能模塊。此模塊功能為使用1中得到的數(shù)據(jù)按照教材中的構(gòu)造哈夫曼樹(shù)的算法構(gòu)造哈夫曼樹(shù)，即將HuffNode數(shù)組中的各個(gè)位置的各個(gè)域都添上相關(guān)的值，并將這個(gè)結(jié)構(gòu)體數(shù)組存于文獻(xiàn)hfmtree.dat中。(3)、建立哈夫曼編碼的功能模塊。此模塊功能為從文獻(xiàn)hfmtree.dat中讀入相關(guān)的字符信息進(jìn)行哈夫曼編碼，然后將結(jié)果存入codefile.dat中,同時(shí)將字符與0、1代碼串的一一相應(yīng)關(guān)系打印到屏幕上。(4)、譯碼的功能模塊。此模塊功能為接受需要譯碼的0、1代碼串，按照3中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，存入文獻(xiàn)textfi1e.dat,同時(shí)將翻譯的結(jié)果在屏幕上打印輸出。(5)、打印哈夫曼樹(shù)的功能模塊。此模塊功能為從HuffNode數(shù)組中讀入相關(guān)的結(jié)點(diǎn)信息，以圖形的方式將各個(gè)結(jié)點(diǎn)以及葉子結(jié)點(diǎn)的權(quán)值和左分支上的0和右分支上的1畫(huà)出來(lái)。四、實(shí)驗(yàn)結(jié)果(程序)及分析1、實(shí)驗(yàn)重要代碼typedefstructtypedefstructtypedefstruct/*結(jié)點(diǎn)結(jié)構(gòu)體*/typedefstruct/*結(jié)點(diǎn)結(jié)構(gòu)體*/stringhfmstr;stringhfmstr;/*結(jié)點(diǎn)內(nèi)容*/?intweightstringhfmstr;/*結(jié)點(diǎn)內(nèi)容*/?intweight；/*結(jié)點(diǎn)權(quán)值*/intparent;intIchiId;]HNodeType;typedefstructtypedefstructtypedefstruct/*typedefstruct/*編碼結(jié)構(gòu)體*/intbit[MAXBIT];intstart;)HCodeType;/*創(chuàng)建哈夫曼樹(shù)*//*創(chuàng)建哈夫曼樹(shù)*/(，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<<"請(qǐng)輸入第"<Vi+1<<"個(gè)權(quán)值"V<endI;docin?HFMTree[i].weight；。cout〈V"請(qǐng)輸入相應(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)建哈夫曼樹(shù)成功！"?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