哈夫曼树应用

1、一具体任务 题目：哈夫曼树应用 功能： 1从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；2. 中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果。同时将此字符形式的编码文件写入文件CodePrint中。3利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。二软件环境 Code：Blocks10.05三算法设计思想1.建立哈夫曼树函数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+) /对数组Huff初始化 Huffi.ch= ; Huffi.weight=0; Huffi.parent=-1; Huffi.lchild=-1; Huffi.rchild=-1; printf(输入%d个字符及它的权值: n,n);/读入数据 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为叶结点的最大个数 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; /保存该编码在数组bit中的起始位置 3. 根据哈夫曼编码进行译码void decode(HN

6、ode Huff,int n)/依次读入电文，根据哈夫曼树译码 FILE *fs; int i,j=0; char bMAXSIZE;i=2*n-2; /从根结点开始往下搜索 printf(【输入电文，并进行译码】n); getchar(); printf(输入发送的编码(以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. 菜单调用void menu() printf(菜单如下n); printf(1-建立哈夫曼树n ); printf(2-进行哈夫编码n); printf(3-进行哈夫译码n); printf(0-程序退出n);5. main函数进行调用int main() HNode HuffMAXSIZE; int n,sel; printf( 哈夫曼编码与译码n);printf(Input numbers o

8、f leaf :n); /n为叶结点个数 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;/增加一个域用于存放该节点的字符 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+) /对数组Huff初始化 Huffi.ch= ; Huffi.we

10、ight=0; Huffi.parent=-1; Huffi.lchild=-1; Huffi.rchild=-1; printf(输入%d个字符及它的权值: n,n);/读入数据 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+) /输出哈夫曼树即数组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为叶结点的最大个数 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; /保存该编码在数组bit中的起始位置 printf(字母哈夫曼编码如下:n); printf(-|-|-|-|n); printf(zifu |HuffCode| weight | bit |n); /输出数组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)/依次读入电文，根据哈夫曼树译码 FILE *fs; int i,j=0; char bMAXSIZE; i=2*n-2; /从根结点开始往下搜索 printf(【输入电文，并进行译码】n); getchar(); printf(输入发送的编码(以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为叶结点个数 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;五测试内容用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“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