資源描述:
《課程設計(論文) 哈夫曼編碼與解碼.doc》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、廣東工業(yè)大學華立學院課程設計(論文)課程名稱數(shù)據(jù)結(jié)構(gòu)題目名稱哈夫曼編碼與解碼學生學部(系)一計算機與藝術(shù)設計學部?專業(yè)班級學號學生姓名指導教師2010年12月29日廣東工業(yè)大學華立學院課程設計(論文)任務書題目名稱哈夫曼編碼學生學部(系)專業(yè)班級姓名學號一、課程設計(論文)的內(nèi)容用C語言實現(xiàn)哈夫曼編碼與解碼,輸入頻率進行編碼,輸入一串二進制碼進行解碼。二、課程設計(論文)的要求與數(shù)據(jù)設計的主要內(nèi)容應包括:①總體設計;②詳細設計;③調(diào)試與測試:測試結(jié)果的分析與討論④源程序清單三、課程設計(論E)應完成的工作
2、(1)根據(jù)上述要求完成一個功能完善哈夫曼編碼解碼的程序;(2)程序書寫符合規(guī)范,程序設計應完善;(3)對系統(tǒng)進行初步的錯誤和漏洞檢測;(4)根據(jù)設計規(guī)范撰寫報告并按時提交;(5)設計內(nèi)容用A4紙打印并按要求裝訂。四、課程設計(論文)進程安排序號設計(論文)各階段內(nèi)容地點起止日期1搜集資料圖書館12.262算法分析與設計圖書館12.27-12.283算法實現(xiàn)圖書館12.29-12.304完成課程設計(論文)機房12.31五、應收集的資料及主要參考文獻自己列五本發(fā)出任務書日期:2010年12月20日指導教師簽
3、名:摘要哈夫曼編碼(HuffmanCoding)是一種編碼方式,哈夫曼編碼是可變字長編碼(VLC)的一種。uffman于1952年提岀一種編碼方法,該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造杲字頭的平均長度最短的碼字,有時稱Z為最佳編碼,一般就叫作Huffman編碼。本課程設計以MicrosoftC++作為系統(tǒng)開發(fā)平臺。關(guān)鍵詞:MicrosoftC++,哈夫曼編碼,數(shù)據(jù)結(jié)構(gòu)1序言以哈夫曼樹一即最優(yōu)二叉樹,帶權(quán)路徑長度最小的二叉樹,經(jīng)常應用于數(shù)據(jù)壓縮。在計算機信息處理屮,“哈夫曼編碼”是一種一?致性編碼法(乂稱〃爛編
4、碼法〃),用于數(shù)據(jù)的無損耗床縮。這一術(shù)語是指使用一張?zhí)厥獾木幋a表將源字符(例如某文件小的一個符號)進行編碼。這張編碼表的特殊Z處在于,它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的(出現(xiàn)概率高的字符使用較短的編碼,反之出現(xiàn)概率低的則使用較長的編碼,這便使編碼之后的字符串的平均期望長度降低,從而達到無損壓縮數(shù)據(jù)的FI的)。這種方法是由David.A.Huffman發(fā)展起來的。例如,在英文屮,e的出現(xiàn)概率很高,而z的出現(xiàn)概率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時,e極有可能用一?個位(bit)來表示,血
5、z則可能花去25個位(不是26)。用普通的表示方法時,每個英文字母均占用一個字節(jié)(byte),即8個位。二者相比,e使用了一般編碼的1/8的長度,z則使用了3倍多。倘若我們能實現(xiàn)對于英文屮各個字母出現(xiàn)概率的較準確的估算,就可以大幅度提高無損壓縮的比例。2算法分析與設計2.1算法分析本項n的名稱是哈夫曼編碼與解碼根據(jù)要求,主要功能包括(1)輸入頻率,進行哈夫曼編碼(2)輸入一串二進制碼,進行解碼。系統(tǒng)的輸入設備由一般的輸入設備(即鍵盤、鼠標)組成,主要是從系統(tǒng)的彈岀對話框輸入帳戶的數(shù)據(jù)信息。系統(tǒng)的輸出主要以
6、對話框、編輯框顯示于屏幕。2.2算法設計學生成績管理系統(tǒng)包括哈夫曼編碼、解碼,詳細的功能描述如下:(1)選擇進行編碼,輸入頻率,輸出編碼(2)選擇進行解碼,輸入一串二進制碼,輸出解碼3算法的實現(xiàn)主要功能代碼。#include^include#include#definen8#definem2*nTttdefinemax2000typedefstruct{intwi;chardata;int卩arent,LehiId,Rchild;}huffm;hu
7、ffmHT[m+l];typedefstruct{charbits[n+l];intstart;charch;}ctype;voidHuffmTree(huffmHT[m+l]);voidHuffmcode(ctypecode[n+l]);voidOutput(ctypecode[n+l]);/*構(gòu)造HuffmTree的函數(shù)*/voidHuffmTree(huffm*HT)inti,j,pl,p2;intsi,s2;//for(i=l;i<=n;i++)//{//scanf("%d〃,&w);//HT[i
8、].wi=w;//}for(i二11+I;i<=m;i++)pl=p2=0;s1—s2—max;for(j=l;j<=i-l;j++)if(HT[j].Parent==0)if(HT[j].wi