数据结构实践环节实验报告(课程设计)

《数据结构实践环节实验报告(课程设计)》由会员分享，可在线阅读，更多相关《数据结构实践环节实验报告(课程设计)（21页珍藏版）》请在毕设资料网上搜索。

1、 课课 程程 设设 计计 说说 明明 书书 课程名称 _数据结构 _ 设计课题 _哈夫曼编/译码器 _ 专 业 _计算机科学与技术 _ 班 级 _ xxxx _ 学 号 _ xxxxxxx_ 姓 名 _ xxx _ 完成日期 2014 年 6 月 14 日 课课 程程 设设 计计 任任 务务 书书 设计题目：设计题目：_哈夫曼编/译码器_ _ 设计内容与要求：设计内容与要求： 设计内容： 打开一篇英文文章， 统计该文章中每个字符出现的次数， 然后以它们作为权值， 设计一个哈夫曼编/译码系统。 要求： 以每个字符出现的次数为权值，建立哈夫曼树，求出哈夫曼编码，对文件 yuanwen 中的正文进行

2、编码，将结果存到文件 yiwen 中，再对文件 yiwen 中的代码 进行译码，结果存到 textfile 中。 指导教师：xxxx 2014 年 6 月 5 日 课课 程程 设设 计计 评评 语语 成绩：成绩： 指导教师： 年 月 日 1 【问题描述】 打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权 值，设计一个哈夫曼编/译码系统。利用哈夫曼编码进行通信可以大大提高信道 利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统 对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信 道（即可以双向传输信息的信道），每端都需要一个完整的编/译码

3、系统。试为这 样的信息收发站编写一个哈夫曼码的编/译码系统。 【基本要求】 以每个字符出现的次数为权值，建立哈夫曼树，求出哈夫曼编码，对文件 yuanwen中的正文进行编码，将结果存到文件yiwen中，再对文件yiwen中的代码 进行译码，结果存到textfile中。一个完整的系统应具有以下功能： (1) I：初始化（Initialization）。从终端读入字符集大小 n，以及 n 个字 符和 n 个权值，建立哈夫曼树，并将它存于文件 hfmTree 中。 (2) E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件 hfmTree 中读入），对文件 ToBeTran 中

4、的正文进行编码，然后将结果存入文件 CodeFile 中。 (3) D：译码（Decoding） 。利用已建好的哈夫曼树将文件 CodeFile 中的代码 进行译码，结果存入文件 Textfile 中。 【测试数据】 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下英文 的编码和译码：“I like playing football”。 字符 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51

5、80 23 8 18 1 16 1 【算法思想】 哈夫曼编译码器的主要功能是先建立哈夫曼树， 然后利用建好的哈夫曼树生 成哈夫曼编码后进行译码 。 在数据通信中，经常需要将传送的文字转换成由二进制字符 0、1 组成的二进 制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表 0，右分 支代表 1，则从根节点到每个叶子节点所经过的路径分支组成的 0 和 1 的序列便 为该节点对应字符的编码，称之为哈夫曼编码。 最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字 符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电 文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。 2 （1） 其主要流程图如图 1-1 所示。 开始 结点数是否大于 1 将 data 和权值赋给 ht 输出根结点和权值 调用 SELECT 函数 计算根结点函数 父结点为两子结点之和 输出两子结点和已构造的结点 是否为根结点？ 左子是否为空？ 此时编码为 0 Ibj.a) jilu-bj.num+; break; if(j-1=jilu-tag jilu-bjilu-tag.a=CHi; jilu-bjilu-tag.num=1; jilu-tag-; f