哈夫曼編碼算法實驗報告-昆明理工大學

昆明理工大學信息工程與自動化學院學生實驗報告（2012—2013學年第1學期）課程名稱：算法設計與分析開課實驗室：信自樓4422012年11月8日年級、專業(yè)、班計科101學號姓名成績實驗項目名稱哈夫曼編碼指導教師吳霖教師評語該同學是否了解實驗原理： A.了解□ B.基本了解□ C.不了解□該同學的實驗能力： A.強□ B.中等□ C.差□該同學的實驗是否達到要求： A.達到□ B.基本達到□ C.未達到□實驗報告是否規(guī)范： A.規(guī)范□ B.基本規(guī)范□ C.不規(guī)范□實驗過程是否詳細記錄： A.詳細□ B.一般□ C.沒有□教師簽名：年月日一、上機目的及內(nèi)容1.上機內(nèi)容設需要編碼的字符集為{d1,d2,…,dn}，它們出現(xiàn)的頻率為{w1,w2,…,wn}，應用哈夫曼樹構(gòu)造最短的不等長編碼方案。2.上機目的（1）了解前綴編碼的概念，理解數(shù)據(jù)壓縮的基本方法；（2）掌握最優(yōu)子結(jié)構(gòu)性質(zhì)的證明方法；（3）掌握貪心法的設計思想并能熟練運用。二、實驗原理及基本技術(shù)路線圖（方框原理圖或程序流程圖）（1）證明哈夫曼樹滿足最優(yōu)子結(jié)構(gòu)性質(zhì)；（2）設計貪心算法求解哈夫曼編碼方案；（3）設計測試數(shù)據(jù)，寫出程序文檔。三、所用儀器、材料（設備名稱、型號、規(guī)格等或使用軟件）1臺PC及VISUALC++6.0軟件四、實驗方法、步驟（或：程序代碼或操作過程） #include<stdio.h>#include<stdlib.h>#include<string.h>typedefstruct{unsignedintweight;//存放權(quán)值unsignedintparent,LChild,RChild;}HTNode,*HuffmanTree;typedefchar*HuffmanCode;//選擇兩個雙親為0，且權(quán)重最小的結(jié)點s1和s2voidSelect(HuffmanTree*ht,intn,int*s1,int*s2){inti,min;for(i=1;i<=n;i++){if((*ht)[i].parent==0){min=i;break;}}for(i=1;i<=n;i++){if((*ht)[i].parent==0) {if((*ht)[i].weight<(*ht)[min].weight)min=i; }}*s1=min;for(i=1;i<=n;i++){if((*ht)[i].parent==0&&i!=(*s1)) {min=i;break; }}for(i=1;i<=n;i++){if((*ht)[i].parent==0&&i!=(*s1)) {if((*ht)[i].weight<(*ht)[min].weight) min=i; }}*s2=min;}voidCrtHuffmanTree(HuffmanTree*ht,int*w,intn){intm,i,s1,s2;m=2*n-1;*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(i=1;i<=n;i++){(*ht)[i].weight=w[i];(*ht)[i].LChild=0;(*ht)[i].parent=0;(*ht)[i].RChild=0;}for(i=n+1;i<=m;i++){(*ht)[i].weight=0;(*ht)[i].LChild=0;(*ht)[i].parent=0;(*ht)[i].RChild=0;}for(i=n+1;i<=m;i++)//創(chuàng)建非葉子結(jié)點，建哈夫曼樹{Select(ht,i-1,&s1,&s2);(*ht)[s1].parent=i;(*ht)[s2].parent=i;(*ht)[i].LChild=s1;(*ht)[i].RChild=s2;(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;}printf("\n");}voidCrtHuffmanCode(HuffmanTree*ht,HuffmanCode*hc,intn){char*cd;inta[100];inti,start,p,w=0;unsignedintc;hc=(HuffmanCode*)malloc((n+1)*sizeof(char*));//分配n個編碼的頭指針cd=(char*)malloc(n*sizeof(char));//分配求當前編碼的工作空間cd[n-1]='\0';//從右向左逐位存放編碼，首先存放編碼結(jié)束符for(i=1;i<=n;i++)//求n個葉子結(jié)點對應的哈夫曼編碼{a[i]=0;start=n-1;//起始指針位置在最右邊f(xié)or(c=i,p=(*ht)[i].parent;p!=0;c=p,p=(*ht)[p].parent)//從葉子到根結(jié)點求編碼{ if((*ht)[p].LChild==c) { cd[--start]='1';//左分支標1 a[i]++; }else { cd[--start]='0';//右分支標0 a[i]++; }}hc[i]=(char*)malloc((n-start)*sizeof(char));//為第i個編碼分配空間strcpy(hc[i],&cd[start]);//將cd復制編碼到hc}free(cd);for(i=1;i<=n;i++)printf("權(quán)值為%d的哈夫曼編碼為：%s\n",(*ht)[i].weight,hc[i]);for(i=1;i<=n;i++)w+=(*ht)[i].weight*a[i];}voidmain(){HuffmanTreeHT;HuffmanCodeHC;int*w,i,n,wei;printf("請輸入結(jié)點個數(shù)：");scanf("%d",&n);w=(int*)malloc((n+1)*sizeof(int));printf("\n輸入這%d個元素的權(quán)值:\n",n);for(i=1;i<=n;i++){printf("%d:",i);fflush(stdin);scanf("%d",&wei);w[i]=wei;}CrtHuffmanTree(&HT,w,n);CrtHuffmanCode(&HT,&HC,n);}五、實驗過程原始記錄(測試數(shù)據(jù)、圖表、計算等)六、實驗結(jié)果、分析和結(jié)論（誤差分析與數(shù)據(jù)處理、成果總結(jié)等。其中，繪制曲線圖時必須用計算紙或程序運行結(jié)果、改進、收獲）得到哈夫曼樹后，自頂向下按路