《数据结构课程设计哈夫曼编译器样本.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计哈夫曼编译器样本.docx（7页珍藏版）》请在三一文库上搜索。
1、资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。中南大学数据结构课程设计报告题目哈夫曼编译器学生姓名指导教师学院信息科学与工程学院资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。 班 科 1302目 要求3 描述3 解决方法3程序模 功能及流程 4 与 8 果9心得体会11源代 12资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。一实验要求(1) 从键盘读入字符集大小 n , 以及 n 个字符和权值 , 建立哈夫曼树。(2) 利用已建好的哈夫曼树对文件正文进行编码 , 将结果存入相关文件中。(3) 利用已建好的哈夫曼树将编码文件中的代码进行译码,结果存
2、入文件中。(4) 输出代码文件 , 以紧凑格式显示。资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。二问题描述利用哈夫曼编码进行通信能够大大提高信道利用率,缩短信息传输时间 , 降低传输成本。 这要求在发送端经过一个编码系统对待传数据预先编码 , 在接收端将传来的数据进行译码。 对于双向传输信息的信道 , 每端都需要一个完整的编译码系统。 为这样的信息收发站编写哈夫曼编译系统。哈夫曼树又称最优二叉树 , 构造的规则即 给定 n 个权值不同的叶子节点 , 构造一棵二叉树 , 使二叉树的带权路径长度达到最小。具体做法即要使权值较大的结点离根节点较近 , 权值较小的结点离根节点较远。三
3、问题解决方法建立哈夫曼树时要进行多次选择 , 每次选择出权值最小和次小的两个节点 , 将两结点权值相加 , 作为新生成父节点的权值。并分别将其作为左、 右孩子。 再将父节点加入需选择的结点序列中 , 继续选择 , 直到将所有节点都选完为止 , 构成一颗哈夫曼树。 每种字符对应一个节点 , 将每种字符的出现次数作为对应节点权值。在编码过程中 , 较科学的方法是统计文章中每种字符出现的频率 , 并以其作为对应节点的权值 , 使出现频率较高的节点离根结点较近 , 从而使出现频率越高的字符所得的编码位数越少 , 这样做得到的编码结果是最简练的 , 也更有利于译码。资料内容仅供您学习参考，如有不当或者侵
4、权，请联系改正或者删除。编码需从叶节点向上回溯,若叶节点为其父结点的左孩子,则编码为 0, 若为右孩子 , 则编码为 1。然后将父节点作为下一轮循环的子节点 , 继续重复上述步骤 , 直至到达根节点为止 , 即得到初始叶节点对应的编码。译码是编码的逆过程 , 因此译码只需读入编码位串 , 从根结点开始 , 若读到 0, 则走向左孩子 , 读到 1, 则走向右孩子。并将对应的子节点作为下一轮循环的叶节点 , 重复上述步骤 , 直至到达最终叶节点 , 该叶节点即为编码对应的节点。四程序模块功能及流程图1.主要程序模块及功能（ 1） 建立哈夫曼树数据结构 :tree为定义在 Huffmantree类
5、上的数组对象。n 为节点个数 , 即字符种类数。m为建好的哈夫曼树的总节点数,在哈夫曼树中 , m=2*n-1 。Smal、 small2分别存放每轮循环中权值最小和次小的节点的权值。p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标。资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。对应代码段 :for (i=0;im;i+)tree i=new Huffmantree();floatsmall1,small2;/建立哈夫曼树for (i=0;in;i+)/初始化叶节点 ,使每个叶结点都为独立的根节点tree i.parent=0;tree i.lchild=-1;tr
6、ee i.rchild=-1;tree i.weight=0;for (i=0;in;i+)/将每种字符及其出现次数赋给叶节点 , 使每个叶节点对应一种字符资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。tree i.ch=chi;tree i.weight=arri;for (i=n;im;i+)/由 n 个叶节点生成n-1 个父节点p1=0;p2=0;small1=10000;small2=100;for (j=0;ji;j+)/选出权值最小与次小的两个节点if ( tree j.parent=0)if ( tree j.weightsmall1)small2=small1;small1=tree j.weight;p2=p1;p1=j;