數(shù)據(jù)結(jié)構(gòu)課程設(shè)計哈夫曼編碼器

1、摘 要哈夫曼（huffman）樹是一種帶權(quán)路徑長度最小的二叉樹，也稱最優(yōu)二叉樹，它有著極為廣泛的應(yīng)用。而我今天做的課程設(shè)計就是其中的一個應(yīng)用-哈夫曼編碼器。其實它的思想很簡單，顯示根據(jù)輸入的權(quán)值建立一棵哈夫曼樹，然后根據(jù)哈夫曼數(shù)求出各個葉結(jié)點的編碼。這樣就構(gòu)成了一個最簡單的哈夫曼編碼器。關(guān)鍵詞：哈夫曼樹 編碼器 最優(yōu)二叉樹 帶權(quán)路徑長度目 錄1 課題分析11.1 設(shè)計目的11.2 設(shè)計要求11.3設(shè)計內(nèi)容12 總體設(shè)計與分析321功能函數(shù)設(shè)計32.1.1建立哈夫曼樹32.2.2求哈夫曼編碼函數(shù)32.2.3打印編碼函數(shù)33 程序說明43.1 結(jié)構(gòu)圖44 程序調(diào)試54.1 菜單54.2 輸入葉結(jié)點

2、和權(quán)值64.3 輸出哈夫曼編碼75 設(shè)計問題85.1存入文件85.1.1問題185.1.2問題286 小結(jié)9參考文獻10源代碼111 課題分析在當(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í)厥獾木幋a表將源字符（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的

3、則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數(shù)據(jù)的目的）。赫夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個葉子對應(yīng)的字符的編碼，這就是哈夫曼編碼。1.1 設(shè)計目的（1）復(fù)習(xí)并靈活掌握二叉樹的各種儲存結(jié)構(gòu)和遍歷方法。（2）了解靜態(tài)鏈表，并掌握其構(gòu)造方法。（3）掌握哈夫曼樹的構(gòu)造過程和哈夫曼編碼的求解方法。（4）復(fù)習(xí)掌握文件讀寫的基本方法。1.2 設(shè)計要求（1）求得的哈夫曼編碼及w

4、pl必須寫入編碼文件。（2）哈夫曼樹的存儲可以采用靜態(tài)鏈表或二叉鏈表。1.3設(shè)計內(nèi)容我在實驗中采用的是靜態(tài)鏈表作為存儲結(jié)構(gòu)，其數(shù)據(jù)類型可以定義為：#define m 2*n-1 /*m為哈夫曼樹的結(jié)點*/ /*具有n個葉結(jié)點的哈夫曼樹共有2n-1個結(jié)點*/typedef structint wi; /*定義權(quán)值*/char data; /*定義葉結(jié)點*/int parent,lchild,rchild; /*定義父結(jié)點、左孩子、右孩子*/huffm;huffm htm+1; /*靜態(tài)鏈表htm+1*/(1)從文件中讀取所有結(jié)點的權(quán)值，將讀取的權(quán)值放到靜態(tài)鏈表中，并初始化靜態(tài)鏈表。（2）依據(jù)給定

5、的權(quán)值，不斷生成各分支結(jié)點，直到生成樹根結(jié)點為止，得到生成哈夫曼樹后的靜態(tài)鏈表。（3）規(guī)定所有的左分支為0，右分支為1，從樹根到葉子所經(jīng)過的分支構(gòu)成的01編碼，即是對應(yīng)葉子的哈夫曼編碼。（4）求出所有葉子的哈夫曼編碼，并將編碼寫入文件。2 總體設(shè)計與分析通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式的字符串。構(gòu)造一棵赫夫曼樹，此構(gòu)造過程稱為赫夫曼編碼。設(shè)計實現(xiàn)的功能： (1) 赫夫曼樹的建立； (2) 赫夫曼編碼的生成； (3) 編碼文件的譯碼。21功能函數(shù)設(shè)計2.1.1建立哈夫曼樹void huffmtree(huffm htm+1);我用的是手動輸

6、入，首先提醒用戶輸入8個葉結(jié)點，即8個字母，輸入完畢后提醒用戶輸入8個權(quán)值。以上的兩個輸入的輸入格式都用空格隔開，以回車結(jié)束。哈夫蠻樹建立成功。其基本算法是：由給定的8個權(quán)值，構(gòu)造由空二叉樹擴充得到的擴充二叉樹，每個數(shù)只有一個外部結(jié)點。在已經(jīng)構(gòu)造的擴充二叉樹中，選取根結(jié)點權(quán)值最小和次小的兩個。將它們作為左子樹、右子樹，構(gòu)造成一顆新的擴充二叉樹，它的根結(jié)點的權(quán)值為兩子樹的權(quán)值之和。重復(fù)執(zhí)行步驟，每次都使擴充的二叉樹的個數(shù)減一，當(dāng)只剩下一棵擴充二叉樹時，它便是所要構(gòu)造的哈夫曼樹。2.2.2求哈夫曼編碼函數(shù)void huffmcode(ctype coden+1);從根結(jié)點開始，尋找每一個葉結(jié)點，在

7、尋找過程中，經(jīng)過左子樹時，編碼增加“0”，經(jīng)過右子樹時，編碼增加“1”，當(dāng)每一個葉結(jié)點都訪問過時，便得到相應(yīng)的編碼。2.2.3打印編碼函數(shù)void output (ctype coden+1);打印編碼函數(shù)即輸出編碼函數(shù)。當(dāng)用戶輸好葉結(jié)點和權(quán)值后，通過哈夫曼編碼函數(shù)進行編碼，然后通過打印編碼函數(shù)將哈夫曼編碼顯示在屏幕上。3 程序說明3.1 結(jié)構(gòu)圖哈夫曼編碼器建立哈夫曼樹哈夫曼編碼輸出哈夫曼編碼這就是整個程序的基本流程，總共分為三大塊：建立哈夫曼樹、哈夫曼編碼、輸出哈夫曼編碼。其實思想很簡單，按照這個步驟來就行了。首先，用戶手動輸入8個字母和權(quán)，建立好哈夫曼樹后，左子樹為0，右子樹為1，根據(jù)這個

8、可以寫出每個葉結(jié)點的編碼。最后輸出即可。這整個程序過程都是通過c語言實現(xiàn)的，所以都是一些很簡單的語句，通俗易懂，這樣我修改起來也比較方便。4 程序調(diào)試4.1 菜單這只是一個很簡單的菜單，在這次的實驗中，我沒有在菜單上花很多功夫，所以這只是一個再簡單不過的開始界面，就是詢問用戶是否要繼續(xù)玩下去。4.2 輸入葉結(jié)點和權(quán)值用戶手動輸入輸入8個字母：a s d f g h j k輸入8個權(quán)值：12 22 33 45 6 9 8 244.3 輸出哈夫曼編碼在這個環(huán)節(jié)中，先輸出編譯好的哈夫曼編碼，接下來還要求最短路徑wpl。然后下面的那個菜單一開始的那個菜單是相同的意思，就是詢問用戶是否要繼續(xù)玩下去，如果

9、選擇1，則用戶再次手動輸入葉結(jié)點和權(quán)值，再進行編譯。5 設(shè)計問題5.1存入文件這次課程設(shè)計輸入的葉結(jié)點和權(quán)值，還有最后的哈夫曼編碼都是要存入文件。剛開始以為加進去個文件會很簡單，因為我們上學(xué)期也做過課程設(shè)計，是c語言的，最主要的就是弄文件，所以這個本來沒有多大問題。但是這次加了文件后出現(xiàn)了比較麻煩的問題。5.1.1問題1為什么記事本會出現(xiàn)空白？在我加入文件后顯示出現(xiàn)了許多小問題,具體是什么問題我已經(jīng)記得不清，只知道最后總算是把錯誤全找出來了，調(diào)通了，本來以為沒錯了，后來運行的一切都很正常。等到最后都執(zhí)行完了，打開文件發(fā)現(xiàn)文件是空白的，什么都沒有，就這個問題我嘗試過很多遍，可記事本始終是空白的，

10、后來我發(fā)現(xiàn)記事本的大小為1kb，就說明里面是肯定有東西，在研究了多遍后，發(fā)現(xiàn)記事本里都是空格，所以我們是看不見的，但用鼠標(biāo)全選一下就會發(fā)現(xiàn)有東西。5.1.2問題2為什么記事本中會全都是空格鍵？上面那個問題算是解決了，但接下來有個更頭疼的問題-為什么記事本中會都是空格鍵呢？怎么樣才能讓記事本中出現(xiàn)我輸入的哪些字符和數(shù)字呢？本來我是把保存文件單獨弄一個函數(shù)的-void save();但是由于文件出了問題，所以我就把文件的那個函數(shù)刪掉了，把它加入到程序中。然后我發(fā)現(xiàn)把文件加入主函數(shù)中后、文件夾中就會出現(xiàn)東西。但是至于為什么將文件單獨作為一個函數(shù)時，文件夾中出現(xiàn)的都是空格還沒有弄清楚。6 小結(jié)在我自己

11、課程設(shè)計中，就在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯誤，遇到了很多麻煩及困難，我的調(diào)試及其中的錯誤和我最終找出錯誤，修改為正確的能夠執(zhí)行的程序中，通過分析，我學(xué)到了：通過這次課程設(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)改變了看法

12、。在這次設(shè)計過程中，體現(xiàn)出自己單獨設(shè)計模具的能力以及綜合運用知識的能力，體會了學(xué)以致用、突出自己勞動成果的喜悅心情，也從中發(fā)現(xiàn)自己平時學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補。而且我還學(xué)習(xí)了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識，真正學(xué)會一種算法了。當(dāng)求解一個算法時,不是拿到問題就不加思索地做，而是首先要先對它有個大概的了解，接著再詳細地分析每一步怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。一個成功的項目必須在寫代碼前，先要對課題有充分的思考和規(guī)劃，否則即使完成了項目也會浪費很多

13、的時間和精力，我認為科學(xué)合理的編程方法是我這次課程設(shè)計的最大收獲。參考文獻1. 譚浩強著c語言設(shè)計（第四版）北京：清華大學(xué)大學(xué)出版社，20102 陳元春 王中華 張亮 王勇等著實用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（第三版）.北京，中國鐵道出版社，2011 3 秦鋒 袁志祥著.數(shù)據(jù)結(jié)構(gòu)（c語言版）例題詳解與課程設(shè)計指導(dǎo). 安徽:中國科學(xué)技術(shù)大學(xué)出版社,2007源代碼#include #include #include #define n 8 /*n為定的8個數(shù)*/#define m 2*n-1 /*m為哈夫曼樹的結(jié)點*/ /*具有n個葉結(jié)點的哈夫曼樹共有2n-1個結(jié)點*/#define max 2000 /*最大值

14、*/typedef struct int wi; /*權(quán)值*/ char data; int parent,lchild,rchild;/*定義父結(jié)點、左孩子、右孩子*/huffm;huffm htm+1;typedef struct char bitsn+1; int start; char ch;ctype;ctype coden+1;void huffmtree(huffm htm+1);void huffmcode(ctype coden+1);void output (ctype coden+1);/* 構(gòu)造huffmtree的函數(shù)*/void huffmtree(huffm *ht

15、) int i,j,p1,p2; int s1,s2; for(i=n+1;i=m;i+) p1=p2=0; s1=s2=max; for(j=1;j=i-1;j+) if(htj.parent=0) if(htj.wi s1) s2=s1; s1=htj.wi; p2=p1; p1=j; else if(htj.wis2) s2=htj.wi ; p2=j; htp1.parent=htp2.parent=i; hti.lchild=p1; hti.rchild=p2; hti.wi=htp1.wi+htp2.wi; return ;/* 求huffmtree編碼的函數(shù)*/void huff

16、mcode(ctype coden+1) int i,p,s; ctype md;for(i=1;i=n;i+) md.ch=codei.ch; md.start = n+1; s=i; p=hti.parent; while(p!=0) md.start-; if(htp.lchild=s) md.bitsmd.start=0; else md.bitsmd.start =1; s=p; p=htp.parent; codei = md; /*打印編碼函數(shù)*/void output(ctype coden+1) file *fp; if (fp=fopen(huffmancode.txt,w

17、)=null) printf(不能打開文件n); exit(0); fprintf(fp,n哈夫曼編碼); int i,j; int wpl=0,count=0; printf(n); printf(n); puts( tt=); printf(n); printf(ttt葉結(jié)點tt哈夫曼編碼); for(i=1;i=n;i+) printf(nttt %ctt,codei.ch ); for(j=1;j=n;j+) if(jcodei.start) printf( ); else if(codei.bitsj=0)|(codei.bitsj=1) printf(%c,codei.bitsj)

18、; count+; fputc(codei.bitsj,fp); fprintf(fp,n); wpl=wpl+count*hti.wi; count=0; printf(nn);printf(ttttwpl=%dn,wpl);fprintf(fp,n wpl=%d,wpl);puts( tt= );fclose(fp);/*主函數(shù)*/void main()file *fp;if (fp=fopen(huffman.txt,w)=null) printf(不能打開文件n); exit(0); int i,j,w;int flag=1; int choice; ctype coden+1; ch

19、ar tempn+1; int temp2n+1; printf(n);printf( ntt 哈夫曼編碼器 n);printf( ntt 主菜單 n);printf( ntt*n); printf( ntt* would you want to play? *n);printf( ntt* 1-yes and start *n);printf( ntt* 0-no and exit *n);printf( ntt*n);printf( ntt請選擇菜單號: ); scanf(%d,&choice); printf(n);while(flag&(choice=1) choice = 0; fo

20、r(i=1;i=m;i+)/初始化 hti.data =null; hti.wi=0; hti.parent = 0; hti.lchild = hti.rchild = 0; for(i=1;i=n;i+) codei.start = 0; codei.ch = null; for(j=1;j=n;j+) codei.bitsj = null; printf( ttplease input %d char(用空格隔開，以回車結(jié)束): n,n);/*輸入字母*/ printf( tt); getchar(); scanf(%c %c %c %c %c %c %c %c,&temp1,&temp2,&temp3,&temp4,&temp5,&temp6,&temp7,&temp8); fprintf(fp,字符); for(i=1;i=n;i+) codei.ch =tempi; hti.data =tempi; fputc(tempi,fp); printf(nn); printf( ttplease input %