数据结构课程设计报告哈夫曼编译器.pdfVIP

数据结构课程设计报告哈夫曼编译器.pdf

  1. 1、本文档共24页,可阅读全部内容。
  2. 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多

.

中南大学

数据结构课程设计报告

题目哈夫曼编译器

学生姓名

指导教师

学院信息科学与工程学院

专业班级计科1302

Word资料

.

目录

实验要求……………3

问题描述……………3

问题解决方法………3

程序模块功能及流程图……………4

调试与测试…………8

测试结果……………9

心得体会……………11

源代码………………12

Word资料

.

一.实验要求

(1)从键盘读入字符集大小n,以及n个字符和权值,建立哈夫曼树。

(2)利用已建好的哈夫曼树对文件正文进行编码,将结果存入相关文件中。

(3)利用已建好的哈夫曼树将编码文件中的代码进行译码,结果存入文件中。

(4)输出代码文件,以紧凑格式显示。

二.问题描述

利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降

低传输成本。这要求在发送端通过一个编码系统对待传数据预先编码,在接收端

将传来的数据进行译码。对于双向传输信息的信道,每端都需要一个完整的编译

码系统。为这样的信息收发站编写哈夫曼编译系统。

哈夫曼树又称最优二叉树,构造的规则即给定n个权值不同的叶子节点,

构造一棵二叉树,使二叉树的带权路径长度达到最小。具体做法即要使权值较大

的结点离根节点较近,权值较小的结点离根节点较远。

三.问题解决方法

建立哈夫曼树时要进行多次选择,每次选择出权值最小和次小的两个节点,

Word资料

.

将两结点权值相加,作为新生成父节点的权值。并分别将其作为左、右孩子。再

将父节点加入需选择的结点序列中,继续选择,直到将所有节点都选完为止,构

成一颗哈夫曼树。每种字符对应一个节点,将每种字符的出现次数作为对应节点

权值。

在编码过程中,较科学的方法是统计文章中每种字符出现的频率,并以其作

为对应节点的权值,使出现频率较高的节点离根结点较近,从而使出现频率越高

的字符所得的编码位数越少,这样做得到的编码结果是最简练的,也更有利于译

码。

编码需从叶节点向上回溯,若叶节点为其父结点的左孩子,则编码为0,若

为右孩子,则编码为1。然后将父节点作为下一轮循环的子节点,继续重复上述

步骤,直至到达根节点为止,即得到初始叶节点对应的编码。

译码是编码的逆过程,所以译码只需读入编码位串,从根结点开始,若读到

0,则走向左孩子,读到1,则走向右孩子。并将对应的子节点作为下一轮循环

的叶节点,重复上述步骤,直至到达最终叶节点,该叶节点即为编码对应的节点。

四.程序模块功能及流程图

1.主要程序模块及功能

(1)建立哈夫曼树

数据结构:

tree[]为定义在Huffmantree类上的数组对象。

n为节点个数,即字符种类数。

m为建好的哈夫曼树的总节点数,在哈夫曼树中,m=2*n-1。

Smal、small2分别存放每轮循环中权值最小和次小的节点的权值。

Word资料

.

p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标。

对应代码段:

for(i=0;im;i++){

tree[i]=newHuffmantree();

}

floatsmall1,small2;//建立哈夫曼树

文档评论(0)

137****6015 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档