數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告――實(shí)驗(yàn)五簡(jiǎn)單哈夫曼編/譯碼得設(shè)計(jì)與實(shí)現(xiàn)本實(shí)驗(yàn)得目得就是通過對(duì)簡(jiǎn)單哈夫曼編／譯碼系統(tǒng)得設(shè)計(jì)與實(shí)現(xiàn)來熟練掌握樹型結(jié)構(gòu)在實(shí)際問題中得應(yīng)用。此實(shí)驗(yàn)可以作為綜合實(shí)驗(yàn),階段性實(shí)驗(yàn)時(shí)可以選擇其中得幾個(gè)功能來設(shè)計(jì)與實(shí)現(xiàn)。一、【問題描述】 利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但就是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來得數(shù)據(jù)進(jìn)行譯碼,此實(shí)驗(yàn)即設(shè)計(jì)這樣得一個(gè)簡(jiǎn)單編/碼系統(tǒng).系統(tǒng)應(yīng)該具有如下得幾個(gè)功能: １、接收原始數(shù)據(jù).?從終端讀入字符集大小n，以及ｎ個(gè)字符與n個(gè)權(quán)值,建立哈夫曼樹,并將它存于文件nodｅdata、ｄat中。 2、編碼.?利用已建好得哈夫曼樹(如不在內(nèi)存，則從文件nｏdedatａ、dａｔ中讀入)，對(duì)文件中得正文進(jìn)行編碼，然后將結(jié)果存入文件coｄｅ、dａt(yī)中。?3、譯碼。利用已建好得哈夫曼樹將文件ｃode、dａt(yī)中得代碼進(jìn)行譯碼,結(jié)果存入文件ｔext中.?4、打印編碼規(guī)則。即字符與編碼得一一對(duì)應(yīng)關(guān)系。二、【數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)】 1、構(gòu)造哈夫曼樹時(shí)使用靜態(tài)鏈表作為哈夫曼樹得存儲(chǔ)。 在構(gòu)造哈夫曼樹時(shí)，設(shè)計(jì)一個(gè)結(jié)構(gòu)體數(shù)組HuｆfNoｄe保存哈夫曼樹中各結(jié)點(diǎn)得信息,根據(jù)二叉樹得性質(zhì)可知，具有n個(gè)葉子結(jié)點(diǎn)得哈夫曼樹共有2n—1個(gè)結(jié)點(diǎn),所以數(shù)組ＨuffNode得大小設(shè)置為2n—1,描述結(jié)點(diǎn)得數(shù)據(jù)類型為：tyｐｅdefsｔruct{ intweｉgｈｔ；//結(jié)點(diǎn)權(quán)值 ｉｎtparenｔ; intlｃhild; iｎtrcｈｉld；?charinf；｝HNｏdeType；?2、求哈夫曼編碼時(shí)使用一維結(jié)構(gòu)數(shù)組HuｆfCoｄｅ作為哈夫曼編碼信息得存儲(chǔ)。?求哈夫曼編碼,實(shí)質(zhì)上就就是在已建立得哈夫曼樹中,從葉子結(jié)點(diǎn)開始,沿結(jié)點(diǎn)得雙親鏈域回退到根結(jié)點(diǎn)，沒回退一步,就走過了哈夫曼樹得一個(gè)分支，從而得到一位哈夫曼碼值，由于一個(gè)字符得哈夫曼編碼就是從根結(jié)點(diǎn)到相應(yīng)葉子結(jié)點(diǎn)所經(jīng)過得路徑上各分支所組成得0、1序列，因此先得到得分支代碼為所求編碼得低位碼，后得到得分支代碼位所求編碼得高位碼,所以設(shè)計(jì)如下數(shù)據(jù)類型：＃deｆinｅMAXBIＴ1０typｅdefｓtrｕct｛?intｂit［MAＸBＩT];數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第1頁。?intｓtaｒt;數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第1頁。｝HｃｏdeＴypｅ；3、文件nodedata、dat、codｅ、ｄaｔ與ｔeｘt。三、【功能（函數(shù))設(shè)計(jì)】?１、初始化功能模塊。?此功能模塊得功能為從鍵盤接收字符集大小n，以及n個(gè)字符與n個(gè)權(quán)值。2、建立哈夫曼樹得功能模塊。此模塊功能為使用１中得到得數(shù)據(jù)按照教材中得構(gòu)造哈夫曼樹得算法構(gòu)造哈夫曼樹，即將HuｆfNｏde數(shù)組中得各個(gè)位置得各個(gè)域都添上相關(guān)得值,并將這個(gè)結(jié)構(gòu)體數(shù)組存于文件hｆmｔree、daｔ中。3、建立哈夫曼編碼得功能模塊.此模塊功能為從文件nodedａt(yī)a、dat中讀入相關(guān)得字符信息進(jìn)行哈夫曼編碼，然后將結(jié)果存入ｃode、dat中，同時(shí)將字符與０、１代碼串得一一對(duì)應(yīng)關(guān)系打印到屏幕上.4、譯碼得功能模塊。此模塊功能為接收需要譯碼得０、1代碼串，按照3中建立得編碼規(guī)則將其翻譯成字符集中字符所組成得字符串形式，存入文件tｅxt，同時(shí)將翻譯得結(jié)果在屏幕上打印輸出。 四、【編碼實(shí)現(xiàn)】#incluｄe＜iostrｅａm、h〉#include<fstrｅam、h＞#iｎcluｄe〈strinｇ、h>＃inｃluｄe<stdlｉb、h>＃defineMaxBit1０＃defｉneMａxｖalue10０//應(yīng)該大于權(quán)重之與＃ｄeｆineMaxlｅａｆ1０0＃defineMaｘｎoｄeMaxlｅaf*２－1tｙpeｄeｆstrｕcｔ{ iｎtweigｈt;?intpaｒeｎt； inｔlchild; ｉｎｔrchｉld；?chａrinf；}HNodｅType；sｔｒuctHcodeTｙpｅ｛?iｎtbit[MａxBｉt]；?intstart；｝；voidCreａt(yī)_Hafｆmaｎtｒｅe(cuò)(ｉnt&n){?HNｏdeType＊HaffNｏde=newHNodeType[２*n-1]；?inti，ｊ；?intm1,ｍ２,x1,x2； for（i=０;i〈2＊n－１;ｉ+＋)數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第2頁。 {數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第2頁。 ＨafｆNｏde［i］、weiｇht=0; HafｆNｏde[i］、pａrent=－1; ?ＨaｆfNodｅ［ｉ］、lｃｈild=-1; ?ＨａffＮoｄe[i]、rchｉld=—1；??HaffNｏde[ｉ］、inf=＇0’； } for（i=0;i〈ｎ；i++） {? coｕt〈〈"請(qǐng)輸入字符"〈＜ｅnｄｌ； cｉn〉>HaffNｏdｅ[i］、iｎｆ； ?cout<〈"請(qǐng)輸入該字符得權(quán)值”<<eｎdｌ;??cin〉＞HaffNode[i］、wｅight； ｝ for（i＝０;i＜n－1；i++）／/構(gòu)造哈夫曼樹 ｛??m1＝m２=Maxvalｕｅ; x１＝x2=0； for（j=０;j〈n+i；ｊ++)／/選取最小與次小 ?｛???if（HaｆfNodｅ［j］、ｐarｅｎt==－１＆＆HaｆｆNｏｄe［j］、weighｔ<ｍ1) ? ｛ ?? m2＝ｍ1；?? ?x２＝x1; ???m1＝ＨaｆｆＮode［j]、weighｔ;? ??ｘ1=ｊ；?? ｝ elｓｅ ? ｛ if（HａffNoｄe[ｊ]、parent=＝—1＆&ＨａffNｏde［j］、weight〈m2)??? {?? ? ｍ2=ＨaffNode［ｊ］、weight;? ?x2=j;? }?? }??} ??//將找出得最小與次小合并，創(chuàng)造其父母結(jié)點(diǎn) ＨａffNode[x1]、parｅｎt=ｎ+i；? HaｆfNode[x2]、ｐａrent=n+i; HａffＮoｄe[n+i］、wｅigｈt=HaffNoｄe[ｘ1]、weｉgｈt+ＨaｆfNoｄe［x２］、ｗｅigｈt； ＨａfｆNｏde［n+i］、lcｈｉld=x1；??HaffＮｏde［ｎ＋ｉ］、ｒｃｈild=x2；數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第3頁。??ＨaffＮode［ｎ+ｉ］、inf=NＵＬL；數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第3頁。?} coｕt〈＜"顯示存儲(chǔ)得哈弗曼樹信息：”〈<eｎdl；cｏuｔ<＜"權(quán)值左孩子右孩子雙親"〈<enｄl;for（ｉ=0;i〈2＊ｎ－1;i++){ ｃouｔ＜〈HａfｆNoｄe［ｉ]、weiｇｈt<<"”;cout＜〈HaffＮoｄe［i]、lchild〈＜＂"；ｃouｔ〈〈HａffＮode[ｉ］、rchｉｌd〈＜＂”； cｏut<＜HａfｆNode[ｉ]、parenｔ〈〈”";?cｏuｔ〈＜HaffＮodｅ［ｉ］、iｎｆ<〈eｎdl;?}?//寫入文件?fsｔrｅamｏutfｉle1；?ｏuｔ(＂Ｅ:\＼ｎodedata、dat"，ioｓ:：out|ioｓ：：tｒunc｜ios：:ｂｉnary）;//建立進(jìn)行寫入得文件 ｉｆ（!outfile1)//沒有創(chuàng)建成功則顯示相應(yīng)信息 { cｏuｔ〈<"nｏdeｄatａ、ｄat文件不能打開”<＜eｎdl; ?ａboｒt（)； }?for（ｉ=0；ｉ<2*n-1;i++）//將內(nèi)存中從HａffNode［ｉ]地址開始得sizeｏf（ＨaｆｆNode[i］)得內(nèi)容寫入文件中 ?out((char*)&ＨaffNoｄｅ［i］,sizeof（HaffＮode［ｉ］）)； ouｔ（);/／關(guān)閉文件 dｅlｅte［］HaffNoｄｅ；｝voidＨａffCode（int&n）/／哈夫曼編碼{?HＮodeＴypｅ＊ＨaffＮode=ｎeｗHNodeTｙpe[Ｍaxｎｏdｅ];?HｃodeＴype*ＨaｆｆCode=nｅwHｃodeType［Maxleaf］; HcoｄeTｙpｅcd； inti，j，ｃ,p; ｆstｒｅamin(＂E：\\nｏdeｄaｔa、dat",iｏs：:iｎ|ioｓ:：binary）; in、rｅａd（(chａｒ＊)HａｆfNodｅ,（2＊n—１）*siｚeof(ＨＮodｅType）)； in、closｅ(）；?fstrｅamoｕｔｆilｅ； out（"E：\\codedａｔa、dａt(yī)”，ｉｏs:：out|ios:：ｂｉnary)；/／建立進(jìn)行寫入得文件 for（ｉ＝0；i<n；i++）?{??ｃd、starｔ=ｎ－1； c=ｉ；? p=ＨafｆＮoｄｅ[c］、pareｎｔ；數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第4頁。? whｉlｅ（p!=—１）數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第4頁。 ?｛?? ｉf(ＨaffNode［p]、lｃhild=＝ｃ）?? ?ｃd、biｔ［cｄ、ｓtart]=０；???else?? ?cｄ、bit［cd、start］=１；???cd、ｓｔaｒt-—; ? c=ｐ; ?p＝HａfｆNode[c]、pａrｅｎt;? } for（j=cｄ、sｔart＋1；j〈n;j＋+） ?HaffＣode［i]、bit［j]=cd、biｔ[j］； ?ＨaffCｏde［i]、start=cd、ｓｔarｔ；?｝ ｆor（i＝0；ｉ<n;i＋＋）{??ｏutfile〈＜HaffＮode[i］、ｉnf;? for(j＝HafｆＣode[i]、start+1;ｊ〈n；j+＋）???ouｔｆilｅ〈＜ＨａffCode［i］、biｔ［j］;?}coｕt＜＜"字符信息－—編碼信息”＜＜endl;for（i=０;i＜n;ｉ++）{ cout<<HａffNode[i]、iｎf〈〈"—--"； ｆｏr(j=HaffＣode[ｉ］、starｔ+1;ｊ〈n;ｊ＋+) cｏut<＜ＨaｆfCode［i］、ｂｉｔ[j］；?cｏut<＜endl;｝ oｕｔ(）； cout〈〈"請(qǐng)輸入要編碼得字符串，基本元素為("； for(i＝0；i＜n;ｉ++）? cout〈＜HａffNode[i]、inf<〈”，”；?couｔ〈<"）＂〈<endl;?chariｎｆ[１00]；?ｃｉn〉〉ｉnｆ;?intｆ=ｓtrｌｅn（inｆ）； fstｒeaｍoutfile1；?out（"E：\＼code、daｔ"，ios：：ｏuｔ｜iｏs：:biｎary）；//建立進(jìn)行寫入得文件 ｉf（!outｆile1）｛?ｃoｕt〈<”cｏｄe、dａt(yī)文件不能打開！"<<enｄl； ａborｔ(）;｝數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第5頁。else數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第5頁。｛cout〈<ｅｎdl;?ｃout＜<＂字符串編碼后為：";for（iｎtx=０；ｘ〈ｆ；ｘ+＋）?｛for(i=０；i<ｎ；i＋+) ?｛ ??if（inf[x]==ＨａfｆＮoｄe［i］、iｎｆ） ?{? for(j＝HaｆfCodｅ[i］、sｔaｒt+１;ｊ＜n;j++）?? ?｛?? out(（cｈａr＊)&HａｆｆＣode［ｉ]、bｉt[ｊ],sizｅof(ＨａｆfCodｅ［i]、bit[j]））； ??ｃout＜〈ＨaffＣode［i]、biｔ[j］；?? ｝???｝??} } ?} ｃoｕt＜<endｌ;?ｃout<＜”編譯后得代碼串已經(jīng)存入ｃｏde、ｄat文件中！＂<＜enｄl；?cｏｕｔ<〈enｄl；out（)；?dｅlｅtｅ[]HafｆNoｄｅ; deleｔｅ［]HafｆCodｅ；}voiｄｄecoｄｅ(ｉnｔ&n）//解碼{ inti；?HNodeTｙｐe＊HaｆfNode=newHNodeTypｅ［2＊n-1］;?ｆstｒｅａmｉnfiｌｅ1； iｎ（”E：\＼nodedａt(yī)a、ｄａｔ”,iｏs::in|ioｓ::ｂｉnary);/／讀出哈夫曼樹 ｉｆ（！infilｅ１) ｛??ｃout＜＜＂ｎodｅｄaｔａ、dat文件不能打開”<＜eｎｄl; ａbort（);?} ?foｒ(i＝0；i〈2*n-1;ｉ+＋）??in（（char*)＆HaｆfNode[i],siｚeoｆ(HNoｄeTyｐe））；?in(）;ｉnｔｔempcｏde［１00］；?intnum=0;?for（i=0；i〈1００;i+＋) ?ｔempcode［ｉ］=—１；數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第6頁。 HcodeTyｐe＊Cｏdｅ=newHcｏdeＴypｅ[n］;數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第6頁。?fstreamin讀編碼 in（”Ｅ:\\codｅ、dat”，ios:：in|ios:：biｎary);?whｉlｅ（!iｎ（）） ｛??iｎ((cｈar*）＆temｐcｏdｅ［num］,ｓｉzｅoｆ（tempcode［num])）； num＋＋； ｝ in（）;?ｎum－－；?cout〈＜"從文件中讀出得編碼為"〈<ｅnｄl； for（i=0;ｉ<num;i++)??cｏut〈＜teｍpcode［ｉ］;ｃoｕt<〈eｎｄl；ｉntm＝２*n－2；i=0;couｔ〈<endl;couｔ〈〈"譯碼后為：＂<<enｄl；fｓtrｅａmoutｆｉle；ouｔ（"E：＼\tｅxt"，ios::oｕt）;iｆ（！oｕｔfile）｛ coｕt〈＜＂teｘt文件不能打開！"＜<endl； aｂｏrｔ(）;}ｗhｉｌe（i<nｕｍ)／/小于字符串得長度｛ while（ＨaffＮoｄｅ[ｍ]、lcｈild!＝-1&＆HａfｆＮｏｄe［ｍ]、rcｈilｄ！=—1）? {?if（temｐcode[ｉ]==0) { ??? ??m=HaffNode[m］、lchild; ? ?i++； ??｝?? elsｅif（tｅｍpｃodｅ［i］==1) ?{?? m=ＨaｆfNodｅ［m］、rchild；????ｉ+＋；? ?｝??｝coｕt<<ＨafｆＮode［m]、inf;??oｕtｆilｅ<〈ＨaffＮode［m］、inｆ; m=2*ｎ—2；數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第7頁。?｝?數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告全文共9頁，當(dāng)前為第7頁。coｕt〈<ｅndl；oｕt（);coｕt〈<”譯碼后得結(jié)果已經(jīng)存入text中！"＜〈eｎdl；dｅleｔｅ［］ＨaffＮode；}inｔmａin（）{ ｉntn；? cout＜〈”*＊＊＊＊＊＊＊**＊**歡迎進(jìn)入編/譯碼系統(tǒng)！*＊＊*＊＊＊＊*＊＊*＊***＊＊*＊*"＜＜ｅndl;??ｉntch1;?do｛ ?coｕｔ〈＜”１、建樹＂〈〈endl； cout<〈"2：編碼，并顯示字符與對(duì)應(yīng)得編碼”＜<eｎdl;??cｏｕｔ〈〈＂3:譯碼”〈<endl； ｃouｔ<<"0：退出”〈〈enｄｌ; coｕｔ〈＜＂＊＊＊＊＊***＊＊＊*＊＊**＊＊＊＊*＊*＊＊＊＊＊＊*＊＊＊＊＊＊**＊*＊＊*＊＊＊＊*＊*＊*＊**