一实验内容描述 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.自定义结点结构包括整型变量weightparentleftright字符型变量等。
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。
算法的时空分析时间复杂度0n最低当所有字符重复。
时间复杂度O(??2)n*(1+n)/2 最高当所有字符不相同。
3数据结构用chars[]字符型数组存储字符num[]存储各字符相应个数。
4程序结构从主函数直接调用。
5调试分析输入字符串 aabbbbbccddddefffggh
6测试结果如图为输入、输出结果
3. 查找最小权值点函数
1问题描述访问哈夫曼树组结点在结点parent值为0的节点中挑选最小权值的点。
2算法分析min初始化为0依次读取数组结点元素当parent值为0时权值与最小值
相比较小则赋值给最小值用k记录节点位置全部比较完后返回最小值点k。
算法的时空分析时间复杂度0n
3数据结构二维数
组存储哈夫曼树整型变量min。
4程序结构从生成哈夫曼树函数中调用。
4.创建哈夫曼树函数
1问题描述读取字符串生成哈夫曼树.
2算法分析读取字符及个数个数作为权值填入哈夫曼数组中parentleftright
初始化为0.选择两个最小值点生成新结点三个结点的parentleftright值依次填写。
再选择最小值点以此循环直至除最后一个所有结点parent值不为0.
算法的时空分析时间复杂度O(??2)2*n+n+1+n+2+…+2n-1=3*n2-n
3数据结构二维数组存储哈夫曼树整型变量weightparentleftright。
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.训练了程序的调试技术。