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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題 目： 哈夫曼編/譯碼器 院 （系）： 計算機(jī)工程學(xué)院 專 業(yè)： 信息與計算科學(xué) 班 級： 0902 學(xué) 生： 陳輝 指導(dǎo)教師： 2010年 12月目錄 1實驗?zāi)康?2概要設(shè)計22.1 總體功能結(jié)構(gòu)22.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計42.3 方法及原理53詳細(xì)設(shè)計和實現(xiàn)63.1 創(chuàng)建huffman樹63.2 編碼93.3 譯碼114調(diào)試與操作說明13總 結(jié)16 1實驗?zāi)康脑O(shè)計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項目，直到選擇退出為止?！净疽蟆?1)初始化：鍵盤輸入字符集大小n、n個字符和n個權(quán)值，建立哈夫曼樹；(2)編碼：利用建好的哈夫曼樹生成哈夫曼編碼；(3

2、)輸出編碼；(4)譯碼功能；(5)設(shè)字符集及頻度如下表：字符 空格 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頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1通過此次課程設(shè)計主要達(dá)到以下目的：1了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；2初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；3提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；4訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)

3、范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。本程序采用visual c+編程實現(xiàn)。2概要設(shè)計2.1 總體功能結(jié)構(gòu) 本程序的主要功能是實現(xiàn)對用戶輸入的字符編碼，然后再把編碼結(jié)果翻譯成原字符。但在進(jìn)行這些操作之前必須做一項工作，就是創(chuàng)建huffman樹。哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(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é)點的二叉樹

4、，相應(yīng)的葉結(jié)點的路徑長度為li(i=1,2,.n)?？梢宰C明哈夫曼樹的wpl是最小的。哈夫曼在上世紀(jì)五十年代初就提出這種編碼時，根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴(yán)格按照碼字所對應(yīng)符號出現(xiàn)概率的大小的逆序排列，則編碼的平均長度是最小的。總體功能流程如下圖：2.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計2.2.1 huffman結(jié)點結(jié)構(gòu) huffman結(jié)點結(jié)構(gòu)是本程序的基本結(jié)構(gòu)，所有操作都在此上進(jìn)行。其中包括存儲字符的元素data，字符的權(quán)值weight，以及左右孩子指針和父指針。 typedef struct char data;/結(jié)點值 int weight;/權(quán)值

5、 int parent;/父結(jié)點指針 int left; /左孩子結(jié)點指針 int right;/右孩子結(jié)點指針huffnode;2.2.2 編碼結(jié)構(gòu)編碼結(jié)構(gòu)用于存儲每個字符的編碼，包括用于存儲編碼的數(shù)組和用于記錄編碼個數(shù)的元素。整個結(jié)構(gòu)相當(dāng)于一個棧結(jié)構(gòu)，采用棧形式存儲編碼。typedef struct int cdm;/編碼串 int top; /串的大小huffcode;2.3 方法及原理2.3.1創(chuàng)建huffman樹 本文創(chuàng)建huffman樹是在順序鏈表的基礎(chǔ)上進(jìn)行的，建樹原理如下： 1、根據(jù)給定的n個權(quán)值w1,w2,w3,wn，構(gòu)造具有n棵二叉樹的森林f=t1,t2,t3,tn，其中每

6、棵二叉樹ti只有一個帶權(quán)值wi的根結(jié)點，其左右子樹均為空。2、重復(fù)以下步驟，直到f中僅剩下一棵樹為止： (1)在f中選取兩棵根結(jié)點的權(quán)值最小的二叉樹，作為左右子樹構(gòu)造一棵新的二叉樹。使新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和。 (2)在f中刪去這兩棵二叉樹，把新的二叉樹加入f。最后得到的就是huffman樹。2.3.2 編碼 編碼操作需在建立好huffman樹的基礎(chǔ)上進(jìn)行。二叉樹的葉子結(jié)點標(biāo)記字符，由根結(jié)點沿著二叉樹路徑下行，左分支標(biāo)記為0，右分支標(biāo)記為1，則每條從根結(jié)點到葉子結(jié)點的路徑唯一表示了該葉結(jié)點的二進(jìn)制編碼。編碼的時候，我們采用從葉子結(jié)點向上回溯的方法編碼，如果當(dāng)前結(jié)點

7、是其父結(jié)點的左孩子，則編碼為0，如果是右孩子，則編碼為1，如此回溯，直到父結(jié)點為空時，該字符的編碼就結(jié)束了，對應(yīng)編碼結(jié)構(gòu)中的編碼數(shù)組就是該字符的編碼。如此操作，直到所有葉子結(jié)點都掃描一遍為止，即編碼結(jié)束。2.3.3 譯碼 譯碼操作也是在前面創(chuàng)建的huffman樹的基礎(chǔ)上進(jìn)行。對譯碼字符串從頭往后掃描，如果是1，則當(dāng)前指針指向右孩子，如果是0，則指向左孩子。如此下去，直到指針為空時，當(dāng)前結(jié)點的data值就是譯碼。然后再從頭開始掃描，進(jìn)行上面操作，當(dāng)編碼字符串掃描結(jié)束時，譯碼結(jié)束。3詳細(xì)設(shè)計和實現(xiàn)3.1 創(chuàng)建huffman樹3.1.1 功能描述 huffman樹是整個程序的核心部分，是編碼譯碼操作

8、的前提。哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴(yán)格按照碼字所對應(yīng)符號出現(xiàn)概率的大小的逆序排列，則編碼的平均長度是最小的。3.1.2 算法原理首先根據(jù)用戶輸入創(chuàng)建n棵子樹的森林，然后對所有子樹掃描，找出權(quán)值最小的兩個子樹，把它們合并成一棵新的子樹，同時把它們的權(quán)值之和作為新樹的權(quán)值。把這兩棵子樹刪掉，再把新樹加如到森林中，然后再掃描出權(quán)值最小的兩棵子樹，接著進(jìn)行同樣的操作，直到只剩下一棵樹即為huffman樹。3.3.3 算法流程 3.3.4 具體程序void select(huffnode

9、hn,int k,int &s1,int &s2)/選取父結(jié)點為空且權(quán)值最小的兩個結(jié)點int minw=200;/暫存最小權(quán)值int i;for(i=1;i=k;i+)if(hni.weightminw&hni.parent=0)minw=hni.weight;s1=i;/s1存儲權(quán)值最小結(jié)點編號minw=200;for(i=1;i=k;i+)if(hni.weightminw&hni.parent=0&i!=s1)minw=hni.weight;s2=i;/s2存儲權(quán)值第二小的結(jié)點編號void creatht(huffnode hn,int n)/創(chuàng)建huffman樹int i;int s1

10、,s2;for(i=n;i2*n-1;i+)select(hn,i,s1,s2);hns1.parent=i+1;hns2.parent=i+1;hni+1.left=s1;hni+1.right=s2;hni+1.weight=hns1.weight+hns2.weight;3.2 編碼 3.2.1 功能描述 編碼的功能就是把字符轉(zhuǎn)換成二進(jìn)制數(shù)來存儲 3.2.2 算法原理編碼的時候，我們采用從葉子結(jié)點向上回溯的方法編碼，如果當(dāng)前結(jié)點是其父結(jié)點的左孩子，則編碼為0，如果是右孩子，則編碼為1，如此回溯，直到父結(jié)點為空時，該字符的編碼就結(jié)束了，對應(yīng)編碼結(jié)構(gòu)中的編碼數(shù)組就是該字符的編碼。如此操作，直

11、到所有葉子結(jié)點都掃描一遍為止，即編碼結(jié)束。 3.2.3 算法流程 3.2.4 具體程序 void encode(huffnode hn,int n,huffcode hc)/編碼函數(shù) int i,j,p; for(i=1;i=n;i+)/對每個字符編碼 int t=-1; j=i; while(hnj.parent!=0)/當(dāng)前結(jié)點的父結(jié)點非空 p=j; j=hnj.parent; if(hnj.left=p)/如果當(dāng)前結(jié)點是父結(jié)點的左孩子，則編碼為0 hci.cd+t=0; if(hnj.right=p)/如果當(dāng)前結(jié)點是父結(jié)點的右孩子，則編碼為1 hci.cd+t=1; hci.top=t;

12、/存儲編碼串大小 3.3 譯碼 3.3.1 功能描述 譯碼功能主要是把二進(jìn)制編碼翻譯成字符形式。 3.3.2 算法原理 從頭往后掃描待譯字符串，如果是1，則當(dāng)前指針指向右孩子，如果是0，則指向左孩子。如此下去，直到指針為空時，當(dāng)前結(jié)點的data值就是譯碼。然后再從頭開始掃描，進(jìn)行上面操作，當(dāng)編碼字符串掃描結(jié)束時，譯碼結(jié)束。 3.3.3 算法流程 3.3.4 具體程序 void decode(huffnode hn,int n,int str)/譯碼函數(shù)int k=0;int p;while(strk=0|strk=1)/待譯碼串值不為1或0退出循環(huán)，即譯碼結(jié)束p=2*n-1;while(hnp

13、.left!=0)/當(dāng)前結(jié)點存在孩子結(jié)點if(strk=1)/如果待譯碼值為1，則指針指向右孩子p=hnp.right;if(strk=0)/如果待譯碼值為0，則指針指向左孩子p=hnp.left;k+;couthnp.data;coutendl;4調(diào)試與操作說明由上文的分析可見，在運行程序時，需先輸入需要編碼的字符串，然后根據(jù)輸入的字符的權(quán)重創(chuàng)建huffman樹，接著再進(jìn)行編碼操作，最后再把所得的編碼進(jìn)行譯碼，各步操作之間存在先后關(guān)系，因此在運行程序時必須注意所選擇的操作的先后順序。具體程序運行過程舉例如下：總結(jié)我們這次做的是哈弗曼編碼譯碼器。在當(dāng)今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲空間和計算機(jī)網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視，哈夫曼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每一個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各葉子對應(yīng)的字符的編碼，這就是哈夫曼編碼。由于我的基礎(chǔ)不太好，我主要做的只是哈弗曼樹的創(chuàng)建和編碼的一部分，首先進(jìn)行初始化：鍵盤輸入字符集大小n、n個字符和n個權(quán)值，建立哈夫曼樹本文創(chuàng)建huffman樹是在順序鏈表的基礎(chǔ)上進(jìn)行的，編碼