1 算法与数据结构课程设计 哈夫曼编码/译码器设计 学生姓名: 学 号: 专 业:(计算机科学与技术) 年 级:(大二) 指导教师:(汪洋) 2 0 0 9 年 6 月 1 9 日 哈夫曼编码/译码器 2 问题描述: 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本,但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)每端都需要一个完整的编/译码系统。试为这样的信息收发站写一哈夫曼编/译码系统。 基本要求: I:初始化(Initialization)。从终端读入字符集大小 n,以及 n 个字符和 n 个权值,建立哈夫曼树,并将它存于文件 hfmTree 中。 E:编码(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件 hfmTree 中读入),对文件 ToBeTran 中的正文进行编码,然后将结果存入文件 CodeFile 中。 D:译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码,结果存入文件 TextFile 中。 P:打印代码文件(Print)。将文件 CodeFile 以紧凑格式显示在终端上,每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。 T:打印哈夫曼树(Tree printing)。将已在 中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件 TreePrint 中。 大体解题思路: (1)对输入的一段欲编码的字符串进行统计各个字符出现的次数,并 它 们转化 为 权 值 {w1,w2,… … , wN} 构成 n 棵二叉树 的 集 合F={T1,T2,… … ,Tn}把它们保存到结构体数组HT[n]中,其中{Ti 是按它们的 ASCⅡ码值先后排序。其中每棵二叉树 Ti 中只有一个带权为 Wi 的根结点的权值为其左、右子树上根结点的权值之和。 (2)在 HT[1..i]中选取两棵根结点的权值最小且没有被选过的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。 (3)哈夫曼树已经建立后,从叶子到根逆向求每一个字符的哈夫曼编码。 概要设计: 实现的功能:1.查看原文(showpassage()),2.字符统计(showdetail()), 3 3.哈夫曼编码并输出内容(HuffmanCoding(HT,HC,30,w)),4.输出整篇文章的码字(printcode()),5.求最小权值(minweight()),6.最码字进行解码(decode()),7.测试解码(testdecode(...