实验报告(哈夫曼编码)

哈弗曼编码实验报告

一．实验内容描述

1.实验名称：

哈夫曼编码译码器

2.实验内容：

利用哈夫曼树实现电文和比特流互相转换的功能。

二．存储结构分析

1.存储需编码字符的字符型数组 chars[N]

2.哈夫曼树的结点元素存储结构

typedef struct {

int weight,parent,left,right;

}HTNode;

3.哈夫曼树存储结构

typedef struct {

HTNode *Htree;

int root；

}HuffmanTree；

4.存储每个字符对应的编码的二维数组

HC[N][N];

三．数据结构分析

1.宏定义 OK为1,Error为0 ，定义Status为int型，N为100，方便调节。

2.自定义结点结构：包括整型变量weight，parent，left，right；字符型变量等。

3.定义数组HC[N][N]，二维数组，可实现编码的存储。

四．程序功能

======Huffman编码解码器======

1----------输入字符创建编码

2----------输出统计结果

3----------打印哈夫曼树

4----------打印哈夫曼编码

5----------电文->比特流

6----------比特流->电文

五．各函数分析

1.主函数

(1)问题描述

显示功能菜单,等待选择。

哈弗曼编码实验报告

1,输入字符创建编码：输入一段字符串，存储到字符型数组中。

2,输出统计结果：对1中读取的字符串进行统计，输出字符及相应个数。

3,打印哈夫曼树：生成哈夫曼树，并打印其存储数组。

4,打印哈夫曼编码：利用哈夫曼树对字符编码，输出字符及相应编码。

5, 电文->比特流：输入一段字符，完成对其的编码，输出。

6，比特流->电文：输入一段编码，完成对其的译码，输出相应字符串。

2. 统计字符函数

（1）问题描述：从主函数读取输入的字符串，统计个数，完成输出相应字符串及个数。

（2）算法分析：依次读取字符，先判断读取的字符是否出现过，循环比较，出现过则对应个数加1，未出现过填入chars[N]数组，个数为1。

算法的时空分析：时间复杂度0（n）：最低，当所有字符重复。

时间复杂度O( ²)：n*(1+n)/2 最高，当所有字符不相同。

（3）数据结构：用chars[]字符型数组存储字符，num[]存储各字符相应个数。

（4）程序结构：从主函数直接调用。

（5）调试分析：输入字符串 aabbbbbccddddefffggh

（6）测试结果：如图为输入、输出结果

3. 查找最小权值点函数

（1）问题描述：访问哈夫曼树组结点，在结点parent值为0的节点中，挑选最小权值的点。

（2）算法分析：min初始化为0，依次读取数组结点元素，当parent值为0时，权值与最小值相比较，小则赋值给最小值，用k记录节点位置，全部比较完后，返回最小值点k。 算法的时空分析：时间复杂度0（n）

（3）数据结构：二维数组存储哈夫曼树，整型变量min。

（4）程序结构：从生成哈夫曼树函数中调用。

4.创建哈夫曼树函数

（1）问题描述：读取字符串，生成哈夫曼树.

（2）算法分析：读取字符及个数，个数作为权值填入哈夫曼数组中，parent，left，right初始化为0.选择两个最小值点，生成新结点，三个结点的parent，left，right值依次填写。再选择最小值点，以此循环，直至除最后一个所有结点parent值不为0.

算法的时空分析：时间复杂度O( ²)：2*（n+n+1+n+2+…+2n-1）=3*n²-n

（3）数据结构：二维数组存储哈夫曼树，整型变量weight，parent，left，right。

（4）程序结构：从主函数中调用，调用了查找最小权值点函数。

（5）调试分析：用输入的字符串创建哈夫曼树，打印数组。

（6）测试结果：如图为输入、输出结果，

哈弗曼编码实验报告

5．字符编码函数

（1）问题描述：利用哈夫曼树对已有字符进行编码，结果存储在二维数组HC[][]中。

（2）算法分析：初始化栈，对哈夫曼树进行先序遍历，遇左子树0进栈，右子树1进栈，遇到叶子结点输出栈内元素，保存在HC数组中，出栈一个元素，继续遍历，直至遍历结束，所有字符完成编码。

算法的时空分析：时间复杂度O( ²)

（3）数据结构：二维数组存储哈夫曼树，栈，二维数组HC[][]存储编码。

（4）程序结构：主函数直接调用了该函数，该函数调用了进栈、出栈、输出栈的函数。

（5）测试结果：如图为输出结果。

6.字符串转换为编码函数

（1）问题描述：利用字符及其编码，将输入的电文转换为比特流。

（2）算法分析：依次读取字符，调用其在HC中对应编码，输出编码字符串，再读取下一个字符，直至所有字符完成编码。

算法的时空分析：时间复杂度O( )：n个字符访问n次编码数组。

（3）数据结构：二维数组存储哈夫曼树，二维数组HC[][]存储编码。

（4）程序结构：主函数直接调用了该函数。

（5）调试分析：主函数输入电文 ddbagheccf

（6）测试结果：如图为输出结果。

哈弗曼编码实验报告

7.编码转换为字符串函数

（1）问题描述：利用生成的哈夫曼树，将输入的比特流转换为电文。

（2）算法分析：依次读取编码，从哈夫曼树的树根开始，遇到1访问左子树，遇到0访问右子树，直至访问到叶子结点，输出其结点元素，继续读取编码，直至所有比特流完成译码。 算法的时空分析：时间复杂度O( )：n个字码访问n次哈夫曼树数组。

（3）数据结构：二维数组存储哈夫曼树。

（4）程序结构：主函数直接调用了该函数。

（5）调试分析：主函数输入比特流 010011111011011100110111111010

（6）测试结果：如图为输出结果。

六.实验体会与收获

1.熟练掌握了定义哈夫曼数组、定义各类型存储数组的基本操作

2．掌握了创建哈夫曼树、生成编码、电文比特流互相转换的算法

3.了解了如何利用通过调用函数使精简、清晰化。

4.了解了如何增强程序健壮性

5.训练了程序的调试技术。