版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告(2012—2013學(xué)年第1學(xué)期)課程名稱(chēng):算法設(shè)計(jì)與分析開(kāi)課實(shí)驗(yàn)室:信自樓4422012年11月8日年級(jí)、專(zhuān)業(yè)、班計(jì)科101學(xué)號(hào)姓名成績(jī)實(shí)驗(yàn)項(xiàng)目名稱(chēng)哈夫曼編碼指導(dǎo)教師吳霖教師評(píng)語(yǔ)該同學(xué)是否了解實(shí)驗(yàn)原理: A.了解□ B.基本了解□ C.不了解□該同學(xué)的實(shí)驗(yàn)?zāi)芰Γ? A.強(qiáng)□ B.中等□ C.差□該同學(xué)的實(shí)驗(yàn)是否達(dá)到要求: A.達(dá)到□ B.基本達(dá)到□ C.未達(dá)到□實(shí)驗(yàn)報(bào)告是否規(guī)范: A.規(guī)范□ B.基本規(guī)范□ C.不規(guī)范□實(shí)驗(yàn)過(guò)程是否詳細(xì)記錄: A.詳細(xì)□ B.一般□ C.沒(méi)有□教師簽名:年月日一、上機(jī)目的及內(nèi)容1.上機(jī)內(nèi)容設(shè)需要編碼的字符集為{d1,d2,…,dn},它們出現(xiàn)的頻率為{w1,w2,…,wn},應(yīng)用哈夫曼樹(shù)構(gòu)造最短的不等長(zhǎng)編碼方案。2.上機(jī)目的(1)了解前綴編碼的概念,理解數(shù)據(jù)壓縮的基本方法;(2)掌握最優(yōu)子結(jié)構(gòu)性質(zhì)的證明方法;(3)掌握貪心法的設(shè)計(jì)思想并能熟練運(yùn)用。二、實(shí)驗(yàn)原理及基本技術(shù)路線圖(方框原理圖或程序流程圖)(1)證明哈夫曼樹(shù)滿足最優(yōu)子結(jié)構(gòu)性質(zhì);(2)設(shè)計(jì)貪心算法求解哈夫曼編碼方案;(3)設(shè)計(jì)測(cè)試數(shù)據(jù),寫(xiě)出程序文檔。三、所用儀器、材料(設(shè)備名稱(chēng)、型號(hào)、規(guī)格等或使用軟件)1臺(tái)PC及VISUALC++6.0軟件四、實(shí)驗(yàn)方法、步驟(或:程序代碼或操作過(guò)程) #include<stdio.h>#include<stdlib.h>#include<string.h>typedefstruct{unsignedintweight;//存放權(quán)值unsignedintparent,LChild,RChild;}HTNode,*HuffmanTree;typedefchar*HuffmanCode;//選擇兩個(gè)雙親為0,且權(quán)重最小的結(jié)點(diǎn)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é)點(diǎn),建哈夫曼樹(shù){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個(gè)編碼的頭指針cd=(char*)malloc(n*sizeof(char));//分配求當(dāng)前編碼的工作空間cd[n-1]='\0';//從右向左逐位存放編碼,首先存放編碼結(jié)束符for(i=1;i<=n;i++)//求n個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的哈夫曼編碼{a[i]=0;start=n-1;//起始指針位置在最右邊f(xié)or(c=i,p=(*ht)[i].parent;p!=0;c=p,p=(*ht)[p].parent)//從葉子到根結(jié)點(diǎn)求編碼{ if((*ht)[p].LChild==c) { cd[--start]='1';//左分支標(biāo)1 a[i]++; }else { cd[--start]='0';//右分支標(biāo)0 a[i]++; }}hc[i]=(char*)malloc((n-start)*sizeof(char));//為第i個(gè)編碼分配空間strcpy(hc[i],&cd[start]);//將cd復(fù)制編碼到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("請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù):");scanf("%d",&n);w=(int*)malloc((n+1)*sizeof(int));printf("\n輸入這%d個(gè)元素的權(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í)驗(yàn)過(guò)程原始記錄(測(cè)試數(shù)據(jù)、圖表、計(jì)算等)六、實(shí)驗(yàn)結(jié)果、分析和結(jié)論(誤差分析與數(shù)據(jù)處理、成果總結(jié)等。其中,繪制曲線圖時(shí)必須用計(jì)算紙或程序運(yùn)行結(jié)果、改進(jìn)、收獲)得到哈夫曼樹(shù)后,自頂向下按路
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 蘇教版創(chuàng)世神話課件
- 蘇教版五年級(jí)心得體會(huì)
- 人教版一年級(jí)下冊(cè)期中試卷
- 師大民俗學(xué)考試題目
- 六年級(jí)人教版負(fù)數(shù)教案
- 蘇教版小學(xué)數(shù)學(xué)教案圖形教學(xué)的策略與創(chuàng)新
- 蘇教版高中物理習(xí)題集錦
- 蘇教版二年級(jí)語(yǔ)文上冊(cè)閱讀訓(xùn)練
- 蘇教版通分教學(xué)的案例分析
- 完全平方公式在人教版課件中的深度解讀
- 原子力顯微鏡AFM課件
- 農(nóng)機(jī)安全生產(chǎn)培訓(xùn)課件
- 幼兒園小班科學(xué)實(shí)驗(yàn)科學(xué)教案《軟軟的和硬硬的》及教學(xué)反思
- ISO90012015各部門(mén)內(nèi)審檢查表
- 傳播學(xué)經(jīng)典理論英文版
- 高速公路橋梁工程作業(yè)指導(dǎo)書(shū)
- ICU新護(hù)士6月專(zhuān)科理論知識(shí)考試試題
- 《鋪滿金色巴掌的水泥道》-優(yōu)秀課件
- 黑馬王子量波理論
- 早產(chǎn)兒發(fā)展性照顧課件
- 橈骨遠(yuǎn)端骨折的護(hù)理查房課件完整版
評(píng)論
0/150
提交評(píng)論