哈夫曼樹及其應(yīng)用完美版

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)題目： 哈夫曼樹及其應(yīng)用 學(xué) 院：計(jì)算機(jī)科學(xué)與技術(shù) 專 業(yè)：網(wǎng) 絡(luò) 工 程 班 級(jí)：網(wǎng) 絡(luò) 131 學(xué) 號(hào)：1308060312 學(xué)生姓名：謝 進(jìn) 指導(dǎo)教師：葉 潔2015年 7 月 12 日設(shè)計(jì)目的： 赫夫曼編碼的應(yīng)用很廣泛，利用赫夫曼樹求得的用于通信的二進(jìn)制編碼稱為赫夫曼編碼。樹中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個(gè)葉子對(duì)應(yīng)的字符的編碼，這就是赫夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進(jìn)制代碼，輸入二進(jìn)制代碼時(shí)可以編譯成字符串。1、熟悉樹的二叉樹

2、的存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)。 2、掌握建立哈夫曼樹和哈夫曼編碼的方法。 設(shè)計(jì)內(nèi)容：欲發(fā)一封內(nèi)容為AABBCAB (共長(zhǎng) 100 字符,字符包括A 、B 、C 、D 、E 、F六種字符)，分別輸入六種字符在報(bào)文中出現(xiàn)的次數(shù)（次數(shù)總和為100）， 對(duì)這六種字符進(jìn)行哈夫曼編碼。設(shè)計(jì)要求：對(duì)輸入的一串電文字符實(shí)現(xiàn)赫夫曼編碼，再對(duì)赫夫曼編碼生成的代碼串進(jìn)行譯碼，輸出電文字符串。通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報(bào)通信是傳遞文字的二進(jìn)制碼形式的字符串。但在信息傳遞時(shí)，總希望總長(zhǎng)度能盡可能短，即采用最短碼。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi，編碼長(zhǎng)度為L(zhǎng)i，電文中有n種字符，則電文編碼總長(zhǎng)

3、度為WiLi。若將此對(duì)應(yīng)到二叉樹上，Wi為葉結(jié)點(diǎn)的權(quán)，Li為根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長(zhǎng)度。那么，WiLi恰好為二叉樹上帶權(quán)路徑長(zhǎng)度。因此 ，設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵赫夫曼樹，此構(gòu)造過程稱為赫夫曼編碼。設(shè)計(jì)實(shí)現(xiàn)的功能： 1.以二叉鏈表存儲(chǔ)， 2.建立哈夫曼樹； 3.求每個(gè)字符的哈夫曼編碼并顯示。 一：赫夫曼樹的構(gòu)造“（1）由給定的n個(gè)權(quán)值W1，W2，Wn構(gòu)成n棵二叉樹的集合FT1，T2，Tn,其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為Wi的根節(jié)點(diǎn)，其左右子樹均空。 （2）在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這

4、棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和； （3）在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合F中； （4）重復(fù)（2）（3）兩步，當(dāng)F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是所要建立的哈夫曼樹?！?二：設(shè)計(jì)概要哈夫曼編譯碼器的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進(jìn)行譯碼 。在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的二進(jìn)制串，稱之為編碼。構(gòu)造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分之代表0，右分支代表1，則從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點(diǎn)對(duì)應(yīng)字符的編碼，稱之為哈夫曼編碼。最簡(jiǎn)

5、單的二進(jìn)制編碼方式是等長(zhǎng)編碼。若采用不等長(zhǎng)編碼，讓出現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長(zhǎng)的編碼，這樣可能縮短傳送電文的總長(zhǎng)度。哈夫曼樹課用于構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。（1）其主要流程圖如圖所示。 開始結(jié)點(diǎn)數(shù)是否大于-1將data和權(quán)值賦給ht輸出根結(jié)點(diǎn)和權(quán)值調(diào)用SELECT函數(shù)計(jì)算根結(jié)點(diǎn)函數(shù)父結(jié)點(diǎn)為兩子結(jié)點(diǎn)之和輸出兩子結(jié)點(diǎn)和已構(gòu)造的結(jié)點(diǎn)是否為根結(jié)點(diǎn)？左子是否為空？此時(shí)編碼為0I<2*N?I+編碼為1結(jié)束否否否右子是否為空是是否否是是是 （2） 設(shè)計(jì)包含的幾個(gè)方面： 赫夫曼樹的建立赫夫曼樹的建立由赫夫曼算法的定義可知，初始森林中共有n棵只含有根結(jié)點(diǎn)的二叉樹。算

6、法的第二步是：將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個(gè)新結(jié)點(diǎn)。顯然要進(jìn)行n1次合并，所以共產(chǎn)生n1個(gè)新結(jié)點(diǎn)，它們都是具有兩個(gè)孩子的分支結(jié)點(diǎn)。由此可知，最終求得的赫夫曼樹中一共有2n1個(gè)結(jié)點(diǎn)，其中n個(gè)結(jié)點(diǎn)是初始森林的n個(gè)孤立結(jié)點(diǎn)。并且赫夫曼樹中沒有度數(shù)為1的分支結(jié)點(diǎn)。我們可以利用一個(gè)大小為2n-1的一維數(shù)組來存儲(chǔ)赫夫曼樹中的結(jié)點(diǎn)。 赫夫曼編碼 要求電文的赫夫曼編碼，必須先定義赫夫曼編碼類型，根據(jù)設(shè)計(jì)要求和實(shí)際需要定義的類型如下： typedet struct char ch; / 存放編碼的字符 char bitsN1; / 存放編

7、碼位串 int len; / 編碼的長(zhǎng)度 CodeNode; / 編碼結(jié)構(gòu)體類型 字符串的譯碼 譯碼的基本思想是：讀文件中編碼，并與原先生成的赫夫曼編碼表比較，遇到相等時(shí)，即取出其對(duì)應(yīng)的字符存入一個(gè)新串中。 三、 詳細(xì)設(shè)計(jì)（1）赫夫曼樹的存儲(chǔ)結(jié)構(gòu)描述為： #define N 50 / 葉子結(jié)點(diǎn)數(shù) #define M 2*N-1 / 赫夫曼樹中結(jié)點(diǎn)總數(shù) typedef struct int weight; / 葉子結(jié)點(diǎn)的權(quán)值 int lchild, rchild, parent; / 左右孩子及雙親指針 HTNode; / 樹中結(jié)點(diǎn)類型 typedef HTNode HuffmanTreeM+1

8、; 哈弗曼樹的算法void CreateHT(HTNode ht,int n) /調(diào)用輸入的數(shù)組ht,和節(jié)點(diǎn)數(shù)n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有結(jié)點(diǎn)的相關(guān)域置初值-1 for (i=n;i<2*n-1;i+) /構(gòu)造哈夫曼樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置 for (k=0;k<=i-1;k

9、+) if (htk.parent=-1) /只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找 if (htk.weight<min1) /若權(quán)值小于最小的左節(jié)點(diǎn)的權(quán)值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是i hti.weight=htlnode.weight+htrnode.weight; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值為兩個(gè)最小節(jié)點(diǎn)權(quán)值之和 hti

10、.lchild=lnode;hti.rchild=rnode; /父節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)（2）哈弗曼編碼void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;i<n;i+) /根據(jù)哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結(jié)點(diǎn)結(jié)束循環(huán) if (htf.lchild=c) /處理左孩子結(jié)點(diǎn) hc.cdhc.start-='0' else /處理右孩子結(jié)點(diǎn) hc.cdhc.start-='1&#

11、39; c=f;f=htf.parent; hc.start+; /start指向哈夫曼編碼hc.cd中最開始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼的列表 int i,k; printf(" 輸出哈夫曼編碼:n"); for (i=0;i<n;i+) /輸出data中的所有數(shù)據(jù)，即A-Z printf(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /輸出所有data中數(shù)據(jù)的編碼 printf("%c&q

12、uot;,hcdi.cdk); printf("n"); void editHCode(HTNode ht,HCode hcd,int n) /編碼函數(shù)char stringMAXSIZE; int i,j,k;scanf("%s",string); /把要進(jìn)行編碼的字符串存入string數(shù)組中printf("n輸出編碼結(jié)果:n");for (i=0;stringi!='#'i+) /#為終止標(biāo)志for (j=0;j<n;j+)if(stringi=htj.data) /循環(huán)查找與輸入字符相同的編號(hào)，相同的就輸出

13、這個(gè)字符的編碼for (k=hcdj.start;k<=n;k+) printf("%c",hcdj.cdk);break; /輸出完成后跳出當(dāng)前for循環(huán)（3）哈弗曼譯碼void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數(shù)char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s",code); /把要進(jìn)行譯碼的字符串存入code數(shù)組中while(code0!='#')for (i=0;i<n;i+)m=0; /m為想同編碼個(gè)數(shù)的計(jì)數(shù)器 for (k=hcdi.

14、start,j=0;k<=n;k+,j+) /j為記錄所存儲(chǔ)這個(gè)字符的編碼個(gè)數(shù)if(codej=hcdi.cdk) /當(dāng)有相同編碼時(shí)m值加1m+;if(m=j) /當(dāng)輸入的字符串與所存儲(chǔ)的編碼字符串個(gè)數(shù)相等時(shí)則輸出這個(gè)的data數(shù)據(jù)printf("%c",hti.data);for(x=0;codex-1!='#'x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex+j;（4）主函數(shù)void main() int n=26,i; char orz,back,flag=1; char str = 'A', 'B

15、', 'C', 'D', 'E', 'F' ; int fnum = 15, 10, 20, 18, 12, 25 ; /初始化 HTNode htM; /建立結(jié)構(gòu)體 HCode hcdN; /建立結(jié)構(gòu)體 for (i=0;i<n;i+) /把初始化的數(shù)據(jù)存入ht結(jié)構(gòu)體中 hti.data=stri; hti.weight=fnumi; while (flag) /菜單函數(shù)，當(dāng)flag為0時(shí)跳出循環(huán) （5）顯示部分源程序： printf("n"); printf(" *");

16、printf("n * 1-顯示編碼 *"); printf("n * 2-進(jìn)行編碼 *"); printf("n * 3-進(jìn)行譯碼 *"); printf("n * 4-退出 *n"); printf(" * *"); printf("n"); printf(" 請(qǐng)輸入選擇的編號(hào):"); scanf("%c",&orz); switch(orz) case 'a': case 'A': syst

17、em("cls"); /清屏函數(shù) CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); getchar(); system("cls"); break; case 'b': case 'B': system("cls"); CreateHT(ht,n); CreateHCode(ht,hcd,n); printf("請(qǐng)輸入要進(jìn)行編碼的字符串(以#結(jié)束):n"); editHCode(ht,hcd,n); getchar

18、(); system("cls"); break; case 'c': case 'C': system("cls"); CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf("請(qǐng)輸入編碼(以#結(jié)束):n"); deHCode(ht,hcd,n); getchar(); system("cls"); break; case 'd': case 'D': flag=0; br

19、eak; default: system("cls"); 四、調(diào)試結(jié)果五.實(shí)驗(yàn)總結(jié) 1.做這個(gè)項(xiàng)目前，應(yīng)該明確需求，劃清功能模塊。 A.明確需求，就是明確所做的是什么，有什么要求，有望達(dá)成什么樣的結(jié)果。 B.功能模塊，就是確定實(shí)現(xiàn)的方法，并將其分而治之，由大化小，各個(gè)部分實(shí)現(xiàn)，是程序清晰化。 2.確定實(shí)現(xiàn)算法，就這個(gè)題目來說，是實(shí)現(xiàn)哈夫曼編碼和譯碼，那首先就得創(chuàng)建哈夫曼樹，創(chuàng)建哈夫曼樹是這個(gè)題目的核心。創(chuàng)建哈夫曼樹，在計(jì)算機(jī)里是很抽象的，在創(chuàng)建之前，應(yīng)該手寫一遍哈夫曼樹的創(chuàng)建過程，以及確定一種編號(hào)方式（很重要，后面的編碼譯碼就是對(duì)你創(chuàng)建的哈夫曼樹的編號(hào)的操作。） 在創(chuàng)建的過

20、程中，明確思路和步驟，順便寫出偽代碼，便于后續(xù)書寫。 3.在寫編碼函數(shù)之前，可以先將單個(gè)字符編碼出來，那樣的話，一個(gè)字符串編碼就只是增加了判斷字符是否相等，然后，通過循環(huán)將其輸出。 4.譯碼時(shí)，應(yīng)當(dāng)注意將前面已經(jīng)譯碼過的二進(jìn)制數(shù)刪除（這里其實(shí)是換成字符格式的），以便接下來的字符繼續(xù)譯碼。 5.做課程設(shè)計(jì)時(shí)，應(yīng)該明確一種核心的實(shí)現(xiàn)思路，然后每一個(gè)功能模塊的實(shí)現(xiàn)，都圍繞這個(gè)核心的思路去確定算法，這樣，就便于寫出每一個(gè)模塊的具體實(shí)現(xiàn)，也便于將其全部聯(lián)系起來。程序清單：/ hafuman.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#includ

21、e<iostream>using namespace std;#include <stdio.h>#include <stdlib.h> /要用system函數(shù)要調(diào)用的頭文件#include<conio.h> /用getch()要調(diào)用的頭文件#include <string.h>#define N 50 /義用N表示50葉節(jié)點(diǎn)數(shù)#define M 2*N-1 /用M表示節(jié)點(diǎn)總數(shù) 當(dāng)葉節(jié)點(diǎn)數(shù)位n時(shí)總節(jié)點(diǎn)數(shù)為2n-1#define MAXSIZE 100 struct HTNodechar data; /結(jié)點(diǎn)值int weight; /權(quán)

22、值int parent; /雙親結(jié)點(diǎn)int lchild; /左孩子結(jié)點(diǎn)int rchild; /右孩子結(jié)點(diǎn); struct HCodechar cdN; /存放哈夫曼碼int start; /從start開始讀cd中的哈夫曼碼;void CreateHT(HTNode ht, int n) /調(diào)用輸入的數(shù)組ht,和節(jié)點(diǎn)數(shù)nint i, k, lnode, rnode;int min1, min2;for (i = 0; i<2 * n - 1; i+)hti.parent = hti.lchild = hti.rchild = -1; /所有結(jié)點(diǎn)的相關(guān)域置初值-1for (i = n;

23、 i<2 * n - 1; i+) /構(gòu)造哈夫曼樹min1 = min2 = 32767; /int的范圍是-3276832767lnode = rnode = -1; /lnode和rnode記錄最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置for (k = 0; k <= i - 1; k+)if (htk.parent = -1) /只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找if (htk.weight<min1) /若權(quán)值小于最小的左節(jié)點(diǎn)的權(quán)值min2 = min1; rnode = lnode;min1 = htk.weight; lnode = k;else if (htk.weight<mi

24、n2)min2 = htk.weight; rnode = k;htlnode.parent = i; htrnode.parent = i; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是ihti.weight = htlnode.weight + htrnode.weight; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值為兩個(gè)最小節(jié)點(diǎn)權(quán)值之和hti.lchild = lnode; hti.rchild = rnode; /父節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)void CreateHCode(HTNode ht, HCode hcd, int n)int i, f, c;HCode hc;for (i = 0; i<n; i+) /根據(jù)

25、哈夫曼樹求哈夫曼編碼hc.start = n; c = i;f = hti.parent;while (f != -1) /循序直到樹根結(jié)點(diǎn)結(jié)束循環(huán)if (htf.lchild = c) /處理左孩子結(jié)點(diǎn)hc.cdhc.start- = '0'else /處理右孩子結(jié)點(diǎn)hc.cdhc.start- = '1'c = f; f = htf.parent;hc.start+; /start指向哈夫曼編碼hc.cd中最開始字符hcdi = hc;void DispHCode(HTNode ht, HCode hcd, int n) /輸出哈夫曼編碼的列表int i,

26、k;printf(" 輸出哈夫曼編碼:n");for (i = 0; i<n; i+) /輸出data中的所有數(shù)據(jù)，即A-Zprintf(" %c:t", hti.data);for (k = hcdi.start; k <= n; k+) /輸出所有data中數(shù)據(jù)的編碼printf("%c", hcdi.cdk);printf("n");void editHCode(HTNode ht, HCode hcd, int n) /編碼函數(shù)char stringMAXSIZE;int i, j, k;cin

27、 >> ("%s", string); /把要進(jìn)行編碼的字符串存入string數(shù)組中printf("n輸出編碼結(jié)果:n");for (i = 0; stringi != '#' i+) /#為終止標(biāo)志for (j = 0; j<n; j+)if (stringi = htj.data) /循環(huán)查找與輸入字符相同的編號(hào)，相同的就輸出這個(gè)字符的編碼for (k = hcdj.start; k <= n; k+)printf("%c", hcdj.cdk);break; /輸出完成后跳出當(dāng)前for循環(huán)

28、void deHCode(HTNode ht, HCode hcd, int n) /譯碼函數(shù)char codeMAXSIZE;int i, j, k, m, x;cin>>("%s", code); /把要進(jìn)行譯碼的字符串存入code數(shù)組中while (code0 != '#')for (i = 0; i<n; i+)m = 0; /m為想同編碼個(gè)數(shù)的計(jì)數(shù)器for (k = hcdi.start, j = 0; k <= n; k+, j+) /j為記錄所存儲(chǔ)這個(gè)字符的編碼個(gè)數(shù)if (codej = hcdi.cdk) /當(dāng)有相同編

29、碼時(shí)m值加1m+;if (m = j) /當(dāng)輸入的字符串與所存儲(chǔ)的編碼字符串個(gè)數(shù)相等時(shí)則輸出這個(gè)的data數(shù)據(jù)printf("%c", hti.data);for (x = 0; codex - 1 != '#' x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex = codex + j;void main()int n = 6, i;char orz, flag = 1;char str = 'A', 'B', 'C', 'D', 'E', 'F' ;int f