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

1、中南大学数据结构课程设计报告题 目哈夫曼编译器 学生 指导教师 学 院信息科学与工程学院专业班级计科1302目录实验要求 3问题描述 3问题解决方法 3程序模块功能及流程图 4调试与测试 8测试结果 9心得体会 11源代码 12 一实验要求(1) 从键盘读入字符集大小n ,以及n个字符和权值，建立哈夫曼树。(2) 利用已建好的哈夫曼树对文件正文进行编码，将结果存入相关文件中。(3) 利用已建好的哈夫曼树将编码文件中的代码进行译码，结果存入文件中。(4) 输出代码文件，以紧凑格式显示。二问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编

2、码系统对待传数据预先编码，在接收端 将传来的数据进行译码。对于双向传输信息的信道，每端都需要一个完整的编译 码系统。为这样的信息收发站编写哈夫曼编译系统。哈夫曼树又称最优二叉树，构造的规则即给定n个权值不同的叶子节点，构 造一棵二叉树，使二叉树的带权路径长度达到最小。具体做法即要使权值较大的 结点离根节点较近，权值较小的结点离根节点较远。三问题解决方法建立哈夫曼树时要进行多次选择，每次选择出权值最小和次小的两个节点，将两结点权值相加，作为新生成父节点的权值。并分别将其作为左、右孩子。再 将父节点加入需选择的结点序列中， 继续选择，直到将所有节点都选完为止，构 成一颗哈夫曼树。每种字符对应一个节

3、点，将每种字符的出现次数作为对应节点 权值。在编码过程中，较科学的方法是统计文章中每种字符出现的频率， 并以其作 为对应节点的权值，使出现频率较高的节点离根结点较近， 从而使出现频率越高 的字符所得的编码位数越少，这样做得到的编码结果是最简练的， 也更有利于译 码。编码需从叶节点向上回溯，若叶节点为其父结点的左孩子，贝U编码为0,若为右孩子，则编码为1。然后将父节点作为下一轮循环的子节点，继续重复上述 步骤，直至到达根节点为止，即得到初始叶节点对应的编码。译码是编码的逆过程，所以译码只需读入编码位串，从根结点开始，若读到 0，则走向左孩子，读到1，则走向右孩子。并将对应的子节点作为下一轮循环的

4、叶节点，重复上述步骤，直至到达最终叶节点，该叶节点即为编码对应的节点 四程序模块功能及流程图1.主要程序模块及功能(1)建立哈夫曼树数据结构：tree 为定义在Huffmantree类上的数组对象。n为节点个数，即字符种类数。m为建好的哈夫曼树的总节点数，在哈夫曼树中，m=2*n-1。Smal、small2分别存放每轮循环中权值最小和次小的节点的权值。p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标。 对应代码段：for (i=0;i<m;i+)t reei= new Huffmantree();float small1,small2; /建立哈夫曼树for (i=0;i&l

5、t;n;i+)/初始化叶节点，使每个叶结点都为独立的根节点tree i.parent=0;tree i.lchild=-1;tree i.rchild=-1;tree i.weight=0;for (i=0;i<n;i+)/将每种字符及其岀现次数赋给叶节点，使每个叶节点对应一种字符tree i.ch=chi;tree i.weight=arri;for (i=n;i<m;i+) /由n个叶节点生成 n-1个父节点p1=0;p2=0;small1=10000;small2=100;for (j=0;j<i;j+)/选岀权值最小与次小的两个节点if (tree j.parent=

6、0)if (tree j.weight<small1)small2=small1;small1=tree j.weight;p2=p1;Pl=j；elseif (tree j.weight<small2)small2= tree j.weight;p2=j； treep1.pare nt=i; /建立子节点与父节点间的对应关系，并将父节点权值赋为两子节点权值之和tree p2.parent=i;tree i.lchild=p1;tree i.rchild=p2;tree i.weight= tree p1.weight+ tree p2.weight;(2)编码模块数据结构：Cod

7、e为定义在codetype类上的数组对象。c为缓冲变量，其值为当前节点的下标值。p为父节点的下标值。Start为每个字符编码位串中第一个字符的起始位置。对应代码段：int c,p;/编码部分，c为当前节点编号，p为其父节点编号Code= new Codetype n;for (i=0;i<n;i+)COdei= new Codetype(); Cbdei.bits=new Character n;for (i=0;i<n;i+) Cod&i.start=n;/start为编码位串的起始位置Codei.ch= tree i.ch;c=i;p= tree i.parent;wh

8、ile (p!=0)Codgi.start-;if (tree p.lchild=c) / 向上回溯编码 Codei.bitsCodei.start='0'elseCodei.bitsCodei.start='1'c=p;p= tree p.parent; / 将父节点作为下一轮循环的子节点 Codei= Codei;3)译码模块数据结构： p 为父节点编号。 t 为待译码文件的字符数。 b 为存放待译码文件容的数组。 ym 存放译码结果。对应代码段：for (int q=0;q<t;q+)if (bq='0')p= tree p.lchi

9、ld;elsep= tree p.rchild;if (tree p.lchild=-1) String ym= tree p.ch.toString(); fw1.write(ym);p=m-1;4)字符统计模块 数据结构：len 为文章中的字符数。ai 为存放文章容的数组。Chj 存放不同种类的字符 , 开始里面所有字符都为 0 值。arr 存放每种字符在文章中出现的次数。 对应代码段：for ( int i=0;i<len;i+) / 选出文章中每一种字符串f or ( int j=0;j<n;j+)if (ai=chj) break ;elseif (j=n-1)chn-1

10、=ai; / 若 ch 中找不到 ai 中存放的字符，则 将该种字符放到 ch 中 若找到，则说明该种字符已被存入 ch.n+;break ;/初始化ch,存放字符种类for (int i=0;i<len;i+)for (int j=O;j<n;j+) if (ai=chj)arrj+;/统计文章中每种字符的岀现次数。(5) Huffman 类public class Huffma ntree /weight为节点的权值public int weight;public int pare nt,lchild,rchild; /分别为当前节点的父节点，左、右子节点编号为节点名，即对应的

11、字符。初始化，每个节点构成一个单节点树，权值为0一维数组，存放每个字符对应的编码位串为每个字符位串的起始位置public Character ch; /ch public Huffma ntree() / weight=0; pare nt=0; lchild=-1; rchild=-1;ch='0'(5)codetype 类public class Codetype public Character bits; /public int start; /startpublic 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 dreamedto grow up. Because

13、 I thi nk a childdoes n't hasfreedom,a nd can't do anything by myself.But now I have grow up,to my surprise feel more tired and have more resp on sibility.Though I can do someth ing myself, I don't feel happy at all.I believe you also have the same thoughs with me. whe n every us was a c

14、hild , we wan ted to grow up, but whe n we became a older man,we don't have such nice life as wish.So whatever we are children or adults, we should try to make our life better, and make ourselves more happy. we should try our best to study hard, the n we can let pare nts have good life, too!do o

15、ur best to do ourself ! Believe yourself ! You are the best!六测试结果1.wtEnnintd ix/l迫in |Java A! ： i首种字符的编码结果如下:3!u:10D；aQoiX；0111v：noio<:ioioy:0011J1011e： 1100W；11Q1g：niODb：moi；：1110iillll! :0110文件中內容如下：Sil,±v u ew gtou; i;±ewiu !文件中各字符及其出现友数如下:s : 1u；: 4:1X ；3v:l：2:2e:22toil；：2i:2! !13译码

16、文件bl -记事本丈禅牺(E)播式(0)章看岡 su. fVj y? u ew gbu; 1; f ewiu !2.文件中内容如下：IflieE I wcu 0 1 itt le girl f I direeatied to g'r ow up . Sccemse I think cl child do ear But now I have groisr up,to my surprise, I feel more tired and have more respors I believe you also have the same thoughs ulxh me. ¥he

17、n every ws was q child * 吕口 whsteveE" Tje 牙苦。oh i I dlrsTl 口附 曰日口丄七 且* mb n卉口 14I日 tpy 匸口 wisfclrp- quf I if e b'Ftt er, 肓 Let1 s do our best to do ouraell ! Believe yourself ! You are the bsst!文件中各字符反苴出现次数如下:142W: 1h：31en:24I:Sm 19&:39s:1:27评 bEjr匚h 左 konsoie .'=：tet*miriaterl IVla

18、in (1) J2721犯931122515餐£：10731051014:sV" 1 I IT i L3 : 1.! : 4L : 1豊希竽育的编碍箱果加下:口6W : iCiLiOOl 1 1Oii s xioxiQ s DIO血：1O111X e llXlOClw : J_XX±1.O£L ： 口丄 L 口9 ! TX 3_D3_1 8 L1OOL1 i xmigot ： m liCff :xxxxoxoe : Xd±00* s XOLXO±wL： XLCIUOms九盅口1O1n ? icvaiUL： 1OL 口 Lp 5 XI

19、LIL JL1 3 LI11OCOB i 丄>IXOCOlC： £ XCVQOQQ>Ci 101100X0ltl : iam1 = 1 meal1111 3口m 瓷 OzL J.O s = moi 1 z 3L 1DD11 5 10 I OC匚=口 Hla sliiicicu I 5L11OO .± 3l口厘 1C3L els 1 1DOC TOi 1 1O1C1 Q S 1OO1 us dLOipi p = a li id.11 » * 3l 11 ICDClEl ； ICllOOC 1 Q £ 1OOOOO K；XO11CO1C1 : &

20、#177;:l±l i± O 1 ± = HCl 口 DCI3l311O1COID » 3. 111O1 121OOO1IO=loooi j.aV31OOO1OTf 1OZ1CO1 111S110X100000! « XUllXQCL 二 Ji QI ZLClCl口1V : 3L口 H 丄口口3_ 九口3ft文件 Jxt -记黑t X文彳机D囁憎式(0)蛮看阴祸助When I was 以 little girl ,1 ctreaired to grrw up” Because I think a child doesn't But no

21、常 I liave row up, tu my suipiise, I fttil ncipb! tirad aud have mare TespmiBAbL I believe you also havo tho sarrc thoughs th me. hen every uu was a child , we So whatever w ar? children or adults, iv= shculd try toour Life better, andLetJ s do our best to da ourself ! Believe vrurself ! You are the

22、best!七心得体会通过本次实验，我复习了数据结构中常见的一种结构树形结构，本次实我熟练掌握了树考验我的算法分验对象是一种特殊的树结构，即哈夫曼树。通过构造哈夫曼树, 的构建及其要素。而编码和译码是在以了解树形结构的基础上，这使我深入了解析与设计能力。而字符统计及文件连接又涉及到许多文件操作，了 java关于文件的库函数及操作语句。这些提高了我在程序设计上的综合能力。同时，本次实验也出现了一些问题如在数组、文件等操作上考虑不周，使程序运行结果不尽如人意。但通过多次的调试及测试，我逐步改正了这些问题。这 使我认识到调试的重要性，即编写程序不仅要知道怎么实现，更要知道怎么找出 错误并改正错误，这是

23、很重要的一项技能。八源代码主类package Huffman;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;原文件 .txt");FileReader fr=new FileReader(file);char a=new char(int)file.l

24、ength();fr.read(a);fr.close();len=a.length; /len为文件长度， n 为字符种类数for(int i=0;i<len;i+)for(int j=0;j<n;j+)if(ai=chj)break;elseif(j=n-1)chn-1=ai;n+;break;/ 初始化 ch, 存放字符种类文件中容如下 :");for(int u=0;u<len;u+)for(int i=0;i<len;i+)for(int j=0;j<n;j+)if(ai=chj)sumj+;文件中各字符及其出现次数如下 :"); f

25、or(int i=0;i<n-1;i+)int i,j,p1,p2,x;n-;int m=n*2-1;tree=new Huffmantreem;for(i=0;i<m;i+)treei=new Huffmantree();float small1,small2; / 建立哈夫曼树for(i=0;i<n;i+)treei.parent=0;treei.lchild=-1;treei.rchild=-1;treei.weight=0;for(i=0;i<n;i+)treei.ch=chi;treei.weight=sumi;for(i=n;i<m;i+)p1=0;p

26、2=0;small1=10000;small2=100; for(j=0;j<i;j+) if(treej.parent=0) if(treej.weight<small1)small2=small1;small1= treej.weight;p2=p1;p1=j;elseif(treej.weight<small2)small2=treej.weight;p2=j;treep1.parent=i;treep2.parent=i;treei.lchild=p1;treei.rchild=p2;treei.weight=treep1.weight+treep2.weight;编

27、码部分int c,p; /Code=new Codetypen;for(i=0;i<n;i+)Codei=new Codetype();Codei.bits=new Charactern;for(i=0;i<n;i+)Codei.start=n;Codei.ch=treei.ch;c=i;p=treei.parent;while(p!=0)Codei.start-;if(treep.lchild=c)Codei.bitsCodei.start='0'elseCodei.bitsCodei.start='1'c=p;p=treep.parent;Codei=Codei;每种字符的编码结果