數(shù)據(jù)結(jié)構(gòu)課程設(shè)計哈夫曼編碼譯碼的設(shè)計與實現(xiàn)

1、 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計題目-哈夫曼編碼/譯碼的設(shè)計與實現(xiàn) 班級：13軟件設(shè)計2班 學(xué)號：1315925068姓名：耿浩琪指導(dǎo)教師： 目錄目錄1一、 需求分析2二、 設(shè)計要求2三、概要設(shè)計21、流程圖22、設(shè)計包含的幾個部分4四、詳細設(shè)計2五、顯示結(jié)果9.六、心得體會10七、參考文獻11哈夫曼編碼譯碼一、 需求分析在當(dāng)今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視，赫夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼是一種編碼方式，以哈夫曼樹即最優(yōu)二叉樹，帶權(quán)路徑長度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈弗曼編碼使用一張?zhí)厥獾木?/p>

2、碼表將源字符（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數(shù)據(jù)的目的）。赫夫曼編碼的應(yīng)用很廣泛，利用赫夫曼樹求得的用于通信的二進制編碼稱為赫夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個葉子對應(yīng)的字符的編碼，這就是赫夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進制代碼，輸入二進制代碼時可

3、以編譯成字符串。二、設(shè)計要求對輸入的一串電文字符實現(xiàn)赫夫曼編碼，再對赫夫曼編碼生成的代碼串進行譯碼，輸出電文字符串。通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度能盡可能短，即采用最短碼。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為wi，編碼長度為li，電文中有n種字符，則電文編碼總長度為wili。若將此對應(yīng)到二叉樹上，wi為葉結(jié)點的權(quán)，li為根結(jié)點到葉結(jié)點的路徑長度。那么，wili恰好為二叉樹上帶權(quán)路徑長度。因此 ，設(shè)計電文總長最短的二進制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵赫夫曼樹，此構(gòu)造過程稱為赫夫曼編碼。設(shè)

4、計實現(xiàn)的功能： (1) 赫夫曼樹的建立； (2) 赫夫曼編碼的生成； (3) 編碼文件的譯碼。 三、 概要設(shè)計哈夫曼編譯碼器的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進行譯碼 。在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進制字符0、1組成的二進制串，稱之為編碼。構(gòu)造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分之代表0，右分支代表1，則從根節(jié)點到每個葉子節(jié)點所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點對應(yīng)字符的編碼，稱之為哈夫曼編碼。最簡單的二進制編碼方式是等長編碼。若采用不等長編碼，讓出現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長的編碼，這樣可能縮短傳送電文的總長度

5、。哈夫曼樹課用于構(gòu)造使電文的編碼總長最短的編碼方案。（1）其主要流程圖如圖1-1所示。開始結(jié)點數(shù)是否大于1將data和權(quán)值賦給ht輸出根結(jié)點和權(quán)值調(diào)用select函數(shù)計算根結(jié)點函數(shù)父結(jié)點為兩子結(jié)點之和輸出兩子結(jié)點和已構(gòu)造的結(jié)點是否為根結(jié)點？左子是否為空？此時編碼為0i2*n?i+編碼為1結(jié)束否否否右子是否為空是是否否是是是（2）設(shè)計包含的幾個方面： 赫夫曼樹的建立赫夫曼樹的建立由赫夫曼算法的定義可知，初始森林中共有n棵只含有根結(jié)點的二叉樹。算法的第二步是：將當(dāng)前森林中的兩棵根結(jié)點權(quán)值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個新結(jié)點。顯然要進行n1次合并，所以共

6、產(chǎn)生n1個新結(jié)點，它們都是具有兩個孩子的分支結(jié)點。由此可知，最終求得的赫夫曼樹中一共有2n1個結(jié)點，其中n個結(jié)點是初始森林的n個孤立結(jié)點。并且赫夫曼樹中沒有度數(shù)為1的分支結(jié)點。我們可以利用一個大小為2n-1的一維數(shù)組來存儲赫夫曼樹中的結(jié)點。 赫夫曼編碼 要求電文的赫夫曼編碼，必須先定義赫夫曼編碼類型，根據(jù)設(shè)計要求和實際需要定義的類型如下： typedet struct char ch; / 存放編碼的字符 char bitsn1; / 存放編碼位串 int len; / 編碼的長度 codenode; / 編碼結(jié)構(gòu)體類型 代碼文件的譯碼 譯碼的基本思想是：讀文件中編碼，并與原先生成的赫夫曼編碼

7、表比較，遇到相等時，即取出其對應(yīng)的字符存入一個新串中。 四、 詳細設(shè)計（1）赫夫曼樹的存儲結(jié)構(gòu)描述為： #define n 50 / 葉子結(jié)點數(shù) #define m 2*n-1 / 赫夫曼樹中結(jié)點總數(shù) typedef struct int weight; / 葉子結(jié)點的權(quán)值 int lchild, rchild, parent; / 左右孩子及雙親指針 htnode; / 樹中結(jié)點類型 typedef htnode huffmantreem+1; 哈弗曼樹的算法void createht(htnode ht,int n) /調(diào)用輸入的數(shù)組ht,和節(jié)點數(shù)n int i,k,lnode,rnode

8、; int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有結(jié)點的相關(guān)域置初值-1 for (i=n;i2*n-1;i+) /構(gòu)造哈夫曼樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權(quán)值的兩個結(jié)點位置 for (k=0;k=i-1;k+) if (htk.parent=-1) /只在尚未構(gòu)造二叉樹的結(jié)點中查找 if (htk.weightmin1) /若權(quán)值小于最小的左節(jié)點的權(quán)值 min2=min1;rno

9、de=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個最小節(jié)點的父節(jié)點是i hti.weight=htlnode.weight+htrnode.weight; /兩個最小節(jié)點的父節(jié)點權(quán)值為兩個最小節(jié)點權(quán)值之和 hti.lchild=lnode;hti.rchild=rnode; /父節(jié)點的左節(jié)點和右節(jié)點（2）哈弗曼編碼void createhcode(htnode ht,hcode hcd,int n)

10、int i,f,c; hcode hc; for (i=0;in;i+) /根據(jù)哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結(jié)點結(jié)束循環(huán) if (htf.lchild=c) /處理左孩子結(jié)點 hc.cdhc.start-=0; else /處理右孩子結(jié)點 hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /start指向哈夫曼編碼hc.cd中最開始字符 hcdi=hc; void disphcode(htnode ht,hcode hcd,int n) /輸出哈夫曼編碼的

11、列表 int i,k; printf( 輸出哈夫曼編碼:n); for (i=0;in;i+) /輸出data中的所有數(shù)據(jù)，即a-z printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+) /輸出所有data中數(shù)據(jù)的編碼 printf(%c,hcdi.cdk); printf(n); void edithcode(htnode ht,hcode hcd,int n) /編碼函數(shù)char stringmaxsize; int i,j,k;scanf(%s,string); /把要進行編碼的字符串存入string數(shù)組中printf(n輸出編碼結(jié)果:n);

12、for (i=0;stringi!=#;i+) /#為終止標志for (j=0;jn;j+)if(stringi=htj.data) /循環(huán)查找與輸入字符相同的編號，相同的就輸出這個字符的編碼for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /輸出完成后跳出當(dāng)前for循環(huán)（3）哈弗曼譯碼void dehcode(htnode ht,hcode hcd,int n) /譯碼函數(shù)char codemaxsize;int i,j,l,k,m,x;scanf(%s,code); /把要進行譯碼的字符串存入code數(shù)組中while(code0!=#

13、)for (i=0;in;i+)m=0; /m為想同編碼個數(shù)的計數(shù)器 for (k=hcdi.start,j=0;k=n;k+,j+) /j為記錄所存儲這個字符的編碼個數(shù)if(codej=hcdi.cdk) /當(dāng)有相同編碼時m值加1m+;if(m=j) /當(dāng)輸入的字符串與所存儲的編碼字符串個數(shù)相等時則輸出這個的data數(shù)據(jù)printf(%c,hti.data);for(x=0;codex-1!=#;x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex+j;（4）主函數(shù)void main() int n=26,i; char orz,back,flag=1; char str

14、=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z; /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 htnode htm; /建立結(jié)構(gòu)體 hcode hcdn; /建立結(jié)構(gòu)體 for (i=0;in;i+) /把初始化的數(shù)據(jù)存入ht結(jié)構(gòu)體中 hti.data=stri; hti.weight=fnumi; while (flag) /菜單函數(shù)，當(dāng)flag為0時跳出循環(huán) （5）顯示部分源程序： pri

15、ntf(n); printf( *); printf(n * 1-顯示編碼 *); printf(n * 2-進行編碼 *); printf(n * 3-進行譯碼 *); printf(n * 4-退出 *n); printf( * *); printf(n); printf( 請輸入選擇的編號:); scanf(%c,&orz); switch(orz) case a: case a: system(cls); /清屏函數(shù) createht(ht,n); createhcode(ht,hcd,n); disphcode(ht,hcd,n); printf(n按任意鍵返回.); getch()

16、; system(cls); break; case b: case b: system(cls); printf(請輸入要進行編碼的字符串(以#結(jié)束):n); edithcode(ht,hcd,n); printf(n按任意鍵返回.); getch(); system(cls); break; case c: case c: system(cls); disphcode(ht,hcd,n); printf(請輸入編碼(以#結(jié)束):n); dehcode(ht,hcd,n); printf(n按任意鍵返回.); getch(); system(cls); break; case d: case

17、 d: flag=0; break; default: system(cls); 五、調(diào)試結(jié)果進入主菜單選a時的顯示結(jié)果選擇b時的顯示結(jié)果選c時的顯示結(jié)果五、 心得體會通過這次課程設(shè)計，讓我對一個程序的數(shù)據(jù)結(jié)構(gòu)有更全面更進一步的認識，根據(jù)不同的需求，采用不同的數(shù)據(jù)存儲方式，不一定要用棧，二叉樹等高級類型，有時用基本的一維數(shù)組，只要運用得當(dāng)，也能達到相同的效果，甚至更佳，就如這次的課程設(shè)計，通過用for的多重循環(huán)，舍棄多余的循環(huán)，提高了程序的運行效率。在編寫這個程序的過程中，我復(fù)習(xí)了之前學(xué)的基本語法，哈弗曼樹最小路徑的求取，哈弗曼編碼及譯碼的應(yīng)用范圍，程序結(jié)構(gòu)算法等一系列的問題它使我對數(shù)據(jù)結(jié)構(gòu)改

18、變了看法。在這次設(shè)計過程中，體現(xiàn)出自己單獨設(shè)計模具的能力以及綜合運用知識的能力，體會了學(xué)以致用、突出自己勞動成果的喜悅心情，也從中發(fā)現(xiàn)自己平時學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補。通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計，我學(xué)習(xí)了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識，真正學(xué)會一種算法了。當(dāng)求解一個算法時,不是拿到問題就不加思索地做，而是首先要先對它有個大概的了解，接著再詳細地分析每一步怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。這次課程設(shè)計，我在編輯中犯了不應(yīng)有的錯誤，設(shè)計統(tǒng)計字符和合并

19、時忘記應(yīng)該怎樣保存數(shù)據(jù)，對文件的操作也很生疏。在不斷分析后明確并改正了錯誤和疏漏，我的程序有了更高的質(zhì)量。六、 參考文獻1 徐孝凱編著，數(shù)據(jù)結(jié)構(gòu)課程實驗，清華大學(xué)出版 2002年第一版2 張乃笑編著，數(shù)據(jù)結(jié)構(gòu)與算法，電子工業(yè)出版社 2004年10月3 嚴蔚敏 數(shù)據(jù)結(jié)構(gòu)（c語言版） 清華大學(xué)出版社附錄：源程序如下：#include #include /要用system函數(shù)要調(diào)用的頭文件#include /用getch()要調(diào)用的頭文件#include #define n 50 /義用n表示50葉節(jié)點數(shù)#define m 2*n-1 /用m表示節(jié)點總數(shù) 當(dāng)葉節(jié)點數(shù)位n時總節(jié)點數(shù)為2n-1#defi

20、ne maxsize 100typedef struct char data; /結(jié)點值 int weight; /權(quán)值 int parent; /雙親結(jié)點 int lchild; /左孩子結(jié)點 int rchild; /右孩子結(jié)點htnode; typedef struct char cdn; /存放哈夫曼碼 int start; /從start開始讀cd中的哈夫曼碼hcode;void createht(htnode ht,int n) /調(diào)用輸入的數(shù)組ht,和節(jié)點數(shù)n int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) hti.

21、parent=hti.lchild=hti.rchild=-1; /所有結(jié)點的相關(guān)域置初值-1 for (i=n;i2*n-1;i+) /構(gòu)造哈夫曼樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權(quán)值的兩個結(jié)點位置 for (k=0;k=i-1;k+) if (htk.parent=-1) /只在尚未構(gòu)造二叉樹的結(jié)點中查找 if (htk.weightmin1) /若權(quán)值小于最小的左節(jié)點的權(quán)值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else i

22、f (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個最小節(jié)點的父節(jié)點是i hti.weight=htlnode.weight+htrnode.weight; /兩個最小節(jié)點的父節(jié)點權(quán)值為兩個最小節(jié)點權(quán)值之和 hti.lchild=lnode;hti.rchild=rnode; /父節(jié)點的左節(jié)點和右節(jié)點void createhcode(htnode ht,hcode hcd,int n) int i,f,c; hcode hc; for (i=0;in;i+) /根據(jù)哈夫曼樹求哈夫曼編

23、碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結(jié)點結(jié)束循環(huán) if (htf.lchild=c) /處理左孩子結(jié)點 hc.cdhc.start-=0; else /處理右孩子結(jié)點 hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /start指向哈夫曼編碼hc.cd中最開始字符 hcdi=hc; void disphcode(htnode ht,hcode hcd,int n) /輸出哈夫曼編碼的列表 int i,k; printf( 輸出哈夫曼編碼:n); for (i=0;in;i+) /

24、輸出data中的所有數(shù)據(jù)，即a-z printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+) /輸出所有data中數(shù)據(jù)的編碼 printf(%c,hcdi.cdk); printf(n); void edithcode(htnode ht,hcode hcd,int n) /編碼函數(shù)char stringmaxsize; int i,j,k;scanf(%s,string); /把要進行編碼的字符串存入string數(shù)組中printf(n輸出編碼結(jié)果:n);for (i=0;stringi!=#;i+) /#為終止標志for (j=0;jn;j+)if(

25、stringi=htj.data) /循環(huán)查找與輸入字符相同的編號，相同的就輸出這個字符的編碼for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /輸出完成后跳出當(dāng)前for循環(huán)void dehcode(htnode ht,hcode hcd,int n) /譯碼函數(shù)char codemaxsize;int i,j,l,k,m,x;scanf(%s,code); /把要進行譯碼的字符串存入code數(shù)組中while(code0!=#)for (i=0;in;i+)m=0; /m為想同編碼個數(shù)的計數(shù)器 for (k=hcdi.start,j=0;k=n;k+,j+) /j為記錄所存儲這個字符的編碼個數(shù)if(codej=hcdi.cdk) /當(dāng)有相同編碼時m值加1m+;if(m=j) /當(dāng)輸入的字符串與所存儲的編碼字符串個數(shù)相等時則輸出這個的data數(shù)據(jù)printf(%c,hti.data);for(x=0;codex-1!=#;x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex+j;void main() int n=26,i; char orz,back,flag=1; char str=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z; /初始化 in