2023年數(shù)據(jù)結(jié)構(gòu)哈夫曼樹的實驗報告

軟件學院設(shè)計性實驗報告專業(yè):網(wǎng)絡(luò)工程年級/班級:2023—2023學年第一學期課程名稱數(shù)據(jù)結(jié)構(gòu)指導教師本組成員學號姓名實驗地點實驗時間項目名稱哈夫曼編／譯碼系統(tǒng)的設(shè)計與實現(xiàn)實驗類型設(shè)計性實驗目的理解哈夫曼樹的特性及其應用；在對哈夫曼樹進行理解的基礎(chǔ)上，構(gòu)造哈夫曼樹,并用構(gòu)造的哈夫曼樹進行編碼和譯碼;通過該實驗,使學生對數(shù)據(jù)結(jié)構(gòu)的應用有更深層次的理解。實驗儀器或設(shè)備學院提供公共機房,１臺／學生微型計算機?？傮w設(shè)計（設(shè)計原理、設(shè)計方案及流程等）1．問題描述：運用哈夫曼編碼進行通信可以大大提高信道運用率，縮短信息傳輸時間,減少傳輸成本。但是，這規(guī)定在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接受端將傳來的數(shù)據(jù)進行譯碼(解碼)。對于雙工信道(即可以雙向傳輸信息的信道）,每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站設(shè)計一個哈夫曼編/譯碼系統(tǒng)。2.一個完整的系統(tǒng)應具有以下功能：１）初始化(Initiaｌｚａt(yī)iｏn)。從數(shù)據(jù)文獻DaｔaＦｉle.dａt(yī)中讀入字符及每個字符的權(quán)值，建立哈夫曼樹HｕｆfTrｅe;2)編碼(EnCｏｄｉng）。用已建好的哈夫曼樹,對文獻ToBeTrａn．dat中的文本進行編碼形成報文，將報文寫在文獻Code．txt中；３）譯碼（Decodinｇ）。運用已建好的哈夫曼樹,對文獻CoｄeFiｌe．dat中的代碼進行解碼形成原文，結(jié)果存入文獻Textfilｅ.txt中；4)輸出(Output）:輸出DataFｉle.ｄat中出現(xiàn)的字符以及各字符出現(xiàn)的頻度(或概率)；輸出ＴｏＢeTran.ｄat及其報文Ｃode.txｔ；輸出ＣodｅFｉle.dat及其原文Teｘtfiｌe.txt;規(guī)定:所設(shè)計的系統(tǒng)應能在程序執(zhí)行的過程中,根據(jù)實際情況(不同的輸入)建立DａｔaFile.daｔ、ToBeＴran.dat和ＣodｅFiｌe.dat三個文獻,以保證系統(tǒng)的通用性。實驗環(huán)節(jié)(涉及重要環(huán)節(jié)、代碼分析等）１）編寫C語言程序#iｎｃlｕde<stｒｉｎｇ.h＞＃ｉncｌude<mａlloｃ.h>#include<stｄｉo.h>#inｃlｕｄｅ<ｉostreａｍ.h>#iｎclude<matｈ.ｈ>#defｉneTRUE1＃dｅfineFALＳE0#defiｎeOK1＃defineERROR0＃ｄeｆｉnｅIＮFEASＩBLE-1tｙpｅｄefsｔruct{?ｃｈａｒdata; intwｅight;?inｔpａrｅnt,ｌchild,rchｉlｄ;}HTNodｅ,*HuffmanＴree;ｔypedｅｆcｈar＊*HuffmaｎCode；ｖoiｄＨuffｍanCodｉng(HuffmａnTree＆ＨT,ＨuffmａｎCode＆ＨＣ，chａr*ｄ,int＊w，ｉnｔn)//構(gòu)造哈弗曼函數(shù)HT,構(gòu)造編碼HＣ{ｖｏiｄｓｅlｅｃｔ(ＨｕfｆmanTrｅeHT,inｔn,int&s1,iｎt&ｓ2);?iｎtｍ,c,f,j; HｕffmanＴreeｐ; intｉ,s１，s2,start； char*ｃd; m=2＊n-1；/／m為結(jié)點數(shù)，ｎ為葉子數(shù)HT＝(HuffmanTｒｅｅ)ｍａlloｃ（(m+1)*siｚｅof(ＨTNoｄe));?p＝HＴ;?p++; fｏr(i=１;i＜=n;i++,p+＋)//將葉子的值輸入HT中 {p->data=ｄ[i］；／/＝{*ｄ,*ｗ,０,0,0}; p-＞ｗeighｔ=w[ｉ］;??p－＞pａrｅnt=0；? ｐ-＞lchild=０；??p->rchｉld=0; ｝foｒ(i=n+1;i<=ｍ;i+＋,p++)/／={'#',0,0,0,0｝ { ?p->ｄata＝＇＃'; p－>wｅight＝0；? p->ｐarｅｎｔ=0； p->ｌchild=0;??p->rchild=0; }?s1=１; ｓ2=2； for(ｉ=n+1;i<=m;i＋+)//構(gòu)建哈夫曼樹?{? sｅlｅｃt（HT,ｉ-１，s１,s2); HT[i].lchilｄ＝s1; ＨT［i]．rchiｌd=s2；??ＨT［ｉ].weigｈt=HT[s1]．ｗeighｔ+HT[ｓ2].ｗeigｈｔ;??HT［ｓ1].parｅnｔ=i； HT[ｓ2］.pａｒent=i;?}?HC=(HuｆfmanＣｏde）malloc((n+１)*sizeof(HuffmanTreｅ));/／開辟空間,編碼?cd=(cｈar*)ｍallｏc（n*sizeof(char));cd[ｎ-1]='\0'；fｏr（i=1;i＜=n;++ｉ）?{ ?start=n-1; ｆor(c=ｉ,ｆ=HT［i].parent;f！=0;c=ｆ,f=HT[f].paｒent)? {? if(HT[f]．lchild==ｃ）? cd[－－sｔart］='0'; ? else cd［--sｔarｔ]='１';? } ?HＣ[i]=(ｃhar*)malloc（(n-ｓtaｒｔ）*ｓizeof（char）)； sｔrcｐy(ＨC[i］,&cd［start]）;? ?priｎtf("％c的編碼是:＂,ＨＴ[i］）;? puｔs(HC［ｉ])；} free(cｄ)；｝vｏidselect(HufｆmａnTreeHT,intn,int&s1,int&s2）/／求最小兩數(shù){?iｎti,t;?s１＝1；?s２=2;?ｗhｉle（HＴ［ｓ１］.pａrent!=0) s1++;?wｈｉle(（HT［s2].paｒent!=0)|｜(ｓ1==s2))??s2++;／*foｒ(i=1;i＜＝ｎ;i++）?｛ ｉf(HT［s1]．ｗｅighｔ＞HT[i].wｅight&&ＨT[i]．ｐａrent==0&&s2!＝ｉ) ?s1=i;?} iｆ（HT[ｓ１]．wｅiｇht＞HT[ｓ2].ｗeight) {? t=s1; s1=s２; s2=ｔ;?｝ for(i=1;ｉ<=ｎ;i+＋） { if（ｓ1!=i)??{? if(HT［s２].weｉght>HT[i].weight&＆ＨＴ[ｉ］．parent==0） ? ｓ2=i; }?｝*/ fｏr(i=1;i<=ｎ；ｉ＋+)?｛ if(s1!=ｉ&&i!=s2）? { if(HT[i].weｉghｔ＜ＨT［s1]．ｗeigｈｔ&&HT［i］.parent==0&＆i!＝s2) { ? ?iｆ（HT[s1].weｉght＜HT[s2].ｗeight）ｓ2＝s１;? s1=i; ? }??eｌse?? if(HT[i].wｅiｇht＜HT[s2].wｅigｈｔ&&HT[i].parent==0&&s1！=i）?s2=i; ?}?｝}voidｔrａnｓｌatioｎ(HｕffmanTreeHT,inｔnum){ charstr[２0];?ｉnｔi，t=nｕm;?pｒintf("請輸入由0或1組成的編碼："）；?cin>>str;?//t＝HT；/／ｔ為樹的指向各節(jié)點的指針?foｒ(i=0;i<(strｌeｎ(sｔｒ)）；ｉ++)?｛ if（sｔr[i]=＝'０')?? t＝HT［t].lchild； ?eｌsｅ ?if(stｒ[i］=='1＇)?? t＝HT[ｔ]．rｃhild;? ｅｌsｅ?? {?? pｒiｎtf("編碼輸入錯誤＂)； ?ｂrｅak; ? }?if（！(HＴ［t].lchild＆&ＨＴ［t］．rchilｄ）) {??prinｔf("%c",HT［t]．data); ??t=nuｍ;??} } prinｔf("\n"）;}voidｍain(){?ｖoｉｄHｕffmａｎCｏdinｇ(HuffｍａnＴrｅe&HT,HuffmanCoｄe&HC,cｈard[],iｎtw［],intn);?vｏidtranslaｔiｏn(ＨufｆｍａｎＴreｅHT,iｎtｎｕm); ＨuｆfmanTｒeｅHT=NULL; HuffｍanＣodeＨC=NULL;?chardａt(yī)a，n,*p,*d; iｎt＊w,wei，i,ｎuｍ； prｉntf（＂pleaseｉntpｕｔｃhａracｔerｎｕmｂer：＂）;?scanf(＂％d"，&n);?d=(chａｒ*)maｌloｃ((ｎ+1)*sｉｚeof(ｃhar)）；?w=(int＊)maｌloc((n+1）＊ｓiｚeof(iｎｔ)）;pｒintf(＂請輸入Hufｆｍａn樹中的字符:＼ｎ"); for（ｉ=1；ｉ＜＝ｎ；i+＋)?{? cｉn＞＞ｄata; d［ｉ]=daｔa; }?priｎtｆ("請輸入%d次位權(quán)＼n:"，n);ｆｏｒ(ｉ=１;ｉ<=n;i＋＋)?｛??cin>>wei; w[i］=wei;?} num=2*n－1;ＨuｆfｍaｎCoｄiｎg(HT,HC,ｄ,w,n); tｒanｓlation(ＨT,nｕm);}程序分析此實驗是構(gòu)造哈夫曼樹，求出哈夫曼編碼然后輸出構(gòu)造哈夫曼樹的算法操作時選出兩棵根節(jié)點的權(quán)值最小的一顆樹的左右子樹，且置新樹的根節(jié)點的權(quán)值為其左右子樹上根節(jié)點的權(quán)值之和，根據(jù)哈夫曼樹求出帶權(quán)途徑的算法操作是用遞歸調(diào)用的方法。在此實驗的操作過程中要注意構(gòu)造哈夫曼樹的方法,由于在此操作的過程中用的的指針變量特