哈夫曼树的编码与译码.doc

目录一、摘要5二、题目6三、实验目的6四、实验原理6五、需求分析75.1实验要求75.2实验内容7六、概要设计76.1所实现的功能函数76.2主函数86.3 系统结构图9七、详细设计和编码9八、运行结果15九、总结189.1调试分析189.2 心得体会18参考文献19一、摘要二、题目哈夫曼树的编码与译码三、实验目的（1）熟悉对哈夫曼的应用以及构造方法，熟悉对树的构造方式的应用；（2）进一步掌握哈夫曼树的含义；（3）掌握哈夫曼树的结构特征，以及各种存储结构的特点以及使用范围；（4）熟练掌握哈夫曼树的建立和哈夫曼编码方法；（5）提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法；（6）掌握一种计算机语言，可以进行数据算法的设计。四、实验原理 哈夫曼（Huffman）编码属于长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下：（1） 初始化，根据富豪概率的大小按由大到小顺序对符号进行排序；（2） 把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和；（3） 重复第（2）步，直到形成一个符号为止（树），其概率最后等于1；（4） 从编码树的根开始回溯到原始的符号，并将每一下分支赋值1，上分支赋值0；译码的过程是分解电文中字符串，从根出发，按字符“0”或者“1”确定找做孩子或右孩子，直至叶子节点，便求得该子串相应的字符。五、需求分析5.1实验要求（1）从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树的存储结构；（2）利用已经建好的哈夫曼树，对给定的n个字符正文进行编码，并输出结果。（3）利用已建好的哈夫曼树，对给定的一个哈夫曼编码进行译码，判断此编码对应的字符，并输出结果。5.2实验内容（1）定义哈夫曼树结构；（2）初始化哈夫曼树，存储哈夫曼树信息；（3）定义哈夫曼编码的函数；（4）定义哈夫曼译码的函数；（5）写出主函数；（6）测试系统；（7）运行程序。六、概要设计6.1所实现的功能函数void initHuffmanTree();/初始化哈夫曼树int inputInit();/进行哈夫曼树的初始化int HuffmanCoding(int *w); /初始化哈夫曼数，按照哈夫曼规则建立二叉树。此函数块调用了Select()函数。void Select(int j,int &s1,int &s2); /选择parent为0，且weight最小的两个节点 序号为s1，s2void encoding();/哈夫曼编码void inputEnco();/进行哈夫曼编码void decode();/哈夫曼译码void inputDeco();/进行哈夫曼译码6.2主函数int main() int sel=0;coutXin Yunendl;coutInformation Safety of 2endl;coutWelcome to use the coding and decode of Huffman!endl; for(;) coutt*t1.initendl; coutt*t2.codingendl; coutt*t3.decodeendl; coutt*t4.quitendl; coutPlease input your choice(1-4).endlsel; if(sel=4) break; switch(sel) case 1:initHuffmanTree();break; case 2:encoding();break; case 3:decode();break; default:coutSorry!The number you have input is wrong!endl; outstuf.close(); coutThank you to use it!endl; return 0;解析：挑选需要实现的功能（1）当输入“1”时，调用initHuffmanTree()函数，进行哈夫曼树的初始化； （2）当输入“2”时，调用encoding()函数，进行哈夫曼树的编码； （3）当输入“3”时，调用decode()函数，进行哈夫曼树的译码；（4）当输入“4”时，退出程序；6.3 系统结构图inputInit（）；初始化哈夫曼树HuffmanCoding（）；构造哈夫曼树调用Select（）给HuffmanCoding（）编码调用encoding（）译码调用decode（）调用inputEnco（）给encoding()调用inputDeco（）给decode()七、详细设计和编码#include#include#includeusing namespace std;ofstream outstuf;typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;typedef char* HuffmanCode; HuffmanTree HT=NULL;int n=0;HuffmanCode HC=NULL;char *ch=NULL;void initHuffmanTree();int inputInit();int HuffmanCoding(int *w);void Select(int j,int &s1,int &s2);void encoding();void inputEnco();void decode();void inputDeco();void initHuffmanTree() inputInit();int inputInit() coutn; int *w=(int *)malloc(n+1)*sizeof(int); if(!w) coutERROR;return 0; ch=(char *)malloc(n+1)*sizeof(char); if(!ch) coutERROR;return 0; cout Please input the characters.t; for(int i=1;ichi; coutPlease input the numbers.t; for(i=1;iwi; outstuf.open(hfmTree.txt,ios:out); for(i=1;i=n;i+)outstufchi; outstufwi; coutendl; HuffmanCoding(w); coutThe coding of every character is:; for(i=1;i=n;i+) cout chit; coutHCi; ; outstuf.close(); outstuf.open(code.txt,ios:out); for(i=1;i=n;i+)outstufchi; outstufHCi; coutendl;outstuf.close(); return 0;int HuffmanCoding(int *w) if(n=1) return 1; int m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); if(!HT) coutERROR;return 0; for(int i=1; i=n; +i) HTi.weight=wi; HTi.parent=HTi.lchild=HTi.rchild=0; for(;i=m; +i) HTi.weight=HTi.parent=HTi.lchild=HTi.rchild=0; int s1=0; int s2=0; for(i=n+1;i=m; +i) Select(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*); char *cd=(char*) malloc(n*sizeof(char); if(!cd) coutERROR;return 0; cdn-1=0; int start; for(i=1;i=n;+i) start=n-1; for(int c=i,unsigned int 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); return 0;void Select(int j,int &s1,int &s2) for(int h=1;h=j;h+) if(HTh.parent=0) s1=h;break; h+; for(;hHTs2.weight) m=s1;s1=s2;s2=m; h+; for(;hHTh.weight&HTh.parent=0) s1=h; for(m=1;mHTm.weight&m!=s1&HTm.parent=0) s2=m;void encoding() inputEnco(); void inputEnco() coutPlease input the sentence that you want to coding.(Please end of the character of $)endl; char *file=(char *)malloc(200*sizeof(char); for(int i=1;ifilei; if(filei=$) break; if(i=200) file=(char *)realloc(file,(200+80)*sizeof(char); for(;ifilei; if(filei=$) break; int m=i; coutThe result of the coding is:endl; outstuf.open(CodeFile.txt,ios:out); for(i=1;im;i+) for(int j=1;j=n;j+)if(filei=chj) coutHCj;outstufHCj; break; if(j=(n+1) coutendlThe sentence is wrong and it cant coding! endl; break; coutendl; outstuf.close();void decode() inputDeco();void inputDeco() int m=2*n-1; char *password=(char *)malloc(200*sizeof(char); coutPlease input the sentence you want to decode.(Please end of the character of $)endl; for(int i=1;ipasswordi; if(i=200) password=(char *)realloc(password,(200+80)*sizeof(char); for(;ipasswordi; coutThe result of decode is:endl; outstuf.open(TextFile.txt,ios:out); for(i=1;passwordi!=$;) char record20; for(int j=0,q=i;passwordq!=$;j+,q+) if(passwordq=0) recordj=0;m=HTm.lchild; else recordj=1;m=HTm.rchild; if(HTm.rchild=0) recordj+1=0;break; if(HTm.rchild!=0) coutendlThe sentence is wrong and it cant decode!endl; break; for(int p=1;p=n;p+) if(!strcmp(record,HCp) outstufchp; coutchp;break; i=i+strlen(record); m=2*n-1; coutendl; outstuf.close();int main() int sel=0;coutXin Yunendl;coutInformation Safety of 2endl;coutWelcome to use the coding and decode of Huffman!endl; for(;) coutt*t1.initendl; coutt*t2.codingendl; coutt*t3.decodeendl; coutt*t4.quitendl; coutPlease input your choice(1-4).endlsel; if(sel=4) break; switch(sel) case 1:initHuffmanTree();break; case 2:encoding();break; case 3:decode();break; default:coutSorry!The number you have input is wrong!endl; outstuf.close(); coutThank you to use it!endl; return 0;八、运行结果图表 1开始界面图表 2哈夫曼树的初始化图表 3哈夫曼树的编码图表 4哈夫曼树的译码图表 5退出界面图表 6全部九、总结9.1调试分析 在写程序和调试的过程中，在对函数的理解及调用、参数的传递等方面遇到了很多的麻烦和困难；但最终在同学和老师的帮助下，我最终找出了程序中的错误并将其修改正确，通过分析，我学到了很多。 在开始的时候，对这个课题很陌生，没有任何的思路，但后来通过查阅各种资料并且和同组的同学相互讨论后，思绪慢慢清晰起来；通过分模块分步骤对这个程序进行编写后，一个雏形大概就出来了。 整体而言，整个程序主要使用了HuffmanCoding()的方式进行哈夫曼编码，在encoding（）里面用了字符串的匹配进行编码，在decode（）里进行了译码过程；也就是说，首先进行的是哈夫曼树的初始化：先输入字符数n，在输入n 个字符以及n个权值，输出哈夫曼树的初始化结构；其次是哈夫曼树的编码或译码：编码是输入字符串（字母且是在刚才的字符内），输出该字符串的编码结果，译码是输入字符串（数字），输出该字符串的译码结果。但我觉得不足之处是程序较冗长， 在算法的效率以及如何节省空间的存储数