北邮数据结构实验报告实验三哈夫曼编解码器.doc

数据结构实验报告
实验名称: 实验三——树
学生姓名:

实验目的:
掌握二叉树基本操作的实现方法;
了解哈夫曼树的思想和相关概念;
培养使用二叉树解决实际问题的能力;
题目2:
利用二叉树结果实现哈夫曼编/解码器。
基本要求如下。
初始化(Init):能够对输入的任意长度的字符串s进行统计,统计每个字符的频度,并建立哈夫曼树。
建立编码表(CreateTable):利用已建好的哈夫曼树进行编码,并将每个字符的编码输出。
编码:(Encoding):根据编码表对输入的字符串进行编码,并将编码后的字符串输出。
译码(Decoding):利用已经建好的哈夫曼树对编码后的字符串进行译码,并输出译码结果。
打印(Print):以直观的方式打印哈夫曼树(选作)。
计算输入的字符串编码前和编码后的长度,并进行分析,讨论哈夫曼编码的压缩效果。
测试数据如下:
I love data structure, I puter. I will try my best to study data structure.
提示:
用户界面可以设计为“菜单”方式,能够进行交互。
根据输入的字符串中的每个字符出现的次数统计频度,对没有出现的字符一律不用编码。
2. 程序分析
存储结构
存储结构:三叉链表
关键算法分析
一、关键算法:
1、对三叉链表即哈夫曼树进行初始化
将每个字符当做一个树赋权值,是父结点和左右孩子结点为-1
选取最小两节点
建立新结点存储最小两节点和为权值
设其父结点为-1,左右孩子分别最小两节点
循环以上操作,直到最后形成一棵树
2、建立编码表
取作为叶子结点的字符
判断其为其父结点的左孩子或右孩子
若为左孩子存为0
若为右孩子存为1
判断存值直到工作结点为根节点
将字符对应所存的编号进行倒置并重新存入
3、对数据进行编码
获取字符顺序数组
对字符对应数组进行循环
循环嵌套,输出编号数组所存元素
4、对编码解码
输入需解码的编码
设置指针指向编码数组
根据编码移动链表指针
若为0,则移向左孩子结点,且数组指针加1
若为1,则移向右孩子结点,数组指针加1
若为\0则结束编译
若寻找到叶子结点,则数组指针加1 ,重新查找
二、代码详细分析:
1、初始化哈夫曼树
关键代码:
建立各字符的哈夫曼树:tree[i].weight=a[i]; tree[i].LChild=-1; tree[i].RChild=-1; tree[i].parent=-1;
选取最小两个结点:for(i=0;i<n;i++)
{if(tree[i].parent==-1){i1=i; break;}}i++;
for(;i<n;i++){if(tree[i].parent==-1){i2=i;break;}}
if(tree[i1].weight>tree[i2].weight){j=i2;i2=i1;i1=j;}i++;
for(;i<n;i++){if(tree[i].parent==-1&&tree[i].weight<tree[i1].weight){i2=i1;i1=i; }else if(tree[i].parent==-1&&tre