北邮信通院数据结构实验报告三--哈夫曼编码器.docx

数据结构实验陈说之迟辟智美创作
实验名称： 实验三 树——哈夫曼编/ 解码器
学生姓名：
班级：
班内序号：
学号：
日 期： 2014 年 12 月 11 日
1．实验要求
利用二叉树结构实现赫夫曼编 / 解码器 .
基parent = i;
HTree[i].weight= HTree[x].weight+
HTree[y].weight;
HTree[i].LChild = x;
HTree[i].RChild = y;
HTree[i].parent = -1;
}
}
时间复杂度为O(n2)
void Huffman::SelectMin( HNode *hTree,int n, int &i1, int
&i2 )
{
int i;
// 找一个比力值的起始值
for(i=0; i<n; i++) // 找 i1
{ if(hTree[i].parent==-1 )
{ i1=i; break; }
}
i++;
for( ; i<n; i++) // 找 i2
{ if(hTree[i].parent==-1 )
{ i2=i;
break; }
}
if(hTree[i1].weight>hTree[i2].weight) //i1 指向最小的
{ int j=i2;i2=i1; i1 = j; }
// 开始找最小的两个
i++;
for( ; i<n; i++)
{ if(hTree[i].parent==-1
&& hTree[i].weight < hTree[i1].weight )
{ i2=i1; i1 = i; }
else if( hTree[i].parent==-1
&& hTree[i].weight < hTree[i2].weight)
{ i2=i; }
}
}
时间复杂度为 O(n)
(3)创立编码表
算法过程：从叶子到根--- 自底向上
首先界说码表存储空间；
循环对 n 个叶子结点自底向上回溯到根，记下途径的
左右关系，形成编码的逆序串；
将各个叶子结点对应的逆序串反序即可.
void Huffman::CreateCodeTable()
{
HCodeTable = new HCode[n]; // 生成编码表
for (int i=0;i<n;i++)
{
HCodeTable[i].data = l[i];
int child = i;//孩子结点编号
int parent = HTree[i].parent; // 以后结点的父结点编号
int k=0;
while(parent!=-1)
{
if (child==HTree[parent].LChild)// 左 孩
子标‘0’
HCodeTable[i].code[k] = '0';
else
HCodeTable[i].code[k] = '1' ;// 右 孩 子 标
‘1’
k++;
child = parent;//迭代
parent = HTree[child].parent;
}
HCodeTable[i].code[k] = '\0';
Reverse(HCodeTable[i].code); //将编码字符
逆置
}
}
时间复杂度为 O(n)
(4)生成编码串
将输入的字符串的每一个字符与编码表比力
void Huffman::Encode(char *d)// 编码， d 为编码后的字符串
{
char *s = str;
while(*s!='\0')
{
for (int i=0;i<n;i++)
if (*s == HCodeTable[i].data )
{
strcat(d, HCodeTable[i].code);
break;
}
s++;
}
}
时间复杂度为 O(n)
( 5)解码:
算法过程： 从根到叶子--- 自顶向下
基于 huffman 树存储数组，从根结点开始，依据输入待解
码串 s 中码字 0 或 1，分别向左或右跟踪至叶子结点，叶子
结点对应的字符(见码表)，即为解码获得的字符；
只要 s 串为结束，重复上述过程
void Huffman::Decode(char* s, char *d)//解码， s 为编码
串， d 为解码后的字符串
{
while(*s!='\0')
{
int parent = 2*n-2;// 根 结 点 在
HTree 中的下标
while (HTree[parent].LChild!=-1) //如果不是叶