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

-
. z
邮电大学电信工程学院
第1页
数据构造实验报告
实验名称： 实验三 树——哈夫曼编/解码器
学生：
—循环实现；
以循环构造，实现分支结点的合成，合成规则按照huffman树构成规则进展。
关键点：选择最小和次小结点合成。
void Huffman::CreateHTree()
{
HTree = new HNode [2*n-1]; //根据权重数组a[0..n-1] 初始化Huffman树
for (int j = 0; j < n; j++)
{
-
. z
邮电大学电信工程学院
第1页
HTree[j].weight = a[j];
HTree[j].LChild = HTree[j].RChild = HTree[j].parent = -1;
}
int *,y;
for (int i = n; i < 2*n-1; i++) //开场建Huffman树
{
SelectMin( HTree, i, *, y); //从1~i中选出两个权值最小的结点
HTree[*].parent = HTree[y].parent = i;
HTree[i].weight = HTree[*].weight+ HTree[y].weight;
HTree[i].LChild = *;
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; }
-
. z
邮电大学电信工程学院
第1页
}
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)创立编码表
算法过程：从叶子到根---自底向上
-
. z
邮电大学电信工程学院
第1页
首先定义码表存储空间；
循环对n个叶子结点自底向上回溯到根，记下途径的左右关系，形成编码的逆序串；
将各个叶子结点对应的逆序串反序即可。
void Huffman::CreateCodeTable()
{
HCodeTable = new HCode[n]; //生成编码表
for (int i=0;i<n;i++)
{
HCodeTable[i].data = l[i];
int child = i; //孩子结点编号
in