哈夫曼编码译码系统课程设计实验报告（含源代码C++ C语言）

东北电力大学计算机科学与技术专业 综合设计报告

目 录

摘 要 ………………………………………………………………………..……………… II Abstract …………………………………………………………………………..………... II 第一章 课题描述………………………..………………………………………………….. 1 1.1 问题描述………………………………………………………………………………...1 1.2 需求分析…………………………………………………..…………………………… 1 1.3 程序设计目标…………………………………………………………………………… 第二章 设计简介及设计方案论述 ………………………………………………………… 2 2.1 设计简介.………………………………………………..………………………..….…2 2.2 设计方案论述……………………………………………..…………………….………2 2.3 概要设计…………………………………………………..………………………….…2 第三章 详细设计…………………………………………………………..……….….…….. 4 3.1 哈夫曼树…………………………………………………..………………………….…4 3.2 哈夫曼算法………………………………………………..……………………….….…4

3.2.1 基本思想………………………………………………..……………………..…..….…4 3.2.2 存储结构………………………………………………..………………………….....…4

3.3 哈夫曼编码………………………………………………..………………………….…5 3.4 文件I/O流………………………………………………..………………………….…6

3.4.1 文件流…………………………………………………..………………………………6 3.4.2 文件的打开与关闭………………………………………..…………………….……….7 3.4.3 文件的读写…………………………….………………..………………………..…..…7

3..5 C语言文件处理方式…………………………………………………………………… 第四章 设计结果及分析…………………………………………………..……………..….. 8 4.1 设计系统功能………………………………….……………………………….....….…8 4.2 进行系统测试……………………………………………..………………………….…8 总 结 …….……………………………………………………..…………………………...13 致 谢 …….……………………………………………………..……………………..…….14 参考文献 …….………………..………………………………..……………………..…….15 附录 主要程序代码 ………...………………………………..………………………..….16

- I -

东北电力大学计算机科学与技术专业 综合设计报告

摘 要

在这个信息高速发展的时代，每时每刻都在进行着大量信息的传递，到处都离不开信息，它贯穿在人们日常的生活生产之中，对人们的影响日趋扩大,而利用哈夫曼编码进行通信则可以大大提高信道利用率，缩短信息传输时间，降低传输成本。在生产中则可以更大可能的降低成本从而获得更大的利润，这也是信息时代发展的趋势所在。本课程设计的目的是使学生学会分析待加工处理数据的特性，以便选择适当的逻辑结构、存储结构以及进行相应的算法设计。学生在学习数据结构和算法设计的同时，培养学生的抽象思维能力、逻辑推理能力和创造性的思维方法，增强分析问题和解决问题的能力。此次设计的哈夫曼编码译码系统，实现对给定报文的编码和译码，并且任意输入报文可以实现频数的统计,建立哈夫曼树以及编码译码的功能。这是一个拥有完备功能的系统程序，对将所学到的知识运用到实践中,具有很好的学习和研究价值.

关键词：信息；通讯；编码；译码；程序

- II -

东北电力大学计算机科学与技术专业 综合设计报告

Abstract

This is a date that information speeding highly development and transmit information every time, everywhere cannot leave the information, it passes through during the people daily life production, the influence expands day by day to the people, but codes using Huffman carries on the correspondence to be possible to raise the channel use factor greatly, reduces the intelligence transmission time, reduces the transmission cost. May greatly possible reduce the cost in the production, thus obtains a bigger profit, this is also the information age development tendency is. This curriculum project's goal is makes the student academic society to analyze treats the processing data the characteristic, with the aim of choosing the suitable logical organization, the memory structure as well as carries on the corresponding algorithm design. The student during the study construction of data and algorithm design’s raises student's abstract thinking ability, logic reasoning ability and the creative thought method, the enhancement analysis question and solves the question ability. This design's Huffman codes the code recognition system, realizes to assigns the text the code and the decoding, and the arbitrary input text may realize the frequency statistics, establishes the Huffman tree as well as the code decoding function. This is one has the complete function system program, to the knowledge which will learn utilizes in the practice, has the very good study and the research value.

Keywords：Information; Communication; Coding; Decoding; Procedure

- III -

东北电力大学计算机科学与技术专业 综合设计报告

第一章 课题描述

1.1问题描述

利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。

1.2需求分析

在本例中设置发送者和接受者两个功能，

1.2.1发送者的功能：

①输入待传送的字符信息；

②统计字符信息中出现的字符种类数和各字符出现的次数（频率）； ②根据字符的种类数和各自出现的次数建立哈夫曼树； ③利用以上哈夫曼树求出各字符的哈夫曼编码； ④将字符信息转换成对应的编码信息进行传送。

1.2.2接受者的功能：

①接收发送者传送来的编码信息；

②利用上述哈夫曼树对编码信息进行翻译，即将编码信息还原成发送前的字符信息。 从以上分析可发现，在本例中的主要算法有三个： （1）哈夫曼树的建立； （2）哈夫曼编码的生成； （3）对编码信息的翻译。

1.3程序设计目标

层次一：编程从文件中读取一段报文，首先统计字符的频度，然后建立哈夫曼树，并给出报文的编码，然后根据使用者的需要对指定文件里的任意二进制编码进行译码并显示。

层次二：使用者从系统界面输入字符串，统计从键盘输入的字符串信息，然后建立哈夫曼树，并给出报文的编码，然后根据使用者的需要对指定文件里的或者使用者从系统界面输入任意二进制编码的进行译码并显示。

- 1 -

东北电力大学计算机科学与技术专业 综合设计报告

第二章 设计简介及设计方案论述

2.1设计简介

文字处理是现代计算机应用的重要领域。文本由字符组成，字符以某种编码形式存储在计算机中。每个字符的编码可以是相等长度的，也可以是不等长度的。ASCII编码是等长编码。为了提高存储和处理文本的效率，在一些计算机应用场合，如数据通信，常采用不等长的编码，对常用的字符用较少的码位，不常出现的字符用较多的码位编码，从而减少文本的存储长度。哈夫曼编码就是用于此目的的不等长编码方法。所以本次设计就是通过构造哈夫曼树来生成哈夫曼编码，最终完成设计要求。

2.2设计方案论述

哈夫曼编码/译码程序主要由主函数、哈夫曼树类和各种功能函数组成，程序运行时首先进入主函数，对各种功能函数进行调用，从而实现了整个程序的运行。将各种不同的函数分别包含在各自的结构体中，使整个程序结构更加的清晰明了，各功能相互独立且紧密联系，有利于编程的实现，同时也体现了面向对象设计语言的封装性。在主菜单中运用了switch()函数和“case”语句，便于对整个程序操作和控制；对数据保存在文档中，则运用了文件I/O流和C语言的文件处理方式，进行文件与内存之间输入，输出数据。

2.3概要设计

2.3.1第一部分功能的实现

在主函数声明HuffmanTree1类的对象HuffmanNode，然后用HuffmanNode调用它的

成员函数TranslatedCode()，此函数能读取Adata.txt里的字符串并统计，然后建立哈夫曼树并对各个字符编码和保存相关信息。然后对象HuffmanNode再调用成员函数TranslateArtcle（）对指定文件得到的二进制编码进行译码，并保存翻译得到的信息。

2.3.1第二部分功能的实现

获取并保存从键盘输入的字符串，并统计其信息。然后利用这些信息建立哈夫曼树对各个字符进行编码和保存相关信息。接着可以调用函数HuffmanTranslateCoding2（）对指定文件得到的二进制编码信息进行译码和保存得到的翻译信息，或者可以调用HuffmanTranslateCoding()对从系统页面输入的二进制编码进行翻译并保存翻译信息

- 2 -

东北电力大学计算机科学与技术专业 综合设计报告

第三章 详细设计

3.1 哈夫曼树

哈夫曼树也称最优二叉树.给定一组具有确定权值的叶子结点,可以构造出不同的二叉树,将其中带权路径长度最小的二叉树称为哈夫曼树.其中,叶子结点的权值(weight)是对叶子结点赋予的一个有意义的数值量.设二叉树具有n个带权值的叶子结点,从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度(weighted path length),记为:

WPL=?Wklk,wk为第k个叶子结点的权值,lk为从根结点到第k个叶子结点的路径

k?1n长度.

3.2 哈夫曼算法

3.2.1 基本思想

根据,哈夫曼的定义,一棵二叉树要使其带权路径长度最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点.依据这个特点便提出了哈夫曼算法,其基本思想是:

(1) 初始化:由给定的n个权值{w1, w2,?, wn}构造n棵只有一个根结点的二叉树,从而得到一个二叉树集合F={ T1,T2,?,Tn};

(2) 选取与合并:在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一颗新的二叉树,这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和;

(3) 删除与加入:在F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到F中;

(4) 重复(2)、(3)两步,当集合F中只剩下一棵二叉树时,这棵二叉树便是哈夫曼

- 3 -

东北电力大学计算机科学与技术专业 综合设计报告

树.

3.2.2 存储结构

在由哈夫曼算法构造的哈夫曼树中,非叶子结点的度均为2，根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,其中有n-1个非叶子结点,它们是在n-1次的合并过程中生成的.为了便于选取根结点权值最小的二叉树以及合并操作,设置一个数组HuffmanNode[2n-1]保存哈夫曼树中各结点的信息,数组元素的结点结构如图3-1所示.

图3-1 哈夫曼树其中,

weight:权值域,保存该结点的权值;

lchild:指针域,保存该结点的左孩子结点在数组中的下标; rchild:指针域,保存该结点的右孩子结点在数组中的下标; parent:指针域,保存该结点的双亲结点在数组中的下标. Inf:存储相关的字符信息

可以用C中的结构类型定义上述结点. struct HuffmanNode {char inf; int weight;

int parent; int lchild,rchild;

weight parent lchild rchild inf 的结点结构

};

3.3 哈夫曼编码

哈夫曼树可用于构造最短的不等长编码方案,具体做法如下:设需要编码的字符集合为{d1,d2,?,dn},它们在字符串中出现的频率为{w1, w2,?, wn},以d1,d2,?,dn作为叶子结点, w1, w2,?, wn作为叶子结点的权值,构造一颗哈夫曼编码树,规定哈夫曼编码树的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径组成的0和1的序列便为该叶子结点对应字符的编码,称为哈夫曼编码(Huffman Code).

- 4 -

东北电力大学计算机科学与技术专业 综合设计报告

在哈夫曼编码树中,数的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和,所以采用哈夫曼树构造的编码是一种能使字符串的编码总长度最短的不等长编码.由于哈夫曼编码树的每个字符结点都是叶子结点,它们不可能在根结点到其他字符结点的路径上,所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀,从而保证了解码的唯一性.

3.4 C++文件I/O流

3.4.1 文件的打开与关闭

本程序中，建立流对象调用成员函数open和close进行文件的打开和关闭。 成员函数open返回非零值或者true，表示流对象已经成功关联到磁盘文件，否则返回0或者false表示该流对象没有关联到文件。

成员函数close首先刷新缓冲区，把所有等待输出的内容写到磁盘文件中，然后关闭磁盘文件，并断开磁盘文件与文件缓冲区的联系。

3.4.2 文件的读写

由于ifstream、ofstream、fstream分别派生自istream、ostream、iostream，因此定义于类istream、ostream、iostream中的大部分共有成员函数。

流插入运算符函数operator<<和流提取运算符函数operator>>、put/get/getline函数主要用于格式化I/O。write/ read函数则常用于无格式化I/O。

3.5 C语言文件处理方式

3.5.1 结构体FILE

结构体FILE类型可以用来定义文件型指针变量，可以使指针指向某一个文件的结构体变量，从而通过该结构体变量中的文件信息能够访问该文件。例如： FILE *fp;

3.5.2 文件的打开（fopen函数）和文件的打开（fclose函数）

FILE *fp;

fp= fopen(文件名，使用文件方式)； fclose（文件指针）； 例如：

- 5 -

东北电力大学计算机科学与技术专业 综合设计报告

FILE *fp;

fp=fopen(“al”,”w”); fclose(fp);

3.5.3 文件的读写 fputc函数

把一个字符写到磁盘文件上去，其一般调用形式为 putc(ch,fp);

其中ch是要输出的字符。fp是文件指针变量。

fget函数

从指定的文件读入一个字符，该文件必须是以读或读写方式打开的。

fgetc函数的调用形式 ch=fgetc(fp);

其中ch是要输出的字符。fp是文件指针变量。

3.6程序功能的详细设计 请看附录的源程序的 详细清单

第四章 设计结果及分析

4.1 设计系统功能

层次一：编程从文件中读取一段报文，首先统计字符的频度，然后建立哈夫曼树，并给出报文的编码，然后根据使用者的需要对指定文件里的任意二进制编码进行译码并显示。

层次二：使用者从系统界面输入字符串，统计从键盘输入的字符串信息，然后建立哈夫曼树，并给出报文的编码，然后根据使用者的需要对指定文件里的或者使用者从系统界面输入任意二进制编码的进行译码并显示。

- 6 -

东北电力大学计算机科学与技术专业 综合设计报告

4.2 进行系统测试

图4-1 系统界面

- 7 -

本文来源：https://www.bwwdw.com/article/1wz2.html