哈夫曼樹應用

1、一具體任務 題目：哈夫曼樹應用 功能： 1從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹并將它存于文件hfmTree中.將已在內(nèi)存中的哈夫曼樹以直觀的方式（比如樹）顯示在終端上；2. 中讀入），對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中，并輸出結果。同時將此字符形式的編碼文件寫入文件CodePrint中。3利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中，并輸出結果。二軟件環(huán)境 Code：Blocks10.05三算法設計思想1.建立哈夫曼樹函數(shù)void HuffTree(HNode Huff,int n)

2、 /生成哈夫曼樹 FILE *fp; char d; int i,j,w,m1,m2,x1,x2; for(i=0;i2*n-1;i+) /對數(shù)組Huff初始化 Huffi.ch= ; Huffi.weight=0; Huffi.parent=-1; Huffi.lchild=-1; Huffi.rchild=-1; printf(輸入%d個字符及它的權值: n,n);/讀入數(shù)據(jù) getchar(); for(i=0;in;i+) printf(請輸入第%d個字符:,i+1); scanf(%c,&d); getchar(); Huffi.ch=d; printf(請輸入第%d個字符的權值:,

3、i+1); scanf(%d,&w); getchar(); Huffi.weight=w; for(i=0;in-1;i+) /構造哈夫曼樹并生成該樹的n-1個分支結點 m1=m2=32767; x1=x2=0; for(j=0;jn+i;j+) /選取最小和次小兩個權值結點并將其序號送x1和x2 if(Huffj.parent=-1&Huffj.weightm1) m2=m1; x2=x1; m1=Huffj.weight; x1=j; else if(Huffj.parent=-1&Huffj.weightm2) m2=Huffj.weight; x2=j; /將找出的兩棵子樹合并為一棵

4、新的子樹 Huffx1.parent=n+i; Huffx2.parent=n+i; Huffn+i.weight=Huffx1.weight+Huffx2.weight; Huffn+i.lchild=x1; Huffn+i.rchild=x2; 2. 對哈夫曼樹進行編碼void HuffmanCode(HNode Huff,int n) /生成哈夫曼編碼 FILE *fw; HCode HuffCodeMAXSIZE/2,cd; / MAXSIZE/2為葉結點的最大個數(shù) int i,j,c,p; for(i=0;in;i+) /求每個葉結點的哈夫曼編碼 HuffCodei.weight=H

5、uffi.weight; cd.start=MAXBIT-1; c=i; p=Huffc.parent; while(p!=-1) if(Huffp.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; c=p; p=Huffc.parent; for(j=cd.start+1;jMAXBIT;j+) /保存該葉結點字符的哈夫曼編碼 HuffCodei.bitj=cd.bitj; HuffCodei.start=cd.start; /保存該編碼在數(shù)組bit中的起始位置 3. 根據(jù)哈夫曼編碼進行譯碼void decode(HN

6、ode Huff,int n)/依次讀入電文，根據(jù)哈夫曼樹譯碼 FILE *fs; int i,j=0; char bMAXSIZE;i=2*n-2; /從根結點開始往下搜索 printf(【輸入電文，并進行譯碼】n); getchar(); printf(輸入發(fā)送的編碼(以2為結束標志)：n); gets(b); printf(譯碼后的字符為:n); while(bj!=2) if(bj=0) i=Huffi.lchild; /走向左孩子 else i=Huffi.rchild; /走向右孩子 if(Huffi.lchild=-1) /treei是葉結點 printf(%c,Huffi.ch

7、); i=2*n-2; /回到根結點 j+; printf(n);if(Huffi.lchild!=-1&bj!=2) /電文讀完，但尚未到葉子結點 printf(nERRORn); /輸入電文4. 菜單調(diào)用void menu() printf(菜單如下n); printf(1-建立哈夫曼樹n ); printf(2-進行哈夫編碼n); printf(3-進行哈夫譯碼n); printf(0-程序退出n);5. main函數(shù)進行調(diào)用int main() HNode HuffMAXSIZE; int n,sel; printf( 哈夫曼編碼與譯碼n);printf(Input numbers o

8、f leaf :n); /n為葉結點個數(shù) scanf(%d,&n); do menu(); printf(請輸入您的選擇:n); scanf(%d,&sel); switch(sel) case 1: HuffTree(Huff,n);/建立哈夫曼樹 break; case 2: HuffmanCode(Huff,n); /生成哈夫曼編碼 break; case 3: decode(Huff,n);/譯碼變代碼 break; while(sel!=0); return 0;4 源代碼#include#include#define MAXSIZE 1000#define MAXBIT 1000

9、/定義哈夫曼編碼的最大長度typedef struct char ch;/增加一個域用于存放該節(jié)點的字符 int weight,parent,lchild,rchild;HNode; /哈夫曼樹結點類型typedef struct int weight; int bitMAXBIT; int start;HCode; /哈夫曼編碼類型void HuffTree(HNode Huff,int n) /生成哈夫曼樹 FILE *fp; char d; int i,j,w,m1,m2,x1,x2; for(i=0;i2*n-1;i+) /對數(shù)組Huff初始化 Huffi.ch= ; Huffi.we

10、ight=0; Huffi.parent=-1; Huffi.lchild=-1; Huffi.rchild=-1; printf(輸入%d個字符及它的權值: n,n);/讀入數(shù)據(jù) getchar(); for(i=0;in;i+) printf(請輸入第%d個字符:,i+1); scanf(%c,&d); getchar(); Huffi.ch=d; printf(請輸入第%d個字符的權值:,i+1); scanf(%d,&w); getchar(); Huffi.weight=w; for(i=0;in-1;i+) /構造哈夫曼樹并生成該樹的n-1個分支結點 m1=m2=32767; x1

11、=x2=0; for(j=0;jn+i;j+) /選取最小和次小兩個權值結點并將其序號送x1和x2 if(Huffj.parent=-1&Huffj.weightm1) m2=m1; x2=x1; m1=Huffj.weight; x1=j; else if(Huffj.parent=-1&Huffj.weightm2) m2=Huffj.weight; x2=j; /將找出的兩棵子樹合并為一棵新的子樹 Huffx1.parent=n+i; Huffx2.parent=n+i; Huffn+i.weight=Huffx1.weight+Huffx2.weight; Huffn+i.lchild

12、=x1; Huffn+i.rchild=x2; printf(哈夫曼樹的列表:n); printf(n_|n); printf(zifu | Huff| weight | lchild | rchild| parent | n); for(i=0;i2*n-1;i+) /輸出哈夫曼樹即數(shù)組Huff的信息 printf(_|_|_|_|_|_|n); printf(%4c |%4d | %5d | %10d |%10d |%10d |n,Huffi.ch, i, Huffi.weight, Huffi.lchild,Huffi.rchild, Huffi.parent); printf(_|n)

13、; if(fp=fopen(d:hfmtree.txt,w)=NULL)/建立hfmtree文件 printf(cannot open the file of hfmtreen); else fprintf(fp,zifu Huff weight lchild rchild parent n); for(i=0;i2*n-1;i+) fprintf(fp,%3c %3d %5d %10d %10d %10d n,Huffi.ch,i, Huffi.weight, Huffi.lchild,Huffi.rchild, Huffi.parent); fclose(fp); void Huffman

14、Code(HNode Huff,int n) /生成哈夫曼編碼 FILE *fw; HCode HuffCodeMAXSIZE/2,cd; / MAXSIZE/2為葉結點的最大個數(shù) int i,j,c,p; for(i=0;in;i+) /求每個葉結點的哈夫曼編碼 HuffCodei.weight=Huffi.weight; cd.start=MAXBIT-1; c=i; p=Huffc.parent; while(p!=-1) if(Huffp.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; c=p; p=Huffc

15、.parent; for(j=cd.start+1;jMAXBIT;j+) /保存該葉結點字符的哈夫曼編碼 HuffCodei.bitj=cd.bitj; HuffCodei.start=cd.start; /保存該編碼在數(shù)組bit中的起始位置 printf(字母哈夫曼編碼如下:n); printf(-|-|-|-|n); printf(zifu |HuffCode| weight | bit |n); /輸出數(shù)組HuffCode的有關信息 printf(-|-|-|-|n); for(i=0;in;i+) /輸出各葉結點對應的哈夫曼編碼 printf(%4c |%5d |%4d | ,Huf

16、fi.ch,i,HuffCodei.weight); for(j=HuffCodei.start+1;jMAXBIT;j+) printf(%d |,HuffCodei.bitj); printf(n); printf(-|-|-|-|n); if(fw=fopen(d:CodeFile.txt,w)=NULL)/建立codeFile文件 printf(cannot open the file of CodeFilen); else fprintf(fw,zifu HuffCode weight bit n); for(i=0;in;i+) fprintf(fw,%4c%5d%8d ,Huff

17、i.ch,i,HuffCodei.weight); for(j=HuffCodei.start+1;jMAXBIT;j+) fprintf(fw,%d,HuffCodei.bitj); fprintf(fw,n); fclose(fw);void decode(HNode Huff,int n)/依次讀入電文，根據(jù)哈夫曼樹譯碼 FILE *fs; int i,j=0; char bMAXSIZE; i=2*n-2; /從根結點開始往下搜索 printf(【輸入電文，并進行譯碼】n); getchar(); printf(輸入發(fā)送的編碼(以2為結束標志)：n); gets(b); printf(

18、譯碼后的字符為:n); while(bj!=2) if(bj=0) i=Huffi.lchild; /走向左孩子 else i=Huffi.rchild; /走向右孩子 if(Huffi.lchild=-1) /treei是葉結點 printf(%c,Huffi.ch); i=2*n-2; /回到根結點 j+; printf(n);if(Huffi.lchild!=-1&bj!=2)/電文讀完，但尚未到葉子結點 printf(nERRORn); /輸入電文有錯 else if(fs=fopen(d:textFile.txt,w)=NULL)/建立textFile文件 printf(cannot

19、 open the textFile.txt of CodeFilen); else fprintf(fs,譯碼后的字符為); while(bj!=2) if(bj=0) i=Huffi.lchild; /走向左孩子 else i=Huffi.rchild; /走向右孩子 if(Huffi.lchild=-1) /treei是葉結點 fprintf(fs,%c,Huffi.ch); i=2*n-2; /回到根結點 j+; void menu() printf(菜單如下n); printf(1-建立哈夫曼樹n ); printf(2-進行哈夫編碼n); printf(3-進行哈夫譯碼n); pr

20、intf(0-程序退出n);int main() HNode HuffMAXSIZE; int n,sel; printf( 哈夫曼編碼與譯碼n); printf(Input numbers of leaf :n); /n為葉結點個數(shù) scanf(%d,&n); do menu(); printf(請輸入您的選擇:n); scanf(%d,&sel); switch(sel) case 1: HuffTree(Huff,n);/建立哈夫曼樹 break; case 2: HuffmanCode(Huff,n); /生成哈夫曼編碼 break; case 3: decode(Huff,n);/譯碼變代碼 break; while(sel!=0); return 0;五測試內(nèi)容用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”字符A B C D E F G H I J K L M頻度64 13 22 32 103 21 15 47 57 1 5 32 20字符N O P Q R