淮海工學(xué)院 數(shù)據(jù)結(jié)構(gòu) 第4次實驗

潑海工禽院針篇機(jī)科禽系實驗報告書課程名：《數(shù)據(jù)結(jié)構(gòu)》題冃：樹型數(shù)據(jù)結(jié)構(gòu)實驗班級：學(xué)號：姓名：評語：成績：指導(dǎo)教師：樹型數(shù)據(jù)結(jié)構(gòu)實驗報告要求1目的與要求：1） 熟練掌握Huffman樹的創(chuàng)建算法與編程實現(xiàn)；2） 熟練掌握Huffman編碼算法的實現(xiàn)與編程應(yīng)用；3） 創(chuàng)建較為實用的通信報文Huffman編碼系統(tǒng)和譯碼系統(tǒng)；4） 按照實驗題目要求獨立正確地完成實驗內(nèi)容（提交程序清單及相關(guān)實驗數(shù)據(jù)與運(yùn)行結(jié)果）；5） 認(rèn)真書寫實驗報告，并按時提交。2實驗內(nèi)容或題目實驗四：樹型數(shù)據(jù)結(jié)構(gòu)實驗一一創(chuàng)建通信報文編碼與譯碼系統(tǒng)構(gòu)造通信報文編碼和譯碼系統(tǒng)（要求Huffman編碼與譯碼）。條件：1、 使用英文報文實施加密通信。設(shè)組成報文的字符集為26個英文字母（不分人小寫）和兩個標(biāo)點符號字符“，”、”和一個空格字符（共29個字符）。2、 字符集中每個字符（含字母和兩個標(biāo)點符號）的使用概率自己根據(jù)英文行文合理給出（可以在網(wǎng)上查詢）。3、 以字符集中各個字符為葉結(jié)點、字符的使用頻率為權(quán)重構(gòu)造Huffman樹，并求得各個字符的Huffman編碼（參考教材P152-153教材算法6.16）。同時，輸出構(gòu)造的Huffman樹和字符編碼結(jié)果。4、 在上述通信報文編碼和譯碼系統(tǒng)中實現(xiàn)：輸入一報文原文（即使用英文書寫的一段文字或一兩句話，稱為明文），給出要發(fā)送的報文編碼（密文）；再輸入一密文（0、1序列），輸出其對應(yīng)的譯碼報文（明文）。其中報文原文或編碼序列自己設(shè)定，盡量是一句話或一段文字的對應(yīng)編碼序列,這樣可以驗證輸出結(jié)果的正確性。5、 本次實驗程序給出創(chuàng)建哈曼和哈邛曼編碼的源程序，調(diào)試運(yùn)行并實驗本次實驗的全部功能。3實驗步驟與源程序#include<stdio.h>#include<stdlib.h>#include<string.h>tvpedefchar*HuffinanCode;/*動態(tài)分配數(shù)組，存儲哈夫曼編碼tvpedefstmctunsignedmtweight;/*用來存放各個結(jié)點的權(quán)值*/unsignedmtparent,LChild,RChild;/*指向雙親、孩子結(jié)點的指針*/}HTNode,*HuffinanTree; /*動態(tài)分配數(shù)組，存儲哈夫曼樹*/voidselect(HuffinanTree*ht,*sl,mt*s2){inti;intmin;fbi(i=l;i<=n;i++){.parent==0){niiii=i;1=n+l;}}fbi(i=l;i<=n;i++){.parent==0){if((*ht)[i].weight<(*ht)[nun].weight)niiii=i;}}*sl=niiii;fbi(i=l;i<=n;i++){if((*ht)[i].parent==0&&i!=(*sl)){niiii=i;1=n+l;}}fbi(i=l;i<=n;i++)if((*ht)[i].parent==0&&i!=(*sl))if((*ht)[i].weight<(*ht)[niin].weight)niiii=i;}}*s2=niiii;}voidCrtHuffiiianTree(HufiiiianTree*ht，mt*w.mtn){/*W存放已知的n個權(quán)值，構(gòu)造哈夫曼樹lit*/intmj;intsl，s2;m=2*n-l;*ht=(HuffinanTiee)nialloc((m+l)*sizeof(HTNode));/*0號單元未使用*/foi(i=l;i<=n;i++){/*1-n號放葉子結(jié)點，初始化*/(*ht)[i].weight=w[i];(*ht)[i].LCliild=0;(*ht)[i].parent=0;(*ht)[i].RChild=0;}fbi(i=n+1;i<=m;i++){(*ht)[i].weight=0;(*ht)[i].LCliild=0;(*ht)[i].parent=0;(*ht)[i].RChild=0;} /*非葉子結(jié)點初始化*//* 初始化完畢！對應(yīng)算法步驟1 */for(i=n+1;i<=m;i++) /*創(chuàng)建非葉子結(jié)點，建哈夫曼樹*/{/*在(*ht)[l]~(*ht)[i-l]的范I制內(nèi)選擇兩個parent為0且weight最小的結(jié)點，其序號分別賦值給si、s2返回*/select(ht,i-l,&s1、&s2);(*ht)[sl].paient=i;(*ht)[s2].paient=i;(*ht)[i].LCluld=sl;(*ht)[i].RChild=s2;(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;}}/*哈夫曼樹建立完畢*/voidoutputHuffinan(HuffiiianTreeHT,mtm){if(m!=0){printf(n%dH.HT[m].weight);outputHuffiiian(HT,HT[m].LChild);outputHuffiiian(HT,HT[m].RChild);}}voidCrtHuffiiianCode(HuffiiianTree*ht,HuffiuanCode*hc,hitn)/*從葉子結(jié)點到根，逆向求每個葉子結(jié)點對應(yīng)的哈夫曼編碼*/{char*cd;inti;unsignedmtc;intstart;intp;hc=(HuffiiianCode*)malloc((n+1)*sizeof(char*));/*分配n個編碼的頭指針*/cd=(char*)nialloc(n*sizeof(chai));/*分配求當(dāng)前編碼的丁作空間*/cd[ml]=〃\0： /*從右向左逐位存放編碼，首先存放編碼結(jié)束符*/for(i=1;i<=n;i-H-)/*求n個葉子結(jié)點對應(yīng)的哈夫曼編碼*/{stait=n-l; /*初始化編碼起始指針*/fbr(c=i,p=(*ht)[i].parent;p!=0;c=p,p=(*ht)[p].parent)/*從葉子到根結(jié)點求編碼*/if((*ht)[p].LChild==c)cd[~start]=,O,;嚴(yán)左分支標(biāo)0*/elsecd[-start]=,l,;嚴(yán)右分支標(biāo)1*/hc[i]=(char*)inalloc((n-start)*sizeof(char));嚴(yán)為第i個編碼分配空間strcpy(hc[i],&cd[stait]);}fiee(cd);char*nungnia(HuffiiianTreeHTjntmxhar*ch,char*code){char*result=newchar[100];for(int1=0j=O;ch[j]!=0J++)iiiitn=m;while(HT[n].LCluld!=0&&HT[n].RChild!=0)iif(code[i]=,0,)n=HT[n].LCluld;elsen=HT[n].RCluld;i++;}result[j]=ch[n-l];}result!j]=0;returnresult;}char*niiwen(HuffinanTreeHT.intm,char*ch,char*c.HuffinanCode*code){char*result=newchar[100];result[0]=0;mtij.n=0;fbr(i=0;ch[i]!=,\0t;i++)ifor(j=0j<mj++)/Iif(c[j]==ch[i])strcat(result,code[j+l]);break;retuinresult;char*CitHuffiuanCode(HuffinanTree*ht,HuffiiianCode*hc,mtn.char*ch)char*cd;inti;intc;intstart;mtp;hc=(HuffiiianCode*)malloc((n+1)*sizeof(char*));cd=(char*)nialloc(n*siz亡oRchar));cd[ml]='\0：fbi(i=l;i<=n;i++)fistart=n-l;for(c=i,p=(*ht)[i].parent;p!=0;c=p,p=(*ht)[p].parent)if((*ht)[p].LChild=c)cd[-start]=,0,;elsecd[-start]=,r；hc[i]=(cliar*)malloc((n-start)*sizeof(char));strcpy(hc[i]、&cd[start]);}fiee(cd);fbi(i=l;i<=n;i++)printf(n%c編碼為％s\iT,ch[i?1].he[i]);charnun[100];pnntf("輸入明碼：\n");gets(nmi);char*nuwen(HuffiiianTreeHT.iiitm、char*ch?char*c,HuffinanCode*code);應(yīng)密文:\ii%s\ii,\niiwen(*ht,29jiuiLch.hc));return0;voidmain(){HuffiiianTreeHT;HuffiiianCodeHC;intn=29;ints=0;intm;charzi[29]={W；BVC\B\T7F\V：H\I\7\,K7L\,Nr^\,O\P\,Q\tR,：St；T\V,V\W/X\,Y7Z\7；.\lintw[29]={8,2A3,l,l8,24,30,7,19,11,54,30,66,71,31,19,73,75,69,36,10,12^2」7,25,72,40,12};printf(HthetotalnumberoftheHuffinanTiee:M);CnHuffiiianTree(&HTw.n);m=2*n-l;outputHuffinan(HT.m);pnnrfVW);char*hc=CrtHuff