《数据结构课程设计哈夫曼编译器》由会员分享，可在线阅读，更多相关《数据结构课程设计哈夫曼编译器（17页珍藏版）》请在金锄头文库上搜索。
1、 中南大学 数据结构课程设计报告 题 目 哈夫曼编译器 学生姓名 指导教师 学 院 信息科学与工程学院 专业班级 计科1302 目录 实验要求3 问题描述3 问题解决方法3程序模块功能及流程图4调试与测试8测试结果9心得体会11 源代码12一实验要求(1)从键盘读入字符集大小n , 以及n个字符和权值，建立哈夫曼树。(2)利用已建好的哈夫曼树对文件正文进行编码，将结果存入相关文件中。(3)利用已建好的哈夫曼树将编码文件中的代码进行译码，结果存入文件中。(4)输出代码文件，以紧凑格式显示。二问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一
2、个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。对于双向传输信息的信道，每端都需要一个完整的编译码系统。为这样的信息收发站编写哈夫曼编译系统。哈夫曼树又称最优二叉树，构造的规则即给定n个权值不同的叶子节点，构造一棵二叉树，使二叉树的带权路径长度达到最小。具体做法即要使权值较大的结点离根节点较近，权值较小的结点离根节点较远。三问题解决方法建立哈夫曼树时要进行多次选择，每次选择出权值最小和次小的两个节点,将两结点权值相加，作为新生成父节点的权值。并分别将其作为左、右孩子。再将父节点加入需选择的结点序列中，继续选择，直到将所有节点都选完为止，构成一颗哈夫曼树。每种字符对应一个节点，将每种
3、字符的出现次数作为对应节点权值。在编码过程中，较科学的方法是统计文章中每种字符出现的频率，并以其作为对应节点的权值，使出现频率较高的节点离根结点较近，从而使出现频率越高的字符所得的编码位数越少，这样做得到的编码结果是最简练的，也更有利于译码。编码需从叶节点向上回溯，若叶节点为其父结点的左孩子，则编码为0，若为右孩子，则编码为1。然后将父节点作为下一轮循环的子节点，继续重复上述步骤，直至到达根节点为止，即得到初始叶节点对应的编码。译码是编码的逆过程，所以译码只需读入编码位串，从根结点开始，若读到0，则走向左孩子，读到1，则走向右孩子。并将对应的子节点作为下一轮循环的叶节点，重复上述步骤，直至到达
4、最终叶节点，该叶节点即为编码对应的节点。四程序模块功能及流程图1. 主要程序模块及功能 （1） 建立哈夫曼树 数据结构： tree为定义在Huffmantree类上的数组对象。 n为节点个数，即字符种类数。 m为建好的哈夫曼树的总节点数，在哈夫曼树中，m=2*n-1。 Smal、small2分别存放每轮循环中权值最小和次小的节点的权值。 p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标。对应代码段： for(i=0;im;i+) treei=new Huffmantree(); float small1,small2; /建立哈夫曼树 for(i=0;in;i+) /初始化叶节点，
5、使每个叶结点都为独立的根节点 treei.parent=0; treei.lchild=-1; treei.rchild=-1; treei.weight=0; for(i=0;in;i+) /将每种字符及其出现次数赋给叶节点，使每个 叶节点对应一种字符 treei.ch=chi; treei.weight=arri; for(i=n;im;i+) /由n个叶节点生成n-1个父节点 p1=0;p2=0; small1=10000;small2=100; for(j=0;ji;j+) /选出权值最小与次小的两个节点 if(treej.parent=0) if(treej.weightsmall1
6、) small2=small1; small1= treej.weight; p2=p1; p1=j; else if(treej.weightsmall2) small2=treej.weight; p2=j; treep1.parent=i; /建立子节点与父节点间的对应关系，并将父节点权值赋为两子节点权值之和 treep2.parent=i; treei.lchild=p1; treei.rchild=p2; treei.weight=treep1.weight+treep2.weight; (2) 编码模块 数据结构： Code为定义在codetype类上的数组对象。 c为缓冲变量，其
7、值为当前节点的下标值。 p为父节点的下标值。 Start为每个字符编码位串中第一个字符的起始位置。对应代码段： int c,p; /编码部分，c为当前节点编号，p为其父节点编号 Code=new Codetypen; for(i=0;in;i+) Codei=new Codetype(); Codei.bits=new Charactern; for(i=0;in;i+) Codei.start=n; /start为编码位串的起始位置 Codei.ch=treei.ch; c=i; p=treei.parent; while(p!=0) Codei.start-; if(treep.lchil
8、d=c) /向上回溯编码 Codei.bitsCodei.start=0; else Codei.bitsCodei.start=1; c=p; p=treep.parent; /将父节点作为下一轮循环的子节点 Codei=Codei; （3） 译码模块 数据结构： p为父节点编号。 t为待译码文件的字符数。 b为存放待译码文件内容的数组。 ym存放译码结果。 对应代码段： for(int q=0;qt;q+) if(bq=0) p=treep.lchild; else p=treep.rchild; if(treep.lchild=-1) String ym=treep.ch.toStrin
9、g(); fw1.write(ym); p=m-1;（4） 字符统计模块 数据结构：len为文章中的字符数。ai为存放文章内容的数组。Chj存放不同种类的字符,开始里面所有字符都为0值。arr存放每种字符在文章中出现的次数。对应代码段： for(int i=0;ilen;i+) /选出文章中每一种字符串 for(int j=0;jn;j+) if(ai=chj)break; else if(j=n-1)chn-1=ai; /若ch中找不到ai中存放的字符，则将该种字符放到ch中。 若找到，则说明该种字符已被存入ch. n+; break; /初始化ch,存放字符种类 for(int i=0;ilen;i+) for(int j=0;jn;j+) if(ai=chj) arrj+; /统计文章中每种字符的出现次数。 （5） Huffman类 public class Huffmantree public int weight; /weight为节点的权值public int parent,lchild,rchild; /分别为当前节点的父节点，左、右子节点编号public Character ch; /ch为节点名，即对应的字符。public Huffmantree() /初始化，每个节点构成一个单节点树，权值为0。
