1、湖南科技學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告課題：霍夫曼編碼專業(yè)班級(jí)：信計(jì)1202學(xué)號(hào)：201205001239姓名：黃思琪牛志毅指導(dǎo)教師：1課程設(shè)計(jì)的目的和意義在當(dāng)今信息爆炸時(shí)代，如何采用有效的數(shù)據(jù)壓縮技術(shù)來節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來越引起人們的重視。哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個(gè)葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“I”碼，取每條路徑上的“0”或“1”的序列作為和各個(gè)對應(yīng)的字符的編碼，這就是哈夫曼編碼。通常我們把

2、數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報(bào)通信是傳遞文字的二進(jìn)制碼形式的字符串。但在信息傳遞時(shí)，總希望總長度盡可能最短，即采用最短碼。2.需求分析課題：哈夫曼編碼譯碼器系統(tǒng)問題描述：打開一篇英文文章，統(tǒng)計(jì)該文章中每個(gè)字符出現(xiàn)的次數(shù)，然后以它們作為權(quán)值，對每一個(gè)字符進(jìn)行編碼，編碼完成后再對其編碼進(jìn)行譯碼。問題補(bǔ)充：1.從硬盤的一個(gè)文件里讀出一段英語文章；2 .統(tǒng)計(jì)這篇文章中的每個(gè)字符出現(xiàn)的次數(shù)；3 .以字符出現(xiàn)字?jǐn)?shù)作為權(quán)值，構(gòu)建哈夫曼樹4 .對每個(gè)字符進(jìn)行編碼并將所編碼寫入文件然后對所編碼進(jìn)行破譯。具體介紹：在本課題中，我們在硬盤D盤中預(yù)先建立一個(gè)xuzhimo.txt文檔，在里面編輯一

3、篇文章(大寫)。然后運(yùn)行程序，調(diào)用Eleopen()函數(shù)讀出該文章,顯示在界面；再調(diào)用tongji()函數(shù)對該文章的字符種類進(jìn)行統(tǒng)計(jì)，并對每個(gè)字符的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì)，并且在界面上顯示；然后以每個(gè)字符出現(xiàn)次數(shù)作為權(quán)值，調(diào)用Create_huffmanTree()函數(shù)構(gòu)建哈夫曼樹。然后調(diào)用Huffman_bianma()函數(shù)對哈夫曼樹進(jìn)行編碼，調(diào)用coding。函數(shù)將編碼寫入文件。163系統(tǒng)(項(xiàng)目)設(shè)計(jì)(1)設(shè)計(jì)思路及方案本課題是用最優(yōu)二叉樹即哈夫曼樹來實(shí)現(xiàn)哈夫曼編碼譯碼器的功能。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi,編碼長度為Li,電文中有n種字符，則電文編碼總長度為(W1*L1)+(W2*L2

4、)+,+(Wi*Li)o若將此對應(yīng)到二叉樹上，Wi為葉結(jié)點(diǎn)，Li為根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長度。那么，(W1*L1)+(W2*L2)+,+(Wi*Li)恰好為二叉樹上帶權(quán)路徑長度。因此，設(shè)計(jì)電文總長最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹，此構(gòu)造過程稱為哈夫曼編碼。該系統(tǒng)將實(shí)現(xiàn)以下幾大功能：從硬盤讀取字符串，建立哈夫曼樹，輸出哈夫曼樹的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)，輸出各種字符出現(xiàn)的次數(shù)以及哈夫曼編碼的譯碼等。(2)模塊的設(shè)計(jì)及介紹1從硬盤讀取字符串fileopen(參數(shù))(實(shí)現(xiàn)命令；打印輸出；)2建立HufifinanTree通過三個(gè)函數(shù)來實(shí)現(xiàn)：voidselect_min(

5、參數(shù))(初始化；for接受命令;處理命令;）說明：在htl.k中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法inttongji（參數(shù)）（初始化；for（接受命令；處理命令；）說明：統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類voidCreate_huffmanTree（）（初始化；for（接受命令；處理命令；）輸出字符統(tǒng)計(jì)情況；說明：構(gòu)造哈夫曼樹3哈夫曼編碼voidHuffman_bianma（參數(shù)）（定義變量；處理命令;說明：哈夫曼編碼(3)主要模塊程序流程圖下面介紹三個(gè)主要的程序模塊流程圖:主函數(shù)流程圖：否是字符總數(shù)num統(tǒng)計(jì)字符種類及頻率建立哈夫曼樹哈夫曼編碼圖3.1流程圖注釋：然后統(tǒng)計(jì)

6、 接著在哈夫該圖比較簡單，主要是調(diào)用各個(gè)函數(shù)模塊，首先代開已經(jīng)存在的文件,總的字符數(shù)以及出現(xiàn)的各個(gè)字符和頻率。然后才開始建立哈夫曼樹，曼樹的基礎(chǔ)上對其進(jìn)行編碼。最后輸出結(jié)束。構(gòu)造哈夫曼樹:圖3.2流程圖注釋:該圖是表示構(gòu)造哈夫曼樹的過程。首先輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值，當(dāng)knum是循環(huán)結(jié)束。然后進(jìn)行哈夫曼樹的構(gòu)建，當(dāng)i=2*num-l是循環(huán)結(jié)束。最后輸出所得到的字符統(tǒng)計(jì)情況。哈夫曼編碼：（開始是VCd-start=O是Tp-ieft=c?Cd-start=l否（結(jié)束）Cd-start=O,start=num圖3.3流程圖解釋:該流程圖表四哈夫曼編碼情況。首先初始化，Cd-start=O,star

7、t=numo然后進(jìn)行編碼，當(dāng)cdstart=Tp.lchild=c時(shí)，cdstart=O；當(dāng)cdstart=Tp.left!=c時(shí),cdstart=lo這個(gè)編碼循環(huán)一直到i二num時(shí)結(jié)束。4系統(tǒng)實(shí)現(xiàn)各模塊關(guān)鍵代碼及算法的解釋：主調(diào)函數(shù)代碼解釋：這是main函數(shù)里的各個(gè)函數(shù)調(diào)用情況。fileopen(string);/從硬盤中讀取文件num=tongji(string,cishu,str);/統(tǒng)計(jì)字符種類及各類字符出現(xiàn)的頻率Create_huffmanTree(HT,HC,cishu,str);/建立哈夫曼樹Huffinan_bianma(HT,HC);/生成哈夫曼編碼建立HuffmanTree

8、代碼解釋：該函數(shù)為在htl.k中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法，其序號(hào)為si和s2。voidselect_min(HuffinanTreeT,intk,int&xl,int&x2)(inti,j;intminl=1000;for(i=l;i<=k;i+)if(Ti.weight<min1&&Ti.parent=O)(尸；minl=Ti.weight;)xl=j;minl=1000;for(i=l；i<=k;i+)if(Ti.weight<min1&&Ti.parent=0&&i!=xl)(

9、尸1;minl=Ti.weight;x2=j;代碼解釋：下面函數(shù)用來統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類。當(dāng)字符在A和Z之間時(shí)即被計(jì)數(shù)，并用strQ保存字母到數(shù)組中，用cntj統(tǒng)計(jì)每種字符個(gè)數(shù)。j返回總共讀取的字符數(shù)目。inttongji(char*s,intcishu,charstr)(inti,j,k;char午；intt27;for(i=l;i<=26;i+)ti=O;for(p=s;加='0'p+)(if(*p>='A,&&*p<=,Z')k=*p-64;tk+;)for(i=l,j=0;i<=26;+i)if

10、(ti!=O)(j+;strj=i4-64;cishuj=ti;returnj;)代碼解釋：下面函數(shù)用來構(gòu)造哈夫曼樹HTo首先初始化哈夫曼樹，然后輸入前面統(tǒng)計(jì)的各結(jié)點(diǎn)的權(quán)值，用for循環(huán)來構(gòu)造哈夫曼樹。ht.HuffrnanCodehe,intvoidCreate_huffmanTree(HuffirnanTree/cishu,charstr)生成哈夫曼樹HTinti,sl,s2;for(i=0;i<2*num-l;i+)hti.right=O;htieparent=O;hti.weight=O;for(i=l;i<=num;i+)/輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值hti.weight=c

11、ishui;for(i=num+l;i<=2*num-l;i+)/選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)，其序號(hào)為si和s2,i為雙親select_min(ht,i-l,s1,s2);htsl.parent=i;hts2.parent=i;htiJeft=s1;hti.right=s2;htieWeight=htsl.weight+hts2.weight;for(i=0;i<=num;i+)hcixh=stri;/字符的種類i=l;while(i<=num)printf(H字符%c次數(shù):%8dn,hci.ch,cishui+);生成Huffinan編碼并寫入文件代碼解釋：

12、根據(jù)哈夫曼樹T求哈夫曼編碼HovoidHuffinan_bianma(HuffinanTreeT,HuffinanCodeH)樹T求哈夫曼編碼Hintchild,parent.i;/childt中孩子和雙親charcoden;/存放編碼intstart;/指示碼在codecodenum=,0,;/最后一位/根據(jù)哈夫曼和parent分別指示中的起始位置num個(gè))放上串結(jié)束for(i=l;i<=num；4-4-i)start=num;/初始位置child=i;/從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行遍歷while(parent=Tchildeparent)>0)/直至/若tchild是tchild是樹

13、根為止(parent的左孩子，則生成0;否則生成1if(Tparent.left=child)code-start='0'elsecodestart=fr；child=parent;strcpy(Hi.co,&codestart);Hi.len=num-start;代碼解釋：對str所代表的字符串進(jìn)行編碼并寫入文件。將翻譯的二進(jìn)制碼寫入文本文件。voidcoding(HuffmanCodehe,char%tr)/對str所代表的字符串進(jìn)行編碼并寫入文件inti,j;FILE*fp;fp=fopen(ncodefile.txtM,nw,f);while(*str)(for

14、(i=l;i<=num;i4-+)if(hci.ch=*str)for(j=O;j<=hci.len;j+)fputc(hci.coj,fp);break;str+;fclose(fp);5系統(tǒng)調(diào)試本次測試是在我的電腦的D盤中建立一個(gè)名為file.txt的文本文檔，其中有大寫字母IAMASTUDENT,期望程序能將其讀出至界面并實(shí)現(xiàn)其他相關(guān)的功能。運(yùn)行程序后，我們可以見到一下的運(yùn)行界面。從硬盤中讀出已有的文本文件哈夫曼編碼MXXMJC,>*L.請選擇1.開始2 .麹出各字符統(tǒng)計(jì)個(gè)數(shù)3 .編碼4 輸出編碼H.退出讀出文本為:lAtlASTUDENT1 .開始2.輸出各字符統(tǒng)計(jì)個(gè)

15、數(shù)3 .編碼4 .輸出編陰5,退出11111輸出所讀字符的種類和每種字符的個(gè)數(shù)ADEIMNSTU數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù) 次次次次次次次次次隼 選 請j rxr.xz輸出編碼陶碼為二000 101 請選擇001 101 011 110 10& 1110 工.開始2 .植出各字符統(tǒng)計(jì)個(gè)數(shù)3 .編碼4 .輸出編用5 0退出mi010 118小結(jié)通過一周的課程設(shè)計(jì)使我對哈夫曼樹以及哈夫曼編碼有了更深的認(rèn)識(shí)和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。首先我談?wù)勎以谠O(shè)計(jì)期間我遇到的難點(diǎn)。開始的時(shí)候，代碼中有許多的錯(cuò)誤，特別是有一個(gè)“無法找到文件”的錯(cuò)誤讓我束手無策，最后還是屏蔽了定

16、義的四個(gè)頭文件然后慢慢地改正錯(cuò)誤才讓我又看到了希望。然后在實(shí)現(xiàn)文章的讀入時(shí)，由于對文件不是太熟悉，只好翻開c語言書本仿照其模式編寫，但后來進(jìn)入了死循環(huán)，最后的解決方式是把main函數(shù)里的一個(gè)do,while循環(huán)去掉。許多的錯(cuò)誤讓我明白了一個(gè)道理一細(xì)心是非常重要的。同時(shí)，對于編程者而言，思路清晰是相當(dāng)重要的。在適當(dāng)?shù)臅r(shí)候和同學(xué)一起交流探討是一個(gè)十分好的學(xué)習(xí)機(jī)會(huì)。這次課程設(shè)計(jì)不但讓我學(xué)得了一些編程知識(shí)，還學(xué)會(huì)了系統(tǒng)的做一份課程設(shè)計(jì)報(bào)告，學(xué)會(huì)了如何截圖，學(xué)會(huì)了如何更好的畫流程圖，明白了做事情只有認(rèn)真，才能真正做得更好！通過這次課程設(shè)計(jì)，我看清楚了自己的編程功底和動(dòng)手能力還很不足，這主要是平時(shí)實(shí)踐太少

17、的緣故。我想，在未來的暑假中，我會(huì)努力嘗試編寫一些程序。在這個(gè)程序中，還有許多地方值得完善。比如，讀出文本只能是大寫的文檔，空格和小寫不能識(shí)別。由于時(shí)間問題，暫時(shí)不能實(shí)現(xiàn)了，我想在暑假里好好研究這個(gè)問題。未完成：哈夫曼譯碼1625附錄源程序# include<stdio.h># include<string.h># include<stdlib.h>#include<fstream.h>類型相關(guān)變量的定義# definen100# definem2%-1typedefstruct(/存放編碼charch;charco9;intlen;(CodeN

18、ode;typedefCodeNodeHuffmanCoden+1;typedefstructintweight;intleft,right,parent;HTNode;typedefHTNodeHuffmanTreem+l;intnum;voidselect_min(HuffiTianTreeT,intk,int&xl,int&x2)/選擇權(quán)值最小的兩個(gè)根結(jié)點(diǎn)，其序號(hào)為xl和X2inti,j;intminl=1000;for(i=l;i<=k;i+)找最小值if(Ti.weight<minl&&Ti.parent=O)(j=i；minl=Ti.we

19、ight;)xl=j;minl=1000;for(i=l;i<=k;i+)/找次小值if(Ti.weight<min1&&Ti.parent=O&&i!=xl)(j二i；minl=Ti.weight;x2=j;)inttongji(char*s,intcishu,charstr)(統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類intchar節(jié)；intt27;fbr(i=l;i<=26;i+)ti=O;ft)r(p=s;個(gè)!=,0,;p+)的個(gè)數(shù)(if(個(gè)二Z)k=*p-64;tk+；)for(i=l,j=0;i<=26;+i)if(ti!=O)

20、(j+；strj=i+64;到數(shù)組中cishuQ=ti;權(quán)值)returnj;種數(shù)voidCreate_huffmanTree(HuiTiTianTreeht,HuffimanCodehe,intcishu,charstr)(生成哈夫曼樹HTinti,sl,s2;for(i=0;i<2*num-l;i+)(hti.left=O;hti.right=O;hti.parent=O;hti.weight=O;/統(tǒng)計(jì)各種字符送對應(yīng)的字母存入對應(yīng)字母的/j是輸入字母/輸入num個(gè)葉)lbr(i=l;i<=num;i+)結(jié)點(diǎn)的權(quán)值號(hào)為si和s2,i為雙親hti. we ig ht=cishui

21、;fbr(i=num+l ;i<=2*num-l ;i+) 選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)，其序select_min(ht,i-l ,s 1 ,s2);hts 1 .parent=i;hts2.parent=i;hti.left=s 1; hti.right=s2;hti.weight=hts 1 . we ight+hts 2. we ight;)fbr(i=O;i<=num;i+)hci.ch=stri;字符的種類i=l; while (i<=num)printf(M 字符 %c 次數(shù):%8dnn,hci.ch,cishui+);void Huffiiian_

22、bianma(HuftTnanTree T,HuffmanCode H)根據(jù)哈夫曼樹T求哈夫曼編碼H分別指示t中孩子和雙親始位置個(gè)）放上串結(jié)束符int child,parent,i;char coden;int start;codenum='0'lbr(i=l ;i<=num;+i)/child 和 parent/存放編碼指示碼在code中的起最后一位（第 numstart=num;/初始位置child=i;從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行遍歷根為止的左孩子，則生成0;否則生成1while(parent=Tchild.parent)>0)/直至tchild是樹若tchild是

23、(parentif(Tparent.left=child)codestart='0'elsecode-starter；child=parent;)strcpy(Hi.co,&codestart);Hi.len=num-start;voidcoding(HuffinanCodehe,char*str)對str所代表的字符串進(jìn)行編碼并寫入文件inti,j;FILE忡；lp=fbpen(ncodefile.txf"/'w");while(*str)(for(i=l;i<=num;i+)if(hci.ch=*str)for(j=O;j<=hci.len;j+)lputc(hci.coj,ip);break;)str+;fclose(ip);voidoutput()輸出編碼FILE加；charch;if(fp=fopen(',codefile.txt,<r+,')=NULL)(printf(,errornH);exit(O);)printf(H編碼為:n");ch=igetc(lp);while(!feof(lp)