赫夫曼樹(shù)的應(yīng)用

1、題目：赫夫曼樹(shù)的應(yīng)用課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)指導(dǎo)教師：專 業(yè)：班級(jí)：學(xué) 號(hào)：姓名：學(xué) 號(hào)：姓名：學(xué) 號(hào)：姓名：學(xué) 號(hào)：姓名：完成時(shí)間：目錄一、前 言2二、程序設(shè)計(jì)目的3三、需求分析3四、概要設(shè)計(jì)31、主要需要用到的主要數(shù)據(jù)結(jié)構(gòu)32、算法流程分析4五、源程序和運(yùn)行結(jié)果51.源程序如下52、運(yùn)行結(jié)果11六、調(diào)試分析141.測(cè)試的結(jié)果142.時(shí)間復(fù)雜度分析143.各模塊在設(shè)計(jì)和調(diào)試時(shí)存在問(wèn)題144.算法的改進(jìn)設(shè)想14七、設(shè)計(jì)心得和總結(jié)15八、參考書(shū)籍15一、前 言赫夫曼編碼(Huffman Coding)是一種編碼方式，赫夫曼編碼是可變字長(zhǎng)編碼(VLC)的一種。赫夫曼壓縮是個(gè)無(wú)損的壓縮算法，一般用

2、來(lái)壓縮文本和程序文件。赫夫曼壓縮屬于可變代碼長(zhǎng)度算法一族。意思是個(gè)體符號(hào)（例如，文本文件中的字符）用一個(gè)特定長(zhǎng)度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些很少出現(xiàn)的符號(hào)，則用較長(zhǎng)的位序列。赫夫曼編碼的應(yīng)用很廣泛，利用赫夫曼樹(shù)求地的二進(jìn)制編碼稱為赫夫曼編碼。赫夫曼樹(shù)中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支約定：指向左子樹(shù)的分支表示“0”碼，指向右子樹(shù)的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為對(duì)應(yīng)的編碼，這就是赫夫曼編碼。我們?cè)趯?duì)一些問(wèn)題進(jìn)行求解時(shí)，會(huì)發(fā)現(xiàn)有些問(wèn)題很難找到規(guī)律，或者根本無(wú)規(guī)律可尋。對(duì)于這樣的問(wèn)題，可以利用計(jì)算機(jī)運(yùn)算速度快的特點(diǎn)，先搜索

3、查找所有可能出現(xiàn)的情況，再根據(jù)題目條件從所有可能的情況中，刪除那些不符合條件的解。由赫夫曼算法的定義可知，初始森林中共有n棵只含有根結(jié)點(diǎn)的二叉樹(shù)。算法的的第二步是：算法的的第二步是：將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹(shù)，合并成一棵新的二叉樹(shù)，每合并一次，森林中就減少一棵樹(shù)，產(chǎn)生一個(gè)新結(jié)點(diǎn)。則要進(jìn)行n-1次合并，所以共產(chǎn)生n-1個(gè)新結(jié)點(diǎn)。由此可知，最終求得的赫夫曼樹(shù)中一共有2n-1個(gè)結(jié)點(diǎn)。其中， n個(gè)結(jié)點(diǎn)是初始森林中的n個(gè)孤立結(jié)點(diǎn)。并且赫夫曼樹(shù)中沒(méi)有度數(shù)為1的分支的結(jié)點(diǎn)。采用赫夫曼編碼方案，即應(yīng)用赫夫曼樹(shù)構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。二、程序設(shè)計(jì)目的1.熟悉掌握C語(yǔ)言的基礎(chǔ)知識(shí)和技能；

4、2.學(xué)習(xí)利用計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)赫夫曼樹(shù)構(gòu)造的算法；3.了解利用赫夫曼樹(shù)對(duì)給定權(quán)值的字符的赫夫曼編碼的算法思想。三、需求分析1、打開(kāi)一個(gè)文本文件，用一個(gè)指針指向它，指針變量為*pf2、對(duì)其進(jìn)行字母頻率統(tǒng)計(jì)，把字母和字母的頻率放到結(jié)構(gòu)體syr s1中3、用Huffman算法建立Huffman樹(shù)以及每個(gè)字母的Huffman碼（Huffman數(shù)以及Huffman碼兩張表，均要求輸出，最好能在文本中輸出）4、把該文本文件的英文文章利用Huffman樹(shù)編碼生成二進(jìn)制文件(該文件要求輸出)5、打開(kāi)該二進(jìn)制文本文件，對(duì)其解碼，仍然利用剛才的Huffman樹(shù)進(jìn)行解碼6、輸入，輸出要求都是讀取文件。四、概要設(shè)計(jì)1、主

5、要需要用到的主要數(shù)據(jù)結(jié)構(gòu)a、赫夫曼樹(shù)的數(shù)據(jù)結(jié)構(gòu)typedef struct char data; int weight; int parent; int lchild; int rchild;HuffmanTreeM; b、 赫夫曼編碼的數(shù)據(jù)結(jié)構(gòu)typedef struct char data; char bitsN;HuffmanCodeN;c、字符串存儲(chǔ)單元的數(shù)據(jù)結(jié)構(gòu)typedef struct str char data;char num;/int num;str;2、算法流程分析 a、建立赫夫曼樹(shù)的數(shù)據(jù)結(jié)構(gòu)、赫夫曼編碼的數(shù)據(jù)結(jié)構(gòu)和字符串存儲(chǔ)單元的數(shù)據(jù)結(jié)構(gòu)， 字符串存儲(chǔ)單元的數(shù)據(jù)結(jié)構(gòu)是用

6、來(lái)存儲(chǔ)字母和對(duì)應(yīng)的權(quán)值。b、調(diào)用int read(str s2)函數(shù)，取讀文本ywq1.txt并統(tǒng)計(jì)這里出現(xiàn)字符的個(gè)數(shù)（字母區(qū)分大小寫(xiě)、空格鍵和各種標(biāo)點(diǎn)符號(hào)），再統(tǒng)計(jì)該字符在文本中出現(xiàn)的頻率（也就是所謂的權(quán)值）存放在結(jié)構(gòu)體str s2中，返回字母?jìng)€(gè)數(shù)k，打印字母的和對(duì)應(yīng)的權(quán)值。c、調(diào)用CrtHuffmanTree(ht,s2,k)函數(shù)來(lái)創(chuàng)建赫夫曼數(shù)，首先初始化節(jié)點(diǎn)并給其賦值0，利用for的循環(huán)語(yǔ)句并調(diào)用SelectMin函數(shù)，查找哈夫曼鏈表中兩個(gè)權(quán)值最小的來(lái)建立赫夫曼樹(shù)，打印赫夫曼樹(shù)各節(jié)點(diǎn)的權(quán)值和它的左右孩子。d、調(diào)用CrtHuffmanCode(ht,hc,k)利用建立好的哈夫曼樹(shù)對(duì)文本文本

7、ywq1.txt進(jìn)行編碼，并把編譯的赫夫曼編碼儲(chǔ)存在文本ywq2.txt中，并且打印出來(lái)文本的赫夫曼編碼。e、通過(guò)調(diào)用DecodHuffmanCode(ht,k)將文本ywq2.txt字符的赫夫曼碼翻譯為字符，這就是所謂的反譯碼，把翻譯的英語(yǔ)文章存儲(chǔ)在文本ywq3.txt并且存儲(chǔ)，并且在對(duì)話執(zhí)行框中打印出來(lái)。五、源程序和運(yùn)行結(jié)果1.源程序如下#include<stdio.h>#include<string.h>#include<stdlib.h>#define N 100#define M 2*N-1typedef struct /定義哈夫曼樹(shù)存儲(chǔ)節(jié)點(diǎn)結(jié)構(gòu)體

8、類型 char data; int weight; int parent; int lchild; int rchild;HuffmanTreeM; typedef struct /定義哈夫曼編碼結(jié)構(gòu)體類型 char data; char bitsN;HuffmanCodeN;typedef struct str /定義字符串存儲(chǔ)單元結(jié)構(gòu)體類型 char data;char num;/int num;str;int read(str s2) FILE *fp; char ch; int i,k; str s1128;for(i=0;i<=128;i+) s1i.num = 0; s1i.

9、data = 0; s2i.num = 0; s2i.data = 0; if(fp=fopen("ywq1.txt","r")=NULL) printf("n庫(kù)文件不存在!"); exit(1); printf("n讀取字符串為:n"); ch=fgetc(fp); while(!feof(fp) /統(tǒng)計(jì)字符頻率 printf("%c",ch); s1ch.num+; s1ch.data = ch; ch=fgetc(fp); fclose(fp); for(i=1,k=1;i<=128

10、;i+) if(s1i.num!=0) s2k.num = s1i.num; s2k.data = s1i.data; k+; printf("nn統(tǒng)計(jì)結(jié)果為(字符 頻率):n"); for(i=1;i<k;i+) printf("<%c %d> ",s2i.data,s2i.num); printf(" (共%d種字符)n",k-1); return k;void SelectMin(HuffmanTree ht, int i,int *p1,int *p2) /查找哈夫曼鏈表中兩個(gè)權(quán)值最小的節(jié)點(diǎn) int j,mi

11、n1,min2; min1 = min2 = -1; for(j = 1;j<=i;j+) if(htj.parent = 0) if(htj.weight<min1|min1=-1) if(min1!=-1) min2 = min1;*p2=*p1; min1 = htj.weight;*p1=j; else if(htj.weight<min2|min2=-1) min2 = htj.weight; *p2=j; void CrtHuffmanTree(HuffmanTree ht,str s,int n) /創(chuàng)建哈夫曼樹(shù) int i,m,p1,p2; for(i=1;i

12、<n;i+) /初始化節(jié)點(diǎn) hti.data = si.data; hti.weight = si.num; hti.parent = 0; hti.lchild = 0; hti.rchild = 0; m=2*n-3; for(i=n;i<=m;i+) hti.data = 0; hti.weight = 0; hti.parent = 0; hti.lchild = 0; hti.rchild = 0; for(i=n;i<=m;i+) SelectMin(ht,i-1,&p1,&p2); /調(diào)用SelectMin函數(shù) hti.weight=htp1.w

13、eight+htp2.weight; htp1.parent=i;htp2.parent=i; hti.lchild=p1;hti.rchild=p2; void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int k) /利用建立好的哈夫曼樹(shù)對(duì)字符串進(jìn)行編碼 int c,p,i; char cdN+1; int start; for(i=1;i<k;i+) hci.data = hti.data; start = k-1; cdstart = '0' c=i; while(p=htc.parent)!=NULL) cd-st

14、art = (htp.lchild=c)?'0':'1' /左分支為0，右分支為1 c=p; strcpy(hci.bits,&cdstart); printf("nn每個(gè)字符對(duì)應(yīng)的編碼為:n"); for(i=1;i<k;i+) printf("<%d %c %s> n",i,hci.data,hci.bits);void WriteToFile(HuffmanCode hc,int n) /將編碼結(jié)果存儲(chǔ)在文件文件ywq2.txt中 FILE *fp1,*fp2; char ch; int i

15、; if(fp1=fopen("ywq1.txt","r")=NULL) printf("n文件不存在!"); exit(1); if(fp2=fopen("ywq2.txt","w")=NULL) printf("n文件不存在!"); exit(1); ch = fgetc(fp1);printf("n編碼結(jié)果為："); while(ch != EOF) for(i=1;i<n;i+) if(ch = hci.data) fputs(hci.bit

16、s,fp2); printf("%s",hci.bits); ch = fgetc(fp1); fclose(fp1); fclose(fp2);printf("n");void DecodHuffmanCode(HuffmanTree ht,int n) /碼結(jié)果進(jìn)行譯碼，并將結(jié)果存儲(chǔ)在文件ywq3中 FILE *fp1,*fp2; char ch; int p,k; if(fp1=fopen("ywq2.txt","r")=NULL) printf("n文件不存在!"); exit(1);

17、if(fp2=fopen("ywq3.txt","w")=NULL) printf("n文件未能創(chuàng)建!"); exit(1); p=k=2*n-3; ch=fgetc(fp1); printf("譯碼為: ");while(ch!=EOF) if(ch='0')p=htp.lchild; else if(ch='1') p=htp.rchild; if(htp.data!=0) printf("%c",htp.data); fputc(htp.data,fp2);

18、 p=k; ch = fgetc(fp1); printf("n");fclose(fp1); fclose(fp2);void compare(int k)FILE *fp1,*fp2; char s1N,s2N;int i=1,j=1;printf("nn編譯前后結(jié)果的比較:");if(fp1=fopen("ywq1.txt","rt")=NULL) printf("n打開(kāi)文件失??！n"); exit(1);printf("nn原文件ywq1中的字符為: "); for(

19、i=1;(s1i=fgetc(fp1)!=EOF;i+)printf("%c",s1i);fclose(fp1); if(fp2=fopen("ywq3.txt","rt")=NULL) printf("n打開(kāi)文件失?。"); exit(1); printf("n文 件ywq3中的字符為: "); for(i=1;(s2i=fgetc(fp2)!=EOF;i+)printf("%c",s2i);fclose(fp2); while(j<k)if(s1j=s2j) j+

20、;else printf("n編碼失敗！n"); break; if(j=k) printf("n前后數(shù)據(jù)一致，編碼成功！n");void main() int i,k;int j=1;HuffmanTree ht; HuffmanCode hc; str s2128; printf("n-哈夫曼編碼譯碼器-");k=read(s2);getchar();CrtHuffmanTree(ht,s2,k); CrtHuffmanCode(ht,hc,k); WriteToFile(hc,k);getchar();printf("nn"); printf("建立的哈夫曼樹(shù)為:"); printf(&quo