哈夫曼树编码以及译码——实验报告.doc

华北水利水电大学 数据结构 实验报告2013 2014 学年 第 一 学期 级 计算机科学与技术专业班级： 学号： 姓名： 实验三：哈夫曼编/译码器一 实验目的掌握哈夫曼树编码原理二实验内容 根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求赫夫曼编码，并能把给定的编码进行译码。 基本要求：（1）初始化：从键盘输入一字符串（或读入一文件），统计出现的字符和每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树。对各个字符进行哈夫曼编码，最后打印输出字符及每个字符对应的哈夫曼编码。 （2）编码：利用已建好的哈夫曼树对“输入串”进行哈夫曼编码，最后打印输入串对应的哈夫曼编码（写入文件）。 （3）计算压缩比（选作） （4）译码：利用已建好的哈夫曼树对给定的一串代码进行译码，并打印输出得到的字符串。（选作）测试数据：对字符串casbcatbsatbat进行编码；对电文“1101000”译码。字符集D= ？,出现频率为w=？ 三 程序源代码#include#include#include/.数据结构的构造.typedef struct HTNodeint weight;int parent;int lchild;int rchild; HTNode(int w,int p,int l,int r)weight=w;parent=p;lchild=l;rchild=r;HTNode,*HuffmanTree;typedef char * HuffmanCode;typedef struct /译码参照表char word;char* code;LNode,*List;/.选取最小和次小的.void Select(HuffmanTree & HT,int num,int *s1,int *s2)int i; for(i=1;i=num;i+)if(HTi.parent=0)*s1=i; break;for(i=1;iHTi.weight)*s1=i; for(i=1;i=num;i+) if(i=*s1) continue; if(HTi.parent=0)*s2=i; break;for(i=1;i=HTi.weight) *s2=i;/.哈夫曼树构造函数.void HuffmanTreeCoding(HuffmanTree &HT,HuffmanCode &HC,int *w, int n)int i,c,m,start;int f,s1,s2;char *cd;HuffmanTree p;if(n=1) return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;i=n;+i,+p,+w) *p=HTNode(*w,0,0,0);for(;i=m;+i,+p) *p=HTNode(0,0,0,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;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;HCi=(char *)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);/.译码函数.int Translate(List ArrayList,char* s1,char *s2)int i,j,k=0;int num=0;int len;for(i=1;i=5;i+)len=strlen(ArrayListi.code);for(j=0;j=len) s=(char*)realloc(s,10*sizeof(char);w=(int*)realloc(w,10*sizeof(int);len+=10;sj=codei; wj=1; j+;HuffmanTreeCoding(HT,HC,w,j); /调用编码函数for(i=1;i=j;i+)ArrayListi.word=si-1;ArrayListi.code=HCi;num=Translate(ArrayList,transcode,transcode_result); /调用译码函数printf(输出编码结果:n);for(i=1;i=j;i+)printf(%c:,ArrayListi.word);puts(ArrayListi.code);printf(译码结果是:n);for(i=0;inum;i+)printf(%c ,transcode_resulti);printf(n);return 0;四 运行结果五 实验总结在这次实验中，利用哈夫曼树进行编码，由于参考书中的哈夫曼编码的原理以及书中的算法，思路很明确，但在实现的过程中依然遇到了不少问题。首先是自己定义的结构体类型初始化的问题。利用原先那种“初始化方法，再编译时总是出现错误，但在语法上没有错误。后来查询了MSDN,了解到这种错误在于自己定义的结构体在初