2022年2022年哈夫曼编译树

《2022年2022年哈夫曼编译树》由会员分享，可在线阅读，更多相关《2022年2022年哈夫曼编译树（12页珍藏版）》请在金锄头文库上搜索。

1、哈夫曼编码译码器实验报告2011 级网络工程1 班姓名：翁轩轩学号： 41109040116 完成日期： 2013.01.03 1需求分析（1） 输入字符和权值；（2） 输出哈夫曼树及哈夫曼编码；（3） 程序可以根据字符使用的频率设计哈夫曼编码；（4） 测试数据：2概要设计本程序的数据类型定义为typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char* HuffmanCode; 所实现的功能函数如下void initHuffmanTree();

2、/选择初始化哈夫曼树的方式int openfileInit();/通过打开的 data.txt文件初始化哈夫曼树该文件是为了测试数据2 包涵 26 个字符int inputInit();/通过手动输入字符初始化哈夫曼树int HuffmanCoding(int *w); / 初始化哈夫曼数，按照哈夫曼规则建立二叉树。此函数块调用了 Select （）函数。void Select(int j,int &s1,int &s2); / 选择 parent为 0，且 weight 最小的两个节点序号为 s1，s2 void encoding();/选择哈夫曼编码方式void openfileEnco(

3、);/通过打开文件encode.txt的方式进行编码void inputEnco();/通过手动输入的方式进行编码void decode();/选择译码方式void openfileDeco();/通过打开文件CodeFile.txt的方式进行译码void inputDeco();/通过手动输入的方式进行译码void dispHT( HuffmanTree nodeRoot, int level ); /以缩进方式输出哈夫曼树直观图主函数字符a v e s f 频度1 2 3 4 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

4、- 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 主函数主要设计的是一个分支语句，让用户挑选所实现的功能。如图所示：3详细设计4调试分析在写程序与调试的过程中，发现自己对于函数的调用与参数的传递的方面还是存在很多问题，从参数的类型等等方面都出现了很多问题。关于这个程序的要求比较复杂，刚开始做的时候没有任何思路，最后分模块一点一点的进行。在输出树的直观图的问题上一开始困扰了我很久，后来想到用一个level记录层数， 以缩进的方式分层显示，解决了这个问题。在调试过程中， 出现了很多次明明建立了文件却发现未存入数据的情况，为此我多次进行调试，

5、发现是打开文件的操作放在了循环体内部导致数据无法写入。整体而言，整个程序主要使用了HuffmanCoding() 的方式进行哈夫曼编码，在encoding （）里面用了字符串的匹配进行译码，在decode（）里进行了重新遍历树的过程，在算法的效率以及如何更为节省空间的存储数据上都要进一步改进。5用户使用说明本程序适应环境为VC6.0 在输入字符及使用频率后可以输出哈夫曼树（以缩进方式输出哈夫曼树直观图）及哈夫曼编码6测试结果initHuffmanTree();初始化哈夫曼树HuffmanCoding() 构造哈夫曼树编码调用 Encoding() 译码调用 Decode（）dispHT() 打

6、 印哈 夫 曼树Select （ ） 供HuffmanCoding()调用名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - 7附录#include #include #include / /* 定义赫夫曼树结点的结

7、构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/ typedef struct int weight; char ch; /增加一个域用于存放该节点的字符 int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char *HuffmanCode; /指向赫夫曼编码的指针/ /* 本程序用到的函数原型*/ void welcome(); /打印操作选择界面void HuffmanCoding(HuffmanTree &,char *,int *,int);/建立赫夫曼树的算法void select(HuffmanTree HT,in

8、t j,int *s1,int *s2); /从目前已建好的赫夫曼树中选择parent 为 0 且 weight 最小的两个结点void Init(); /输入 n 个字符及其对应的权值，根据权值建立哈夫曼树void Coding(); /编码void Decoding(); /译码void Print_code(); /打印译码好的代码文件void Print_tree(); /以凹凸表形式打印哈夫曼树int Read_tree(HuffmanTree &); /从文件中读入赫夫曼树void find(HuffmanTree &HT,char *code,char *text,int i,i

9、nt m);/译码时根据01 字符串寻找相应叶子节点的递归算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - void Convert_tree(unsigned char T100100,int s,int *i,int j);/将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; /全局变量，指向存放赫夫曼树的存储空间int n=0; /全局变量，存放赫夫曼树叶子结点的数目int main() cha

10、r select; while(1) welcome(); scanf(%c,&select); switch(select) case i: case I:Init();break; case c: case C:Coding();break; case d: case D:Decoding();break; case p: case P:Print_code();break; case t: case T:Print_tree();break; case e: case E:exit(1); default :printf(Input error!n); getchar(); return

11、 0; void welcome() /打印操作选择界面 printf(*-*n); printf(| 选择你要的操作 |n); printf(|-|n); printf(| |n); printf(| I-进入哈夫曼树 |n); printf(| C- 编码文件 |n); printf(| D-删除编码 |n); printf(| P-打印编码 |n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - printf(| T-

12、P打印哈夫曼树 |n); printf(| |n); printf(*-*n); / /* 初始化函数，输入n 个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree 中*/ void Init() FILE *fp; int i,n,w52; /w数组存放 n 个字符的权值char character52; /存放 n 个字符printf(n输入字符个数 n:); scanf(%d,&n); /输入字符集大小printf(输入%d个字符及其对应的权值:n,n); for (i=0;in;i+) char b=getchar(); scanf(%c,&characteri);

13、 scanf(%d,&wi); /输入 n 个字符和对应的权值 HuffmanCoding(HT,character,w,n); /建立赫夫曼树if(fp=fopen(hfmtree.txt,w)=NULL) printf(Open file hfmtree.txt error!n); for (i=1;i=2*n-1;i+) if(fwrite(&HTi,sizeof(HTNode),1,fp)!=1) /将建立的赫夫曼树存入文件hfmtree.txt中 printf(File write error!n); printf(n建立赫夫曼树成功，已将其存于文件hfmtree.txt中n); f

14、close(fp); / /建立赫夫曼树的算法/ void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n) int m,i,s1,s2; HuffmanTree p; if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - fo

15、r(p=HT+1,i=1;ich=*character;p-weight=*w;p-parent=0;p-lchild=0;p-rchild=0; for(;ich=0;p-weight=0;p-parent=0;p-lchild=0;p-rchild=0; for(i=n+1;i=m;+i) select(HT,i-1,&s1,&s2); HTs1.parent=i;HTs2.parent=i; HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; / /* 从 HT1 到 HTj 中选择 parent 为 0且 w

16、eight 最小的两个结点，用s1 和 s2 返回其序号 */ void select(HuffmanTree HT,int j,int *s1,int *s2) int i; / 找 weight 最小的结点for (i=1;i=j;i+) if (HTi.parent=0) *s1=i;break; for (;i=j;i+) if (HTi.parent=0)&(HTi.weightHT*s1.weight) *s1=i; HT*s1.parent=1; / 找 weight 次小的结点for (i=1;i=j;i+) if (HTi.parent=0) *s2=i;break; for

17、 (;i=j;i+) if (HTi.parent=0)&(i!=*s1)&(HTi.weightHT*s2.weight) *s2=i; / /* 对文件 tobetrans中的正文进行编码，然后将结果存入文件codefile中*/ void Coding() FILE *fp,*fw; int i,f,c,start; char *cd; HuffmanCode HC; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - if

18、(n=0) n=Read_tree(HT);/从文件 hfmtree.txt中读入赫夫曼树 , 返回叶子结点数 /以下程序段求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中 HC=(HuffmanCode)malloc(n+1)*sizeof(char*); cd=(char *)malloc(n*sizeof(char); cdn-1=0; for(i=1;i=n;+i) start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start=0; else cd-start=1; HC

19、i=(char *)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd); / if(fp=fopen(tobetrans.txt,rb)=NULL) printf(Open file tobetrans.txt error!n); if(fw=fopen(codefile.txt,wb+)=NULL) printf(Open file codefile.txt error!n); char temp; fscanf(fp,%c,&temp); /从文件读入第一个字符while(!feof(fp) for(i=1;i=n;i+

20、) if(HTi.ch=temp) break; /在赫夫曼树中查找字符所在的位置 for(int r=0;HCir!=0;r+) /将字符对应的编码存入文件 fputc(HCir,fw); fscanf(fp,%c,&temp); /从文件读入下一个字符 fclose(fw); fclose(fp); printf(n对文件 hfmtree.txt编码成功 , 结果已存入 codefile.txt中。 nn); / 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12

21、页 - - - - - - - - - /* 将文件 codefile中的代码进行译码，结果存入文件textfile中*/ void Decoding() FILE *fp,*fw; int m,i; char *code,*text,*p; if(n=0) n=Read_tree(HT);/从文件 hfmtree.txt中读入赫夫曼树 , 返回叶子结点数if(fp=fopen(codefile.txt,rb)=NULL) printf(Open file codefile.txt error!n); if(fw=fopen(textfile.txt,wb+)=NULL) printf(Ope

22、n file textfile.txt error!n); code=(char *)malloc(sizeof(char); fscanf(fp,%c,code); /从文件读入一个字符for(i=1;!feof(fp);i+) code=(char *)realloc(code,(i+1)*sizeof(char); /增加空间 fscanf(fp,%c,&codei); /从文件读入下一个字符 codei-1=0; /到此 codefile.txt文件中的字符已全部读入，存放在code 数组中 text=(char *)malloc(100*sizeof(char); p=text; m

23、=2*n-1; if(*code=0) find(HT,code,text,HTm.lchild,m); /从根节点的左子树去找else find(HT,code,text,HTm.rchild,m); /从根节点的右子树去找 for(i=0;pi!=0;i+) /把译码好的字符存入文件textfile.txt中 fputc(pi,fw); fclose(fp); fclose(fw); printf(n对 codefile.txt文件译码成功，结果已存入textfile.txt文件。 nn); / /* 将文件 codefi1e以紧凑格式显示在终端上, 每行 50 个代码。同时将此字符形式的

24、编码文件写入文件codeprint中。 */ void Print_code() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - FILE *fp,*fw; char temp; int i; if(fp=fopen(codefile.txt,rb)=NULL) printf(Open file codefile.txt error!n); if(fw=fopen(codeprint.txt,wb+)=NULL) printf

25、(Open file codeprint.txt error!n); printf(n文件 codefi1e以紧凑格式显示如下:n); fscanf(fp,%c,&temp); /从文件读入一个字符for (i=1;!feof(fp);i+) printf(%c,temp); if(i%50=0) printf(n); fputc(temp,fw); /将该字符存入文件codeprint.txt中 fscanf(fp,%c,&temp); /从文件读入一个字符 printf(nn此字符形式的编码已写入文件codeprint.txt中.nn); fclose(fp); fclose(fw); /

26、 /* 将已在内存中的哈夫曼树以凹凸表形式显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。*/ void Print_tree() unsigned char T100100; int i,j,m=0; FILE *fp; if(n=0) n=Read_tree(HT);/从文件 hfmtree.txt中读入赫夫曼树 , 返回叶子结点数Convert_tree(T,0,&m,2*n-1); /将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中if(fp=fopen(treeprint.txt,wb+)=NULL) printf(Open file treeprint.t

27、xt error!n); printf(n以凹凸表形式打印已建好的赫夫曼树：n); for(i=1;i=2*n-1;i+) for (j=0;Tij!=0;j+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - if(Tij= ) printf( );fputc(Tij,fp); else printf(%d,Tij);fprintf(fp,%dn,Tij); printf(n); fclose(fp); printf(n此

28、字符形式的哈夫曼树已写入文件treeprint.txt中.nn); / /* 从文件 hfmtree.txt中读入赫夫曼树，返回叶子节点数*/ int Read_tree(HuffmanTree &HT) FILE *fp; int i,n; HT=(HuffmanTree)malloc(sizeof(HTNode); if(fp=fopen(hfmtree.txt,r)=NULL) printf(Open file hfmtree.txt error!n); for (i=1;!feof(fp);i+) HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNo

29、de); /增加空间 fread(&HTi,sizeof(HTNode),1,fp); /读入一个节点信息 fclose(fp); n=(i-1)/2; return n; / /* 译码时根据 01 字符串寻找相应叶子节点的递归算法*/ void find(HuffmanTree &HT,char *code,char *text,int i,int m) if(*code!=0) /若译码未结束 code+; if(HTi.lchild=0&HTi.rchild=0) /若找到叶子节点 *text=HTi.ch; /将叶子节点的字符存入text中 text+; 名师资料总结 - - -精品

30、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - if(*code=0) find(HT,code,text,HTm.lchild,m); /继续从根节点的左子树找 else find(HT,code,text,HTm.rchild,m); /继续从根节点的右子树找 else /如果不是叶子节点 if(*code=0) find(HT,code,text,HTi.lchild,m); /从该节点的左子树去找 else find(HT,code,text,

31、HTi.rchild,m); /从该节点的右子树去找 else *text=0; /译码结束 / /* 将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树*/ void Convert_tree(unsigned char T100100,int s,int *i,int j) int k,l; l=+(*i); for(k=0;ks;k+) Tlk= ; Tlk=HTj.weight; if(HTj.lchild) Convert_tree(T,s+1,i,HTj.lchild); if(HTj.rchild) Convert_tree(T,s+1,i,HTj.rchild); Tl+k=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -