数据结构课程设计 哈夫曼编译器

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;i

10、len;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。weight=0;parent=0;lchild=-1;rchild

11、=-1;ch=0;(5)codetype类public class Codetype public Character bits; /一维数组，存放每个字符对应的编码位串 public int start; /start为每个字符位串的起始位置 public char ch; public Codetype() start=0; ch=0; 2.流程图 将文件内容读入数组 统计文件中字符的种类和出现次数 建立哈夫曼树 哈夫曼树编码 将编码内容写入数组和文件 对编码文件进行译码五调试与测试 分别输入多篇文章进行测试，文章字符数由少到多。在程序编写过程中，要应用的数组较多，数组的使用使原本难于实现

12、的算法变得简单易行。但因数组产生的问题也较多。编码时因存放文章及其频率的数组定义长度较短，不能给较长的文章编码。故要把相应数组长度改大一些。输出时会因为数组长度不匹配的问题出现空字符，也要做相应的调整。测试文章：1. su.fv,y,u ew gbu;i;fewiu!2. When I was a little girl ,I dreamed to grow up. Because I think a child doesnt has freedom,and cant do anything by myself. But now I have grow up,to my surprise,I

13、feel more tired and have more responsibility.Though I can do something myself, I dont feel happy at all. I believe you also have the same thoughs with me. when every us was a child , we wanted to grow up, but when we became a older man,we dont have such nice life as wish. So whatever we are children

14、 or adults, we should try to make our life better, and make ourselves more happy. we should try our best to study hard, then we can let parents have good life, too! do our best to do ourself ! Believe yourself ! You are the best!六测试结果1. 2.七心得体会 通过本次实验，我复习了数据结构中常见的一种结构树形结构，本次实验对象是一种特殊的树结构，即哈夫曼树。通过构造哈

15、夫曼树，我熟练掌握了树的构建及其要素。而编码和译码是在以了解树形结构的基础上，考验我的算法分析与设计能力。而字符统计及文件连接又涉及到许多文件操作，这使我深入了解了java关于文件的库函数及操作语句。这些提高了我在程序设计上的综合能力。 同时，本次实验也出现了一些问题如在数组、文件等操作上考虑不周，使程序运行结果不尽如人意。但通过多次的调试及测试，我逐步改正了这些问题。这使我认识到调试的重要性，即编写程序不仅要知道怎么实现，更要知道怎么找出错误并改正错误，这是很重要的一项技能。 8 源代码 主类package Huffman;import java.io.File;import java.io

16、.FileReader;import java.io.FileWriter;public class Main public static Huffmantree tree; public static Codetype Code;public static void main(String args) throws Exception float len;int n=1; int sum=new int50000;char ch=new char50000;File file=new File(d:原文件.txt); FileReader fr=new FileReader(file); c

17、har a=new char(int)file.length(); fr.read(a); fr.close(); len=a.length; /len为文件长度，n为字符种类数 for(int i=0;ilen;i+) for(int j=0;jn;j+) if(ai=chj)break; else if(j=n-1)chn-1=ai; n+; break; /初始化ch,存放字符种类 System.out.println(文件中内容如下:); for(int u=0;ulen;u+) System.out.print(au); System.out.println(n); for(int

18、i=0;ilen;i+) for(int j=0;jn;j+) if(ai=chj) sumj+; System.out.println(文件中各字符及其出现次数如下:); for(int i=0;in-1;i+) System.out.println(chi+:+sumi); int i,j,p1,p2,x; n-; int m=n*2-1; tree=new Huffmantreem; for(i=0;im;i+) treei=new Huffmantree(); float small1,small2; /建立哈夫曼树 for(i=0;in;i+) treei.parent=0; tre

19、ei.lchild=-1; treei.rchild=-1; treei.weight=0; for(i=0;in;i+) treei.ch=chi; treei.weight=sumi; for(i=n;im;i+) p1=0;p2=0; small1=10000;small2=100; for(j=0;ji;j+) if(treej.parent=0) if(treej.weightsmall1) small2=small1; small1= treej.weight; p2=p1; p1=j; else if(treej.weightsmall2) small2=treej.weight

20、; p2=j; treep1.parent=i; treep2.parent=i; treei.lchild=p1; treei.rchild=p2; treei.weight=treep1.weight+treep2.weight; int 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; Codei.ch=treei.ch; c=i; p=treei.parent; while(p!=0) C

21、odei.start-; if(treep.lchild=c) Codei.bitsCodei.start=0; else Codei.bitsCodei.start=1; c=p; p=treep.parent; Codei=Codei; System.out.println(每种字符的编码结果如下：); for(i=0;in;i+) System.out.print(Codei.ch+:); for(int r=Codei.start;rn;r+) System.out.print(Codei.bitsr); System.out.println( ); FileWriter fw=new FileWriter(d:编码文件.txt); for(int k=0;klen;k+) for(int l=0;ln;l+) if(ak=Codel.ch) for(int h=Codel.start;hn;h+) String bm=Codel.bitsh.toS