哈夫曼樹與哈夫曼編碼

實(shí)驗(yàn)三：哈夫曼樹與哈弗曼編碼u實(shí)驗(yàn)?zāi)康模豪斫夤蚵鼧涞暮x和性質(zhì)。掌握哈夫曼樹的存儲(chǔ)結(jié)構(gòu)以及描述方法。掌握哈夫曼樹的生成方法。掌握哈夫曼編碼的一般方法，并理解其在數(shù)據(jù)通訊中的應(yīng)用。2、 實(shí)驗(yàn)內(nèi)容：哈夫曼樹與哈弗曼編碼、譯碼a?問題描述：哈夫曼問題的提出可以參考教材P.145.利用哈弗曼編碼進(jìn)行通信可以大大提高通信利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼。b.算法提示：參見教材P.147-148算法6.12、6.13的描述。3、 實(shí)驗(yàn)要求：建立哈夫曼樹，實(shí)現(xiàn)編碼，譯碼。初始化(Initialization)o從終端讀入字符集人小n,以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。編碼(Encoding)。利用已建好的哈夫曼樹(如不在內(nèi)存，則從文件hfmTree中讀入)，對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。.譯碼(Decoding)o利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。.輸出代碼文件(Print)。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePimt中。.輸出哈夫曼樹(TreePnntuig)。將已在內(nèi)存中的哈夫曼樹以直觀的方式(樹或凹入表形式)顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TieePrmt中。測(cè)試數(shù)據(jù)：設(shè)權(quán)值c=(a,b,c,d,e,f,g.h)w=(5,29,7,8,14,23,3,11),n=8°按照字符^或T，確定找左孩子或右孩子，則權(quán)值對(duì)應(yīng)的編碼為：5：0001,29：10,7：1110,8：111114：110,23：01,3：0000,11：0014、 實(shí)驗(yàn)程序：iiiclude<stdio.h>iiiclude<stdlib.h>mclude<string.h>^defineN100//赫夫曼樹和赫夫曼編碼的存儲(chǔ)表示tvpedefstmct{charch;unsignedmtweight;unsignedmtparentJchildjchild;}HTNode.*HuffiiianTree;tvpedefchar**HuffiuanCode;mtiiun(HuffiiianTree&HT,inti){〃函數(shù)voidselect()調(diào)用mtj.flag;mtk=65535;fbr(j=lJ<=ij-H-)if(HT[j].weight<k&&HT[j].parent==0)k=HT[j].weight,flag^j;HT[flag].parent=l;returnflag;voidSelect(HuffinaiiTree&HT.inti.iiit&si,mt&s2)sl=min(HT、i);s2=min(HT、i);}〃構(gòu)造赫夫曼樹HT,并求出n個(gè)字符的赫夫曼編碼HCvoidHuffinaiiCodmg(HuffinanTiee&HLHuffinanCode&HC,int*w,char*cha.iiitn)chaic;intfj,stailjn,sl,s2;HTNode*p;if(n<=l)return;m=2*n-l;HT=(HuffinanTree)malloc((m+l)*sizeof(HTNode));fbr(p=HT,-H-p4=1;i<=n;-H-i,-H-p){p->ch=cha[i];p->weight=w[i];p->paient=0;p->lcluld=0:p->icluld=0:p->weight=O;p->paient=O;p->lcluld=O:p->icluld=O:fbr(i=n+l;i<=m;++i)fSelect(HTj-l,sl,s2);HT[sl].parent=i;HT[s2].parent=i;HT[i].lchUd=sl;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;} HC=(HuffinanCode)nialloc((n+1)*sizeof(char*));char*cd=(char*)nialloc(n*sizeof(chai));cd[n-l]=^;fbr(i=l;i<=n;++i){stait=n-l;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)if(HT[f].lcluld=c)cd[—start]=,Ol;elsecd[—start]-I1;HC[i]=(char*)nialloc((n-start)*sizeof(char));strcpy(HC[i]，&cd[start]);printff字符為%c“,HT[i].ch);prmtf(n的編碼是％s\n\HC[i]);}fiee(cd);//赫夫曼譯碼函數(shù)voidDeCodmg(HuffinanTree&HT.HuffinanCode&HC,intn)charf{N]；pmitf(”請(qǐng)輸入一串字符串:\n”);getchaiQ;gets(f);inti;intm、k=0;while(f!k]!=r\0,)fbr(i=l;i<=n;i++){m=stilen(HC[i]);if(strncmp(HC[i],f^k,m)==O){k=k+m;pnntf(”輸出％s的字符是”,HC[i]);pnntf(”％c\iT,HT[i].ch);}}}voiddisplavHT(HuffinanTree&HT.intn.iiitm){Hiti；pmitf("打印赫夫曼HC存儲(chǔ)結(jié)構(gòu)\n");pmitf(”編號(hào)字符權(quán)重雙親左孩子右孩子\n”)；foi(i=l;i<=n;i-H-)pmHfT%d\t%c\t%d\t%d\t%d\t%d\ir丄HT[i]?chHT[i]?weight?HT[i]?paimrHT[i]?lcluld?HT[i].rcliild);for(i=n+1;i<=m;i-H-)\t%d\t%d\t%d\t%d'ii,\i.HT[i].weight,HT[i].parent.HT[i].lcliild.HT[i].rchild);}main(){HuffiiianTreeHT;HuffiiianCodeHC;iiitnj;printfC*********建赫夫曼樹，編碼和譯碼程序**************?);printf("\n輸入建赫夫曼樹元素的個(gè)數(shù)：")；scanf(”％d役&n);iiitm=2*n-l;chaicha[9];intw[9];fdr(i=l;i<=n;i++){pimtf(n?%d個(gè)元素=>字母和權(quán)重getchar();scanf(”％c%d",&cha[i],&w[i]);}HuffiiianCoding(HLHC,w,cha.n);displayHT(HTjian);

DeCoding(HLHCai);return0;}5、輸出結(jié)果:丁?* ■塢號(hào)宇符權(quán)重雙更1a592b29143c7104d8105e14126f2313?g398h11119811101