实验报告(哈夫曼编码)

一实验内容描述 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(??2)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)2*n+n+1+n+2+…+2n-1=3*n2-n
3数据结构二维数组存储哈夫曼树整型变量weightparentleftright。
4程序结构从主函数中调用调用了查找最小权值点函数。
5调试分析用输入的字符串创建哈夫曼树打印数组。
6测试结果如图为输入、输出结果












5字符编码函数
1问题描述利用哈夫曼树对已有字符进行编码结果存储在二维数组HC[][]中。
2算法分析初始化栈对哈夫曼树进行先序遍历遇左子树0进栈右子树1进栈遇
到叶子结点输出栈内元素保存在HC数组中出栈一个元素继续遍历直至遍历结束所
有字符完成编码。
算法的时空分析时间复杂度O(??2)
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.训练了程序的调试技术。