哈弗曼編碼實(shí)驗(yàn)報(bào)告

華北科技學(xué)院計(jì)算機(jī)系綜合性實(shí)驗(yàn)報(bào)告PAGE 第9頁(yè)華北科技學(xué)院計(jì)算機(jī)系綜合性實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)學(xué)期2010至2011學(xué)年第2學(xué)期學(xué)生所在系部管理系年級(jí)2009級(jí)專業(yè)班級(jí)電商B092學(xué)生姓名劉偉學(xué)號(hào)200904064221任課教師蘭蕓實(shí)驗(yàn)成績(jī)計(jì)算機(jī)系制

《數(shù)據(jù)結(jié)構(gòu)B》課程綜合性實(shí)驗(yàn)報(bào)告開(kāi)課實(shí)驗(yàn)室：基礎(chǔ)六年月日實(shí)驗(yàn)題目哈夫曼編碼的實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康?、掌握線性鏈表的插入、刪除等算法。3、掌握Huffman樹(shù)的概念及構(gòu)造方法。4、掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及遍歷算法。5、構(gòu)造Huffman樹(shù)及Huffman編碼二、設(shè)備與環(huán)境微型計(jì)算機(jī)、Windows系列操作系統(tǒng)、VisualC++6.0軟件三、實(shí)驗(yàn)內(nèi)容根據(jù)字符出現(xiàn)的頻率情況，創(chuàng)建Haffman樹(shù)，再將各字符對(duì)應(yīng)的哈夫曼編碼顯示在屏幕上四、實(shí)驗(yàn)結(jié)果及分析實(shí)驗(yàn)過(guò)程（圖）： 赫夫曼編碼樹(shù)seletemintwoval GenbinoryTree子函數(shù)子函數(shù)HuffmanTree生成赫夫曼樹(shù) 輸出權(quán)值 輸出赫夫曼編碼及實(shí)現(xiàn)了譯碼功能測(cè)試截圖:代碼分析:#include<stdio.h>#include<string.h>#defineMIN50;typedefstructHnode{ charval; intleft; intright; intparent; intweight; intside; intvisted;}Hnode;HnodeH[60];intindex[2];voidseletemintwoval(intn) //選兩個(gè)最小值{ inti,j,min; for(j=0;j<2;j++) {min=MIN; for(i=0;i<n;i++) { if(H[i].visted==0&&H[i].weight<=min) { min=H[i].weight; index[j]=i; } } H[index[j]].visted=1; }}intGenbinoryTree(intn) //用選出的兩個(gè)結(jié)點(diǎn)構(gòu)成二叉樹(shù){ H[n].left=index[0];H[n].right=index[1]; H[n].weight=H[index[0]].weight+H[index[1]].weight;H[index[0]].parent=n;H[index[0]].side=0; H[index[1]].parent=n; H[index[1]].side=1; n++; return(n);}intHuffmanTree(ints) //生成哈夫曼樹(shù){ intn=s; intcount=s; while(count>1) {seletemintwoval(n); n=GenbinoryTree(n); count--; } returnn;}voidOutputHcoding(chardoc[],intw,intk,intn) //輸出編碼{ inti,j[20],p,q,t=0; intc[20][20]; for(i=0;i<n;i++) { p=i; if(H[p].left==-1&&H[p].right==-1) { printf("%c對(duì)應(yīng)的的編碼是:",H[p].val); j[t]=0; while(H[p].parent!=-1)//從葉子節(jié)點(diǎn)開(kāi)始檢查，用數(shù)組代替棧 { c[t][j[t]]=H[p].side; j[t]++; p=H[p].parent; } for(q=j[t]-1;q>=0;q--)//將數(shù)組從后往前輸出以實(shí)現(xiàn)棧的功能 printf("%d",c[t][q]); printf("\n"); t++; } } printf("所輸入字母序列的編碼為：\n"); for(i=0;i<w;i++) { for(p=0;p<k;p++) { if(doc[i]==H[p].val) { for(q=j[p]-1;q>=0;q--) printf("%d",c[p][q]); } } } printf("\n");}voidTranslate(intn) //譯碼{ inti,x,y,N=0; chara[30]; intb[30]; printf("請(qǐng)輸入'0'、'1'編碼序列用于譯碼:\n"); gets(a); while(a[N]!='\0') { b[N]=(int)a[N]%2; N++; } for(i=0;i<n;i++) { if(H[i].parent==-1) { x=i; y=x; } } printf("該字母序列的譯碼為：\n");for(i=0;i<N;i++) { if(b[i]==0)x=H[x].left; if(b[i]==1)x=H[x].right;if(H[x].left==-1&&H[x].right==-1) { printf("%c",H[x].val); x=y; } } printf("\n");}voidmain(){ chardoc[30]; intt=0,k=0,count=0; inti,j,n; intd[30][26]; intsum[26]={0}; charb[26]; for(i=0;i<26;i++) { b[i]='a'+i; } for(i=0;i<20;i++) { H[i].left=H[i].right=H[i].parent=H[i].side=-1;//初始化樹(shù)節(jié)點(diǎn) H[i].visted=0; } printf("請(qǐng)輸入用于編碼的字母序列:\n");gets(doc); while(doc[t]!='\0') { t++; } for(i=0;i<t;i++) { for(j=0;j<26;j++) { if(doc[i]==b[j]) { d[i][j]=1; count++; } elsed[i][j]=0; } } for(j=0;j<26;j++) { for(i=0;i<t;i++)//統(tǒng)計(jì)權(quán)值 sum[j]=sum[j]+d[i][j]; if(sum[j]!=0) { H[k].weight=sum[j];H[k].val=b[j]; k++; } } n=HuffmanTree(k); for(i=0;i<k;i++) printf("%c出現(xiàn)的次數(shù)為：%d\n",H[i].val,H[i].weight);OutputHcoding(doc,t,k,n); Translate(n);}五、收獲和體會(huì)本實(shí)驗(yàn)為赫夫曼編碼實(shí)驗(yàn)。目的是掌握赫夫曼編碼的原理，及編碼的概念。整個(gè)程序設(shè)計(jì)的結(jié)果是能夠?qū)⒁粋€(gè)字母序列轉(zhuǎn)化為赫夫曼編碼，并能統(tǒng)計(jì)出各個(gè)字母出現(xiàn)的次數(shù)，以及每個(gè)字母在赫夫曼編碼樹(shù)里面的編碼，將這學(xué)期學(xué)習(xí)的關(guān)于赫夫曼編碼及樹(shù)的知識(shí)全都得到了很好的應(yīng)用。在設(shè)計(jì)程序的初期，我的目的很明確，但是因?yàn)閷?duì)各個(gè)代碼環(huán)節(jié)的編碼不是很熟悉，以及大一學(xué)習(xí)的C語(yǔ)言知識(shí)掌握的不是很熟練，所以在做本次試驗(yàn)的時(shí)候很困難。本實(shí)驗(yàn)共涉及到五個(gè)子函數(shù)，既找出最小的兩個(gè)數(shù)，作為左孩子和右孩子，從而建造赫夫曼樹(shù)，將得到的數(shù)據(jù)存儲(chǔ)在赫夫曼樹(shù)中，最后再將各個(gè)字母的編碼打出，輸入到顯示屏上。經(jīng)過(guò)這次試驗(yàn)，我想收獲的不僅僅是關(guān)于赫夫曼編碼有關(guān)的知識(shí)，更多的是我在今后的編