赫夫曼課程設(shè)計

1、目目 錄錄前言前言.1 1正文正文.1 11.1 課程設(shè)計的教學目的和任務 .11.2 課程設(shè)計的主要內(nèi)容 .11.3 課程設(shè)計報告的要求.22.1.問題描述及基本要求 .22.2. 算法思想 .22.3 模塊劃分 .22.3.1 構(gòu)造赫夫曼樹.22.3.2 赫夫曼編碼(huffmancode).32.4. 數(shù)據(jù)結(jié)構(gòu) .52.5. 算法的時空分析 .52.6 測試數(shù)據(jù) .62.7. 測試情況 .6總總 結(jié)結(jié).7 7參考文獻：參考文獻：.7 7附附 錄錄.9 9塔里木大學信息工程學院課程設(shè)計第 1 頁 共 14 頁前言前言赫夫曼編碼(Huffman Coding)是一種編碼方式，赫夫曼編碼是可變

2、字長編碼(VLC)的一種。赫夫曼壓縮是個無損的壓縮算法，一般用來壓縮文本和程序文件。赫夫曼壓縮屬于可變代碼長度算法一族。意思是個體符號（例如，文本文件中的字符）用一個特定長度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號，則用較長的位序列。赫夫曼編碼的應用很廣泛，利用赫夫曼樹求地的二進制編碼稱為赫夫曼編碼。赫夫曼樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為對應的編碼，這就是赫夫曼編碼。我們在對一些問題進行求解時，會發(fā)現(xiàn)有些問題很難找到規(guī)律，或者根本無規(guī)

3、律可尋。對于這樣的問題，可以利用計算機運算速度快的特點，先搜索查找所有可能出現(xiàn)的情況，再根據(jù)題目條件從所有可能的情況中，刪除那些不符合條件的解。由赫夫曼算法的定義可知，初始森林中共有 n 棵只含有根結(jié)點的二叉樹。算法的的第二步是：算法的的第二步是：將當前森林中的兩棵根結(jié)點權(quán)值最小的二叉樹，合并成一棵新的二叉樹，每合并一次，森林中就減少一棵樹，產(chǎn)生一個新結(jié)點。則要進行 n-1 次合并，所以共產(chǎn)生 n-1 個新結(jié)點。由此可知，最終求得的赫夫曼樹中一共有 2n-1 個結(jié)點。其中， n 個結(jié)點是初始森林中的 n 個孤立結(jié)點。并且赫夫曼樹中沒有度數(shù)為 1 的分支的結(jié)點。采用赫夫曼編碼方案，即應用赫夫曼樹

4、構(gòu)造使電文的編碼總長最短的編碼方案。正文正文1.1 課程設(shè)計的教學目的和任務(1) 使學生進一步理解和掌握所學的各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和操作實現(xiàn)算法，以及它們在程序中的使用方法。(2) 使學生初步掌握軟件開發(fā)過程的問題分析、設(shè)計、編碼、測試等基本方法和基本技能。(3) 使學生掌握使用各種計算機資料和有關(guān)參考資料，提高學生進行程序設(shè)計的基本能力。(4) 使學生能用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作方法和作風。1.2 課程設(shè)計的主要內(nèi)容(1) 問題分析和任務定義。根據(jù)題目的要求，充分地分析和理解問題，明確問題要求做什么？限制條件是什么？(

5、2) 邏輯設(shè)計。對問題描述中涉及的操作對象定義相應的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計的結(jié)果應寫出每個抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明） ，各個主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖。(3) 物理設(shè)計。定義相應的存儲結(jié)構(gòu)并寫出各函數(shù)的偽代碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細設(shè)計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作作出進一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架。(4)程序編碼

6、。把詳細設(shè)計的結(jié)果進一步求精為程序設(shè)計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚。(5) 程序調(diào)試與測試。塔里木大學信息工程學院課程設(shè)計第 2 頁 共 14 頁采用自底向上，分模塊進行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計測試數(shù)據(jù)確定疑點，通過修改程序來證實它或繞過它。調(diào)試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結(jié)果。(6) 結(jié)果分析。程序運行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。算法的時間、空間復雜性分析。(7) 撰寫課程設(shè)計報告。1.3 課程設(shè)計報告的要求課程設(shè)計報告要求規(guī)范書寫。應當包括如下內(nèi)容： 問題描述：描述

7、要求編程解決的問題。 基本要求：給出程序要達到的具體的要求。 測試數(shù)據(jù)：設(shè)計測試數(shù)據(jù)，或具體給出測試數(shù)據(jù)。要求測試數(shù)據(jù)能全面地測試所設(shè)計程序的功能。 算法思想：描述解決相應問題算法的設(shè)計思想。 模塊劃分：描述所設(shè)計程序的各個模塊（即函數(shù)）功能。 數(shù)據(jù)結(jié)構(gòu)：給出所使用的基本抽象數(shù)據(jù)類型，所定義的具體問題的數(shù)據(jù)類型，以及新定義的抽象數(shù)據(jù)類型。 源程序：給出所有源程序清單，要求程序有充分的注釋語句，至少要注釋每個函數(shù)參數(shù)的含義和函數(shù)返回值的含義。 測試情況：給出程序的測試情況，并分析運行結(jié)果。 算法的時空分析(包括基本操作和其他算法的時間復雜度和空間復雜度的分析)和改進設(shè)想；經(jīng)驗和體會等。 參考文獻

8、：列出參考的相關(guān)資料和書籍。2.1.問題描述及基本要求利用赫夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本，試設(shè)計一個赫夫曼編碼系統(tǒng)。從鍵盤輸入一段報文（如what did you do that made you so happy） ，輸出這段報文的赫夫曼編碼。2.2. 算法思想赫夫曼編碼是根據(jù)可變長最佳編碼定理，應用赫夫曼算法而產(chǎn)生的一種編碼，是消除編碼冗余度最常用的方法。它的平均碼字長度在具有相同輸入概率集合的前提下，比其它任何一種可譯碼都小，因此，也常被稱為緊湊碼。將輸入的字符串統(tǒng)計其個數(shù)算出百分率，最為它的權(quán)值，然后將各權(quán)值創(chuàng)建赫夫曼樹，計算出對應的編碼。通過

9、譯碼字符串，從根部出發(fā)，按字符0和1確定找左右孩子。2.3 模塊劃分2.3.1 構(gòu)造赫夫曼樹給定 n 個實數(shù) w1，w2， ，wn（n） ，求一個具有 n 個結(jié)點的二叉數(shù)，使其帶權(quán)路徑長度最小。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度（若根結(jié)點為 0 層，葉結(jié)點到根結(jié)點的路徑長度為葉結(jié)點的層數(shù)） 。樹的帶權(quán)路徑長度記為 WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N 個權(quán)值 Wi(i=1,2,.n)構(gòu)成一棵有N 個葉結(jié)點的二叉樹，相應的葉結(jié)點的路徑長度為 Li(i=1,2,.n)?？梢宰C明赫夫曼樹的WPL 是最小的。(1) 根據(jù)與 n 個權(quán)值

10、w1,w2wn對應的 n 個結(jié)點構(gòu)成具有 n 棵二叉樹的森林 F=T1,T2Tn,其中第 i 棵二叉樹 Ti(1 i n)都只有一個權(quán)值為 wi 的根結(jié)點，其左、右子樹均為空塔里木大學信息工程學院課程設(shè)計第 3 頁 共 14 頁(2) 在森林 F 中選出兩棵根結(jié)點的權(quán)值最小的樹作為一棵新樹的左、右子樹，且置新樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點權(quán)值之和(3) 從 F 中刪除構(gòu)成新樹的那兩棵，同時把新樹加入 F 中(4) 重復第(2)和第(3)步，直到 F 中只含有一棵為止，此樹便為赫夫曼樹void CreatHFMTree(HFMTree *HT,int count)/創(chuàng)建赫夫曼樹int i

11、;HFMTree p,HT1,HT2; /HT1，HT2 分別存放權(quán)值最小和次小的節(jié)點的位置p=*HT=(HFMTree)malloc(sizeof(HFMNode);p-next=p-LChild=p-RChild=p-Parent=NULL; /初始化赫夫曼鏈表且有 2n-1個節(jié)點for(i=1;inext=(HFMTree)malloc(sizeof(HFMNode); p=p-next; p-next=p-LChild=p-RChild=p-Parent=NULL; for(i=0,p=*HT;iweight=counti; p=p-next; for(i=n;iParent=HT2-

12、Parent=p; p-LChild=HT1; p-RChild=HT2;p-weight=HT1-weight+HT2-weight;/將兩個節(jié)點的權(quán)值相加存入一個節(jié)點 p=p-next; /p 指向下一個沒有存儲權(quán)值的節(jié)點 2.3.2 赫夫曼編碼(huffmancode)1 根據(jù)最優(yōu)二叉樹構(gòu)造赫夫曼編碼，利用赫夫曼樹很容易求出給定字符集及其概率(或頻度)分布的最優(yōu)前綴碼。赫夫曼編碼正是一種應用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。該技術(shù)一般可將數(shù)據(jù)文件壓縮掉 20至 90，其壓縮效率取決于被壓縮文件的特征。（1）用字符 si作為葉子，counti做為葉子 si的權(quán)，構(gòu)造一棵赫夫曼樹，并將樹中左分支

13、和右分支分別標記為 0 和 1；（2）將從根到葉子的路徑上的標號依次相連，作為該葉子所表示字符的編碼。該編碼即為最優(yōu)前綴碼（也稱赫夫曼編碼） 。代碼如下：void TotalCoding(char s,CodeNode HC,char code)/利用赫夫曼編碼表對整個字符串進行編碼 int i,j;code0=0; /編碼數(shù)組初始化 for(i=0;si;i+) for(j=0;jn;j+) if(si=HCj.ch) strcpy(code+strlen(code),HCj.code+HCj.start);2 給定字符集的赫夫曼樹生成后，求赫夫曼編碼的具體實現(xiàn)過程是：依次以葉子 si塔里木

14、大學信息工程學院課程設(shè)計第 4 頁 共 14 頁(0in-1)為出發(fā)點，向上回溯至根為止。上溯時走左分支則生成代碼 0，走右分支則生成代碼 1。(1)由于生成的編碼與要求的編碼反序，將生成的代碼先從后往前依次存放在一個臨時向量中，并設(shè)一個指針 start 指示編碼在該向量中的起始位置.(2)當某字符編碼完成時，從臨時向量的 start 處將編碼復制到該字符相應的位串中即可。(3)因為字符集大小為 n，故變長編碼的長度不會超過 n，加上一個結(jié)束符0 .2.3.3 建立赫夫曼表void HFMCode(HFMTree HT,CodeNode HC,char str)/從每個葉子節(jié)點開始，利用赫夫曼

15、樹對每個字符進行編碼，最終建立一個赫夫曼表int i;HFMTree q,p=HT;for(i=0;in;i+) /將字符存入赫夫曼編碼結(jié)構(gòu)體數(shù)組的字符單元中 HCi.ch=stri; HCi.coden-1=0; /初始化編碼的最后一位 for(i=0;iParent;q=q-Parent) /判斷 q 所指向的節(jié)點，左孩子置 0，右孩子置 1 if(q=q-Parent-LChild) HCi.code-HCi.start=0; else HCi.code-HCi.start=1; p=p-next; /判斷下一個葉子節(jié)點 2.3.4 赫夫曼譯碼算法依次讀人文件的二進制碼，從赫夫曼樹的根結(jié)

16、點(即 Tm-1)出發(fā)，若當前讀人 0，則走向左孩子，否則走向右孩子。一旦到達某一葉子 T 時便譯出相應的字符 H.ch。然后重新從根出發(fā)繼續(xù)譯碼，直至文件結(jié)束。代碼如下：void DeCoding(char code,HFMTree HT,char str,char s)/對赫夫曼編碼進行解碼，放入字符串 s 中int i,j,k=0;HFMTree root,p,q;for(root=HT;root-Parent;root=root-Parent); /用 root 指向赫夫曼樹的根結(jié)點for(i=0,p=root;codei;i+) /從根結(jié)點開始按編碼順序訪問樹if(codei=0)

17、p=p-LChild; else p=p-RChild; if(p-LChild=NULL&p-RChild=NULL) /到根節(jié)點時將該節(jié)點對應的字符輸出 for(j=0,q=HT;q!=p;q=q-next,j+); sk+=strj; p=root; /回溯到根結(jié)點 塔里木大學信息工程學院課程設(shè)計第 5 頁 共 14 頁sk=0; /解碼完畢，在字符串最后一個單元存入02.4. 數(shù)據(jù)結(jié)構(gòu)主要定義了兩個結(jié)構(gòu)體2.4.1 定義赫夫曼樹節(jié)點結(jié)構(gòu)體typedef struct node int weight;struct node *LChild,*RChild,*Parent; /分別

18、指向該節(jié)點的左孩子，右孩子，和雙親節(jié)點struct node *next; /指向建立的赫夫曼樹的下一個節(jié)點HFMNode,*HFMTree;2.4.2 定義赫夫曼編碼的結(jié)構(gòu)體typedef struct char ch; /存儲對應的字符char codeN+1; /存儲對應字符的編碼int start; /存儲編碼的起始位置CodeNode;2.4.3 各個函數(shù)間的關(guān)系如圖：圖圖 2.12.1 各函數(shù)簡的調(diào)用關(guān)系各函數(shù)簡的調(diào)用關(guān)系2.5. 算法的時空分析時間復雜度：構(gòu)造赫夫曼樹:T(n)= O(n) 塔里木大學信息工程學院課程設(shè)計第 6 頁 共 14 頁建立赫夫曼表：T(n)=O(n2)

19、進行譯碼：T(n)= O(n) 赫夫曼編碼 T(n)= O(n) 2.6 測試數(shù)據(jù)對下列給出的字符集數(shù)據(jù)建立赫夫曼樹，并實現(xiàn)以下報文的編碼和譯碼字符串：what did you do that made you so happy字符 空格 A B C D E F G H I J K L M 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 12.7. 測試情況2.7.1 編碼首先在初始界面，選擇編碼，鍵盤中輸入 1 如圖 2.2

20、：圖圖 1 1 編譯初始界面編譯初始界面塔里木大學信息工程學院課程設(shè)計第 7 頁 共 14 頁圖圖 2 2 編碼界面編碼界面2.7.2 通過編碼出來的密碼文件解碼最終的到的字符串，通過與原來的字符串對比，完全一樣.說明編碼解碼成功?？偪?結(jié)結(jié)通過該題目的設(shè)計過程,對數(shù)據(jù)結(jié)構(gòu)以及二叉樹的邏輯結(jié)構(gòu),存儲結(jié)構(gòu)的理解,對樹的數(shù)據(jù)結(jié)構(gòu)上基本運算的實現(xiàn)有所掌握,對課本中所學的各種數(shù)據(jù)結(jié)構(gòu)進一步理解和掌握,學會了如何把學到的知識用于解決實際問題,鍛煉了自己動手的能力。完成所有的工作是非常困難和耗時的。在以后的學習中我會更加注意自己各個方面的能力的協(xié)調(diào)發(fā)展。在課程設(shè)計時我遇到了很多的問題，在老師的幫助，和對各

21、種資料的查閱中，將問題解決，培養(yǎng)了我自主動手，獨立研究的能力，為今后在學習工作中能更好的發(fā)展打下了堅實的基礎(chǔ)。參考參考文獻：文獻：1譚浩強編著.C+課程設(shè)計.北京：清華大學社，20042S.B.Lippman，J.Lajoie 著.潘愛民譯.C+Primer（3rd Edition）中文版.北京：中國電力出版社，20023H.M.Deitel，Paul James Deitel 著.薛萬鵬譯.C+程序設(shè)計教程.北京：機械工業(yè)出版社，20004Stephen R.Savis 著.C+ For Dummies 4th edition，IDG Books Worldwide，Inc.，20025Ha

22、rvey M.Deitel .Jack W.Davidson 著.邱仲潘譯.C+大學教程（第二版）.北京：電子工業(yè)出版社，20026James P.Cohoon.Jack W.Davidson 著.劉瑞挺等譯.C+程序設(shè)計（第三版）.北京：電子工業(yè)出版社塔里木大學信息工程學院課程設(shè)計第 8 頁 共 14 頁7Decoder 編著.C/C+程序設(shè)計.北京：中國鐵道出版社，20028Brian Overland 著.董梁等譯.C+語言命令譯解（第二版）.北京：機械工業(yè)出版社，20029 H.M.Deitel，Paul James Deitel 著.薛萬鵬譯.C/C+程序設(shè)計大全.北京：機械工業(yè)出版

23、社.199710Al Strevens,Clayton Walnum 著.林麗閩等譯.標準 C+寶典.北京：電子工業(yè)出版社.2001 11Michael J.Young 著.Mastering Visual C+6.0 Sybex Inc.199912Leen Ammeraal 著.劉瑞挺等譯.C+程序設(shè)計教程（第三版）.北京：zhongguo 鐵道出版社，200313 呂鳳翥著. C+語言程序設(shè)計.北方交通大學出版社，200314 袁啟昌著.C+語言程序設(shè)計.清華大學出版社，200415 劉振安，劉燕君，孫忱 C+語言課程設(shè)計.機械工業(yè)出版社，200716 楊進才，沈顯君，劉蓉編.C+語言程

24、序設(shè)計教程.清華大學出版社，200617 宋振會著. C+語言編程基礎(chǔ)教程.清華大學出版社，2005塔里木大學信息工程學院課程設(shè)計第 9 頁 共 14 頁附附 錄錄#include#include#include#include#includetypedef struct /赫夫曼樹的結(jié)構(gòu)體char ch;int weight; /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2) /Select 函數(shù)，選出 HT

25、樹到 a 為止，權(quán)值最小且 parent 為 0 的 2 個節(jié)點int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i; /選出最小的節(jié)點for(j=1;j=a;+j)if(HTj.parent=0&x!=j)y=j;break;塔里木大學信息工程學院課程設(shè)計第 10 頁 共 14 頁for(i=j+1;i=a;+i)if(HTi.weighty)*p1=y;*p2=x;else*p1=x;*p2=y;void h

26、fmcoding(hfmtree &HT,hfmcode &HC,int n) /構(gòu)建赫夫曼樹 HT，并求出 n 個字符的赫夫曼編碼 HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=n;+i) /初始化 n 個葉子結(jié)點printf(請輸入第%d 字符信息和權(quán)值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.

27、weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的結(jié)點HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;塔里木大學信息工程學院課程設(shè)計第 11 頁 共 14 頁for(i=n+1;i=m;+i) /建立赫夫曼樹Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.w

28、eight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /給 n 個字符編碼start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int main()char code

29、100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件輸入輸出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;coutn;cout 計算機（3）班 Q07620307 XXXn;while(choice!=Q&choice!=q) /當 choice 的值不為 q 且不為Q 時循環(huán)cout *赫夫曼編碼/譯碼器*n; cout I.Init E.Encoding D.Decoding Q.Exitn;塔里木大學信息工程學院課程設(shè)計第 12 頁 共 14 頁

30、coutchoice; if(choice=I|choice=i) /初始化赫夫曼樹coutn;hfmcoding(HT,HC,n);for(i=1;i=n;+i)coutHTi.ch:HCiendl;output_file.open(hfmTree.txt);if(!output_file)coutcant oen file!endl;return 1;for(i=1;i=n;i+)output_file(HTi.chHCi);output_file.close();cout赫夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入 hfmTree.txt 文件中!endl; else if(choice=E|choice=e) /進行編碼，并將字符放入ToBeTran.txt，碼值放入 CodeFile.txt 中printf(請輸入字符：);gets(str);output_file.open(ToBeTran.txt);if(!output_file)coutcant oen file!endl;return 1;output_filestrendl;output_file.close();output_file.open(CodeFile.txt);if(!output_f