《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告哈夫曼編譯碼器程序設(shè)計(jì)

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

2、最短的碼字，有時(shí)稱之為最佳編碼，一般就叫作huffman編碼（有時(shí)也稱為霍夫曼編碼）。哈夫曼編碼適用于多遠(yuǎn)獨(dú)立信源,對(duì)于多元獨(dú)立信源來說它是最佳碼。但其存在的不足直接制約了它的廣泛應(yīng)用。本設(shè)計(jì)主要介紹了哈夫曼編碼算法、譯碼算法等功能的程序?qū)崿F(xiàn)。關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；哈夫曼編碼；哈夫曼樹；譯碼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ù)據(jù)分析22.2 功能要求23 概要設(shè)計(jì)33.1 設(shè)計(jì)思路33.2 抽象數(shù)據(jù)類型43.3 主程序流程53.4 各程序模塊的關(guān)系64 詳細(xì)設(shè)計(jì)74.1 數(shù)據(jù)類型的定義74.2 主要模塊的描述84.2.1 主要模塊算法描述84.2.2 主要算法流程圖描述105 調(diào)試分析125.1 調(diào)試問題分析125.2

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

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

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

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

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

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

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

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

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

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

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

18、value1 20 /默認(rèn)編碼長(zhǎng)度typedef char nodetype; /定義char類型是哈夫曼碼類型typedef int weighttype; /定義int類型是權(quán)值類型4.2 主要模塊的描述4.2.1 主要模塊算法描述1）構(gòu)建哈夫曼樹模塊的偽碼算法如下：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個(gè)節(jié)點(diǎn)的權(quán)值域全為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;/置兩個(gè)權(quán)值最小的節(jié)點(diǎn)及其雙親節(jié)點(diǎn)數(shù)據(jù)hufi.weight=hufnode1.weight+hufnode2.wei

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

21、de,&hufcode,& lchild);/沒有到達(dá)根節(jié)點(diǎn)，則編碼繼續(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) /掃描整個(gè)字符串a(chǎn)(&i,&j,&node,&str) /找到葉子結(jié)點(diǎn)recodek+=nodej.node;recodek=0;4.2.2 主要算法流程圖描述1）構(gòu)建哈夫曼樹模塊的流程圖如圖3.1所示。兩個(gè)權(quán)值

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

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

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

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

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

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

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

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

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

31、據(jù)結(jié)構(gòu)這門課程有了跟深刻的認(rèn)識(shí)，同時(shí)我還要感謝幫助過我的同學(xué)，沒有他們的幫助我不肯能完成這樣順利，謝謝。參考文獻(xiàn)1 陳越.數(shù)據(jù)結(jié)構(gòu)m.第一版.北京:高等教育出版社,2012:142-150.2 鄭阿奇.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（c語言版）m.第一版.北京:電子工業(yè)出版社,2011:170-179.3 張基溫.新概念c程序設(shè)計(jì)大學(xué)教程m.第一版.北京:清華大學(xué)出版社,2012:143-155.4 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（c語言版）m.第一版.北京:清華大學(xué)出版社,2011:203-206.5 克尼漢.c程序設(shè)計(jì)語言m.第二版.北京:機(jī)械工業(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ù)據(jù)域weighttype weight;/權(quán)值域int parent;/雙親域int lchild; /左孩子域int rchild; /右孩子域hufnode;typedef struct charcodehuffman_maxvalue1;/哈夫曼編碼值intstart;/編碼起始位置 hufcode;/

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

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

35、de;chartable table;/初始字符表chartable chars;/不包含次數(shù)為0的字符表autoout(); /自動(dòng)演示while(k!=n&k!=n)l=y;for(i=0;i請(qǐng)輸入需要編碼的字符串：); gets(string); /統(tǒng)計(jì)字符出現(xiàn)的頻率 n = frequencycounter(string, &table, 128); /統(tǒng)計(jì)字符出現(xiàn)的次數(shù) n = selectcharactor(&table ,128, &chars);/選出次數(shù)不為0的字符 /構(gòu)造哈夫曼樹 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請(qǐng)輸入需要譯碼的二進(jìn)制串：); 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;/構(gòu)造哈夫曼樹，樹節(jié)點(diǎn)保存在 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個(gè)節(jié)點(diǎn)的權(quán)值域全為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+)/尋找兩個(gè)權(quán)值最小的節(jié)點(diǎn)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;/置兩個(gè)權(quán)值最小的節(jié)點(diǎn)及其雙親節(jié)點(diǎn)數(shù)據(jù)hufi.weight=hufnode1.weight+hufnode2.weight;hufi.lchild=nod

40、e1,hufi.rchild=node2;hufnode1.parent=i,hufnode2.parent=i;/構(gòu)造哈夫曼編碼，編碼值將保存在code數(shù)組中void huffmancode(hufnode node,int n,hufcode code)int i,parent,lchild;hufcode hufcode;for(i=0;in;i+)/計(jì)算每個(gè)葉子節(jié)點(diǎn)的赫夫曼編碼hufcode.start=n;hufcode.codehufcode.start+1=0;lchild=i,parent=nodei.parent;while(parent != -1)/沒有到達(dá)根節(jié)點(diǎn)，則編碼繼續(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