《數(shù)據結構》課程設計報告哈夫曼編譯碼器程序設計

1、各專業(yè)全套優(yōu)秀畢業(yè)設計圖紙數(shù)據結構課程設計報告哈夫曼編譯碼器程序設計班 級： 2012 級計算機科學與技術 學 號： 201225160106 姓 名： 指導老師： 提交日期： 2013年12月20日 摘 要在現(xiàn)代社會，通信的發(fā)展，使得現(xiàn)代社會更加豐富多彩，我們可以隨時隨地在任何地方了解到世界各地的信息，而這又必須依賴信息的傳遞。在信息化高度發(fā)達的當今社會，我們必須對信息的傳遞有著較高的要求，我們希望信息在傳遞的過程中，能夠保持節(jié)省性和保密性和無損性，而著名的哈夫曼編碼就能夠達到這樣的要求。哈夫曼編碼是huffman于1952年提出一種編碼方法，該方法完全依據字符出現(xiàn)概率來構造異字頭的平均長度

2、最短的碼字，有時稱之為最佳編碼，一般就叫作huffman編碼（有時也稱為霍夫曼編碼）。哈夫曼編碼適用于多遠獨立信源,對于多元獨立信源來說它是最佳碼。但其存在的不足直接制約了它的廣泛應用。本設計主要介紹了哈夫曼編碼算法、譯碼算法等功能的程序實現(xiàn)。關鍵詞：數(shù)據結構；哈夫曼編碼；哈夫曼樹；譯碼abstractin modern society, the development of communication, making more colorful modern society, we can understand that information anywhere, anytime in an

3、y place around the world, which in turn must rely on the transmission of information. in todays highly developed information society, we have to pass information to a higher demand, we hope the information in the course of transmission, it is possible to save and maintain the confidentiality and non

4、-destructive nature, and the famous huffman coding can meet this requirement.huffman huffman coding is a coding method proposed in 1952, the method according to the probability of the characters appear completely different prefix to construct the shortest average length of codewords, sometimes refer

5、red to as the best coding, generally known as huffman coding (huffman coding is sometimes referred to). huffman coding applied to how far an independent source for diverse independent sources for it is the best code. but its shortcomings directly restricts its wide application. this design introduce

6、s the huffman coding algorithm decoding algorithm functions such program.keywords: data structure;huffman coding; huffman decoding目 錄1 引言12 需求分析22.1 數(shù)據分析22.2 功能要求23 概要設計33.1 設計思路33.2 抽象數(shù)據類型43.3 主程序流程53.4 各程序模塊的關系64 詳細設計74.1 數(shù)據類型的定義74.2 主要模塊的描述84.2.1 主要模塊算法描述84.2.2 主要算法流程圖描述105 調試分析125.1 調試問題分析125.2

7、算法時空分析126 用戶使用說明137 測試結果147.1 詳細測試分析147.2 各種情況測試分析158 結論198.1 總結198.2 個人心得19參考文獻20附錄211 引 言電報曾經是人們進行快速遠距離通信的重要手段，它將傳送的文字一般使用二進制數(shù)傳送數(shù)據。在發(fā)送端將數(shù)據轉換成0、1序列（即編碼），而在接收端又將0、1序列轉換成對應的數(shù)據（即譯碼）。在傳送電文時，采用哈夫曼方法對傳輸?shù)碾妶筮M行編碼，讓電文中出現(xiàn)的次數(shù)較多的字符采用盡可能短的編碼，這樣的傳輸電文的總長度就會減少。哈夫曼編碼是一種編碼方式，是一種用于無損數(shù)據壓縮的熵編碼（權編碼）算法。1952年，davida.huffma

8、n在麻省理工攻讀博士時所發(fā)明的，并發(fā)表于一種構建極小多余編碼的方法（amethodfortheconstructionofminimum-redundancycodes）一文。本設計主要介紹了哈夫曼樹的構造，哈夫曼編碼以及哈夫曼譯碼的主要算法，給出了哈夫曼編譯碼的程序的簡單實現(xiàn)。將要求用戶輸入一行字符串而后程序將統(tǒng)計字符串中每個字符重復出現(xiàn)的次數(shù)并作為其權值。然后將這些字符及權值來構造一棵哈夫曼樹，并對它們進行哈夫曼樹編碼，再根據這些哈夫曼樹編碼給出二進制串譯出字符。2 需求分析2.1 數(shù)據分析1）輸入的形式：輸入一串字符串；在譯碼的時候輸入一串由“0”和“1”組成的字符串。2）輸入值的范圍：

9、字符串長度小于256（可根據需要進行修改）。3）輸出的形式：編碼時輸出編碼表，譯碼時輸出原文字符串。4）程序所能達到的功能：對電文進行轉換編碼以及實現(xiàn)哈二進制串的譯碼。5）測試數(shù)據：一串包含數(shù)字、字母、符號的字符串；一串包含數(shù)字的字符串；一串包含字母的字符串；一串包含符號的字符串；一串包含數(shù)字、字母、符號、空格的字符串等情況；由所給出的哈夫曼編碼組成的二進制串；隨意的二進制串；隨意的字符串。2.2 功能要求課程設計程序功能要求如下：1）生成哈夫曼樹。2）哈夫曼樹采用靜態(tài)鏈表存儲。3）求哈夫曼樹對應的哈夫曼編碼。4）給出哈夫曼編碼譯出字符。3 概要設計3.1 設計思路1）編寫frequencyc

10、ounter函數(shù)來實現(xiàn)統(tǒng)計用戶輸入字符串的字符及其次數(shù)。在統(tǒng)計用戶輸入的字符串中每個字符出現(xiàn)的次數(shù)時，假定這些字符都是ascii碼字符。可以預定一個字符表的結構，其中包含ascii碼表中的所有字符，以及該字符出現(xiàn)的次數(shù)。而后對用戶輸入的字符串進行遍歷，若ascii碼表中某個字符在字符串中出現(xiàn)一次，那么將其對應在字符表結構中的次數(shù)加1。字符表結構的定義如下：typedef struct char data128;/ascii碼表中的所有字符int freq128; /每個字符出現(xiàn)的次數(shù)，初始為0chartable;2）編寫selectcharactor函數(shù)來實現(xiàn)篩選字符表的0次字符。然而此時字符

11、表中存在許多出現(xiàn)次數(shù)為0的字符，因此不能夠直接通過得到的字符表來構造哈夫曼樹，需要篩選那些字符表結構中次數(shù)為0的字符，剩下在字符串中出現(xiàn)過的字符及其權值。3）編寫huffmantree函數(shù)來實現(xiàn)構造哈夫曼樹，樹結點保存在 huf 數(shù)組中。在獲取這些字符及其權值后，就可以構建哈夫曼樹：哈夫曼樹的結點類型是左右孩子域、雙親域、數(shù)據域和權值域。哈夫曼樹可以通過一個一維結點類型數(shù)組來表示。對于具有n個葉子結點的哈夫曼樹，其結點個數(shù)為2n-1，若將這2n-1個結點用一個一維數(shù)組來儲存，可以將葉子結點存放在數(shù)組的前n個位置，而將分支結點放在后n-1個位置。然后依次從huf數(shù)組中選出兩個權值最小的根結點，并

12、用它們來構造一棵新的二叉樹，對于已經構造二叉樹的結點不再參與二叉樹的構造，而有它構成的二叉樹的根結點就才參與新的二叉樹的構造。4）編寫huffmancode函數(shù)來實現(xiàn)構造哈夫曼編碼，編碼值保存在code數(shù)組中。每個結點的哈夫曼編碼都是由0和1組成的序列，因此可以通過一個字符類型的數(shù)組來保存每個結點的哈夫曼編碼；同時，由于每個結點的哈夫曼編碼的長度是不同的，那么還需要增加一個標志域start來表示編碼的起始位置，這樣從start開始的所有的值都是編碼值。哈夫曼編碼的結構為：typedef struct char codehuffman_maxvalue1;/哈夫曼編碼值int start; /編

13、碼起始位置 hufcode;在構造的哈夫曼樹中，其結點都存放在數(shù)組huf中，并且該數(shù)組的前n個位置存放的葉子結點，而后n-1個位置存放的是分支結點。為了方便哈夫曼編碼的實現(xiàn)，講從葉子結點到根的路徑進行編碼。因此首先將哈夫曼編碼的start域初始化為n，然后當結點為雙親結點的左孩子時，將編碼賦值為0；否則賦值為1。同時將start值減1，直到到達根結點為止。5）編寫huffmandecode函數(shù)來實現(xiàn)構造哈夫曼譯碼，字符串保存在recode數(shù)組中。在對二進制串進行譯碼時，首先從哈夫曼樹的祖父結點開始，哈夫曼樹的祖父結點就是哈夫曼樹結點數(shù)組的最后一個，也就是2n-1個哈夫曼樹結點，按照字符串中的“

14、0”或“1”來查找左孩子結點或者右孩子結點。若達到葉子結點，葉子結點的左孩子域和右孩子域都是-1，則譯出其中字符，而后再從根結點重新出發(fā)按照之前的順序譯出其他字符。3.2 抽象數(shù)據類型樹的抽象數(shù)據類型定義：adt stack數(shù)據對象：d=ai|aielemset,i=1,2,.,n, n0數(shù)據關系：若d為空集，則稱為空樹。若d僅為一個數(shù)據元素，r為空集，否則r=h，h是如下的二元關系：1）再d中存在唯一的稱為根的數(shù)據元素root，它在關系h下無前驅。2）若d-root空集，則存在一個劃分d1，d2，dm（m0）。3）對應于d-root的劃分，h-root，x1，有唯一的一個劃分h1，h2，hm

15、（m0）?；静僮鳎篿nittree(&t)操作結果：構造空樹t。destroytree(&t)初始條件：樹t已存在。操作結果：樹t被銷毀。cleartree(&t)初始條件：樹t已存在。操作結果：將樹t清為空棧。treeempty(t)初始條件：樹t已存在。操作結果：若樹t為空，則返回true，否則false。treedepth(t)初始條件:樹t已存在。操作結果：返回t的深度。root（t）初始條件：樹t已存在。操作結果：返回樹t的根。3.3 主程序流程主程序的流程圖如圖2.1所示：開始結束輸入原文字符串統(tǒng)計出字符的頻率 篩選頻率不為0的字符構建哈夫曼樹哈夫曼編碼輸出字符對應的哈夫曼編碼

16、輸入二進制串 哈夫曼譯碼輸出原文字符串 圖2.1 主程序流程圖3.4 各程序模塊的關系哈夫曼編譯碼程序主要是由以下幾個模塊組成：主程序模塊、構造哈夫曼樹模塊、哈夫曼編碼模塊、哈夫曼譯碼模塊、統(tǒng)計次數(shù)模塊、篩選字符模塊。主程序調用其它子函數(shù)，子函數(shù)之間沒有進行互相調用，各程序模塊的關系圖如圖2.2所示。構造哈夫曼樹構造哈夫曼編碼哈夫曼譯碼統(tǒng)計字符出現(xiàn)次數(shù)選出次數(shù)不為0的字符主程序圖2.2 各程序模塊的關系圖4 詳細設計4.1 數(shù)據類型的定義1）哈夫曼樹結點結構類型：typedef struct nodetype node; /數(shù)據域weighttype weight;/權值域int parent

17、; /雙親域int lchild; /左孩子域int rchild; /右孩子域 hufnode;2）哈夫曼編碼結構類型：typedef struct char codehuffman_maxvalue1;/哈夫曼編碼值int start; /編碼起始位置 hufcode;3）字符表結構類型：typedef structchar data128;/ascii碼表中的所有字符int freq128; /每個字符出現(xiàn)的次數(shù)，初始為0 chartable;4）程序中所需的一些其他類型定義：#define huffman_maxvalue32767 /默認權值最大#define huffman_max

18、value1 20 /默認編碼長度typedef char nodetype; /定義char類型是哈夫曼碼類型typedef int weighttype; /定義int類型是權值類型4.2 主要模塊的描述4.2.1 主要模塊算法描述1）構建哈夫曼樹模塊的偽碼算法如下：void huffmantree(nodetype node, weighttype weight, int n,hufnode huf)int i,j=0,w1,w2,node1,node2;a(&n,&i,&node,&huf); /初始化哈夫曼樹后，n-1個節(jié)點的權值域全為0for (i = n; i 2*n-1; i+

19、)w1 = huffman_maxvalue;w2 = huffman_maxvalue;node1 = node2 = -1;for (int j = 0; j = i-1; j+)if(hufj.parent != -1) continue;if(hufj.weight w1)w2 = w1, node2 = node1;w1 = hufj.weight;node1 = j;else if(hufj.weight w2)w2 = hufj.weight;node2 = j;/置兩個權值最小的節(jié)點及其雙親節(jié)點數(shù)據hufi.weight=hufnode1.weight+hufnode2.wei

20、ght;hufi.lchild=node1,hufi.rchild=node2;hufnode1.parent=i,hufnode2.parent=i;2）構建哈夫曼編碼模塊的偽碼算法如下：void huffmancode(hufnode node, int n, hufcode code)int i,parent,lchild;hufcode hufcode;for(i=0;in;i+) /計算每個葉子節(jié)點的赫夫曼編碼hufcode.start=n;hufcode.codehufcode.start+1=0;lchild=i,parent=nodei.parent;a(&parent,&no

21、de,&hufcode,& lchild);/沒有到達根節(jié)點，則編碼繼續(xù)hufcode.start+;codei=hufcode;3）哈夫曼譯碼模塊的偽碼算法如下：void huffmandecode(hufnode node, char *str, nodetype recode, int n)int i,j,k=0;j=2*n-2;for(i=0;stri!=0;j=2*n-2) /掃描整個字符串a(&i,&j,&node,&str) /找到葉子結點recodek+=nodej.node;recodek=0;4.2.2 主要算法流程圖描述1）構建哈夫曼樹模塊的流程圖如圖3.1所示。兩個權值

22、最小的結點及其雙親結點數(shù)據否是否否結束開始i2*n-1i2*n-1后n-1個結點的權值域為0i+i+初始化最小結點，默認為-1ji-1否葉子結點權值小于w1得到最小較小權值賦值給w1，w2=w1得到最小較小權值賦值給w2j+是是是是否圖3.1 構建哈夫曼樹模塊的流程圖2）構建哈夫曼編碼模塊的流程圖如圖3.2所示。3）哈夫曼譯碼模塊的流程圖如圖3.3所示。是否開始結束in初始化哈夫曼編碼類型hufcode否是到達根結點左孩子相同否是左孩子編碼右孩子編碼i+下一個結點下一個葉子結點開始結束字符串結束是否是否是否字符為“0”沒有左右孩子查找左孩子查找右孩子譯出葉結點數(shù)據域圖3.2 哈夫曼編碼模塊的流

23、程圖 圖3.3 哈夫曼譯碼模塊的流程圖5 調試分析5.1 調試問題分析1）問題：輸出字符串的時候，后面附帶一部分亂碼。解決方法：在字符串最后一個有效值的后面置0，結束字符串。2）問題：輸入字符過多的時候不能正確編碼。解決方法：增大字符串的存儲空間。5.2 算法時空分析算法的時空說明如下所示，n表示輸入的字符串的不同字符的個數(shù)。1）主函數(shù)的時間復雜度是s(128)（當n128時）；主函數(shù)的空間復雜度是t(1)；2）統(tǒng)計次數(shù)函數(shù)的時間復雜度是s(n2)；統(tǒng)計次數(shù)函數(shù)的空間復雜度是t(1)；3）篩選字符函數(shù)的時間復雜度是s(n)；篩選字符函數(shù)的空間復雜度是t(1)；4）構造哈夫曼樹函數(shù)的時間復雜度是

24、s(4n2)；構造哈夫曼樹函數(shù)的空間復雜度是t(1)；5）哈夫曼編碼函數(shù)的時間復雜度是s(n2)；哈夫曼編碼函數(shù)的空間復雜度是t(n)；6）哈夫曼譯碼函數(shù)的時間復雜度是s(n2)；哈夫曼譯碼函數(shù)的空間復雜度是t(1)。6 用戶使用說明程序運行的主界面后將需要用戶根據以下要求進行使用：1）用戶根據提示輸入原文字符串。輸入字符串之后程序就會輸出相應的哈夫曼編碼表，包括字符、出現(xiàn)次數(shù)和對應哈夫曼編碼。2）用戶根據編碼成功的哈夫曼編碼輸入相應的二進制串。輸入二進制串之后，程序就會輸出譯出對應的原文字符串。3）譯碼成功后根據提示是否繼續(xù)譯碼，用戶需要輸入y or n。在程序輸出譯碼完成的原文字符串之后將

25、會提示是否繼續(xù)譯碼，是以原來的哈夫曼編碼進行重新的譯碼，需要用戶輸入y之后再一次輸入需要譯碼的二進制串。4）不再進行譯碼時根據提示是否繼續(xù)編譯碼，用戶需要輸入y or n。在程序輸出譯碼完成的原文字符串并且不再繼續(xù)譯碼之后，程序將會提示是否繼續(xù)編譯碼，是以新的字符串進行重新的編譯碼，需要用戶輸入y之后再一次輸入原文字符串。5）該程序在開頭的時候會進行自動演示，指導用戶如何進行操作。如圖5.1所示。圖5.1 自動演示7 測試結果7.1 詳細測試分析輸入的字符串是：i love you輸入的二進制串是：101111110111101輸入的字符串轉換成字符分別是：sp（空格）、e、i、l、o、u、v

26、、y；對應次數(shù)分別是2、1、1、1、2、1、1、1。構造出哈夫曼樹如圖6.1所示。sp/2o/1e/1i/1l/1u/1v/1y/122244610圖6.1 哈夫曼樹所有字符對應的哈夫曼編碼分別為110、000、001、010、111、011、100、101。輸入的二進制字符串的時候，從根結點開始，依次根據“0”或者“1”，查找左孩子和右孩子，直到找到葉子結點，以字符101譯碼過程為例進行分析，如圖6.2所示。sp/2o/1e/1i/1l/1u/1v/1y/122244610101圖6.2 字符101的譯碼過程程序測試的結果如圖6.3所示。圖6.3 測試結果7.2 各種情況測試分析1）輸入字符

27、串為data strutures（由大小寫字母和空格組成）輸入二進制串為 00110011100111100011110001000100結果如圖6.4所示。圖6.4 測試用例12）輸入字符串為201312182013（由數(shù)字組成）輸入二進制串為 01101110111101100結果如圖6.5所示。圖6.5 測試用例23）輸入字符串為78jfjs _-+sj =.（由字母、數(shù)字、符號和空格組成）輸入二進制串為 0000111101111110110100100結果如圖6.6所示。圖6.6 測試用例34）輸入字符串為huhugug78 78gh（由字母、數(shù)字和空格組成）輸入二進制串為 1110

28、00102101（出現(xiàn)非二進制字符在字符串中）只完成非二進制字符前的譯碼，遇到非二進制將會停止并警告。結果如圖6.7所示。圖6.7 測試用例45）輸入字符串為huhugug77（由字母和數(shù)字組成）輸入二進制串為 +0001（出現(xiàn)非二進制字符在字符串首）遇到非二進制將會停止并警告，非二進制在字符串首直接停止。結果如圖6.8所示。圖6.8 測試用例56）輸入字符串為njnjnjwxwxwx（由字母組成）輸入二進制串為 11100001測試譯碼完成是否繼續(xù)正確譯碼，測試編譯碼完成是否繼續(xù)編譯碼。結果如圖6.9所示。圖6.9 測試用例68 結 論8.1 總結在當今信息時代，如何采用有效的數(shù)據壓縮技術來

29、節(jié)省數(shù)據文件的存儲空間和計算機網絡的傳送時間已越來越引起人們的重視，哈夫曼編碼正是一種應用廣泛且非常有效的數(shù)據壓縮技術。正因為哈夫曼編碼是一種根據字母的使用頻率而設計的變長碼,能提高信息的傳輸效率,至今仍有廣泛的應用。但是采用哈夫曼編碼時有個問題值得注意：哈夫曼碼沒有錯誤保護功能，在譯碼時，如果碼串中沒有錯誤，那么就能一個接一個地正確譯出代碼。但如果碼串中有錯誤，哪怕僅是1位出現(xiàn)錯誤，不但這個碼本身譯錯，更糟糕的是后面的數(shù)據串也會接著被譯錯，全亂了套，這種現(xiàn)象稱為錯誤傳播(errorpropagation)。計算機對這種錯誤也無能為力，說不出錯在哪里，更談不上去糾正它。8.2 個人心得通過這次

30、課程設計使我充分的理解了用哈夫曼樹編碼譯碼問題中基本原理的應用，知道了樹的不同存儲結構的定義和算法描述，同時也學會了編寫簡單的哈夫曼編碼譯碼問題的程序。雖然此次的程序不夠完善，但是總體還是一個能體現(xiàn)數(shù)據結構知識點能力的程序。在剛開始編程的時候，無從下手。但是困難是可以解決的，只要通過努力，向老師虛心學習請教，再難的題目也可以自己動手完成。通過這次的數(shù)據結構課程設計，我也深刻了解到這門學問的博大精深，要積極進取，不斷學習，不斷積累知識。同時也認識到自己的不足和缺點，做什么事都需要細心和耐心，并堅持下去，這樣才還有一個比較滿意的成果。在此我要感謝的是我的指導老師，感謝老師的細心認真的輔導，讓我對數(shù)

31、據結構這門課程有了跟深刻的認識，同時我還要感謝幫助過我的同學，沒有他們的幫助我不肯能完成這樣順利，謝謝。參考文獻1 陳越.數(shù)據結構m.第一版.北京:高等教育出版社,2012:142-150.2 鄭阿奇.數(shù)據結構實用教程（c語言版）m.第一版.北京:電子工業(yè)出版社,2011:170-179.3 張基溫.新概念c程序設計大學教程m.第一版.北京:清華大學出版社,2012:143-155.4 嚴蔚敏,吳偉民.數(shù)據結構（c語言版）m.第一版.北京:清華大學出版社,2011:203-206.5 克尼漢.c程序設計語言m.第二版.北京:機械工業(yè)出版社,2004:111-130.附 錄#define huf

32、fman_maxvalue32767#define huffman_maxvalue1 20#include#include#includetypedef char nodetype;typedef int weighttype;typedef struct nodetypenode;/數(shù)據域weighttype weight;/權值域int parent;/雙親域int lchild; /左孩子域int rchild; /右孩子域hufnode;typedef struct charcodehuffman_maxvalue1;/哈夫曼編碼值intstart;/編碼起始位置 hufcode;/

33、字符表結構typedef struct chardata128;/ascii碼表中的所有字符intfreq128;/每個字符出現(xiàn)的次數(shù)，初始為0chartable;void huffmantree(nodetype node,weighttype weight,int n,hufnode huf);/構造哈夫曼樹，樹節(jié)點保存在 huf 數(shù)組中void huffmancode(hufnode node,int n,hufcode code);/構造哈夫曼編碼，編碼值將保存在code數(shù)組中void huffmandecode(hufnode node,char *str,nodetype reco

34、de,int n);/哈夫曼譯碼int frequencycounter(char *str,chartable *table,int n);/統(tǒng)計字符出現(xiàn)的次數(shù)int selectcharactor(chartable *org,int n,chartable *res);/選出出現(xiàn)次數(shù)不為0的字符void autoout();/自動演示/程序主函數(shù)int main()int i,j,n;char k=y,l=y;char string256;/保存用戶輸入的緩沖區(qū)hufnode *hufnode;/哈夫曼樹節(jié)點hufcode *hufcode;/哈夫曼編碼nodetype *hufdeco

35、de;chartable table;/初始字符表chartable chars;/不包含次數(shù)為0的字符表autoout(); /自動演示while(k!=n&k!=n)l=y;for(i=0;i請輸入需要編碼的字符串：); gets(string); /統(tǒng)計字符出現(xiàn)的頻率 n = frequencycounter(string, &table, 128); /統(tǒng)計字符出現(xiàn)的次數(shù) n = selectcharactor(&table ,128, &chars);/選出次數(shù)不為0的字符 /構造哈夫曼樹 hufnode = (hufnode*)malloc(2*n+1) * sizeof(hufn

36、ode); huffmantree(chars.data, chars.freq, n, hufnode); /哈夫曼編碼 hufcode = (hufcode*)malloc(n * sizeof(hufcode); huffmancode(hufnode, n, hufcode); printf(n 原文字符t出現(xiàn)次數(shù)thaffman 編碼n); printf(=n); /輸出哈夫曼編碼值 for(i=0; i請輸入需要譯碼的二進制串：); gets(string); hufdecode = (nodetype*)malloc(256 * sizeof(nodetype); huffman

37、decode(hufnode,string,hufdecode,n); printf(n譯碼完成的原文字符串是：%sn,hufdecode);printf(n譯碼完畢，是否繼續(xù)譯碼？(y/n); scanf( %c,&l);getchar(); printf(n哈夫曼編譯碼器編譯碼完畢，是否繼續(xù)?(y/n); scanf( %c,&k);getchar();printf(n - n);printf(ttt感謝使用哈夫曼編譯碼系統(tǒng)n);getchar();/free(hufnode);/free(hufnode);return 0;/構造哈夫曼樹，樹節(jié)點保存在 huf 數(shù)組中void huffm

38、antree(nodetype node,weighttype weight,int n,hufnode huf)int i,j=0,w1,w2,node1,node2;for (i = 0; i 2*n-1; i+)/初始化哈夫曼樹hufi.node = in ? nodei : 0;hufi.weight = in ? weighti : 0;/后n-1個節(jié)點的權值域全為0hufi.parent = hufi.lchild = hufi.rchild = -1;for (i = n; i 2*n-1; i+)w1 = huffman_maxvalue;w2 = huffman_maxval

39、ue;node1 = node2 = -1;for (int j = 0; j = i-1; j+)/尋找兩個權值最小的節(jié)點node1和node2if(hufj.parent != -1) continue;if(hufj.weight w1)w2 = w1, node2 = node1;w1 = hufj.weight;node1 = j;else if(hufj.weight w2)w2 = hufj.weight;node2 = j;/置兩個權值最小的節(jié)點及其雙親節(jié)點數(shù)據hufi.weight=hufnode1.weight+hufnode2.weight;hufi.lchild=nod

40、e1,hufi.rchild=node2;hufnode1.parent=i,hufnode2.parent=i;/構造哈夫曼編碼，編碼值將保存在code數(shù)組中void huffmancode(hufnode node,int n,hufcode code)int i,parent,lchild;hufcode hufcode;for(i=0;in;i+)/計算每個葉子節(jié)點的赫夫曼編碼hufcode.start=n;hufcode.codehufcode.start+1=0;lchild=i,parent=nodei.parent;while(parent != -1)/沒有到達根節(jié)點，則編碼繼續(xù)if(nodeparent.lchild=lchild)hufcode.codehufcode.start=0;/左孩子編碼elsehufcode.codehufcode.start=1;/右孩子編碼hufcode.start-;lchild=parent,parent=nodeparent.parent; hufcode.start+;codei=hufcode;/哈夫曼譯碼v