哈夫曼树顺序存储结构的创建、编码、译码(南邮实验二)
哈夫曼树顺序存储结构的创建、编码、译码
结构体如下
typedef struct HFMTreeNode{
ElementType Data;
int w; //权值
int parent,lchild,rchild;
string s=""; //用于存储译码结果
}HFMTreeNode;
哈夫曼树创建过程
void createHFMTree (HFMTreeNode ht[],int N){
int i,j,k,lmin,rmin,min1,min2;
for(i=1;i<2*N;i++)
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for(i=N+1;i<2*N;i++)
{
lmin=rmin=-1;
min1=min2=10000;
for(k=1;k<=i-1;k++){
if(ht[k].parent==-1)
{
if(ht[k].w<min1){
min2=min1;
rmin=lmin;
min1=ht[k].w;
lmin=k;
}
else if(ht[k].w<min2){
min2=ht[k].w;
rmin=k;
}
}
}
ht[lmin].parent=i;
ht[rmin].parent=i;
ht[i].w=ht[lmin].w+ht[rmin].w;
ht[i].lchild=lmin;
ht[i].rchild=rmin;
}
}
哈夫曼树编码
自底向上编码最后再倒序
void codeHFMTree(HFMTreeNode ht[],int N){
for(int i=1;i<=N;i++){
int j=i;
while(j!=2*N-1)
{
int temp=j;
j=ht[j].parent;
if(ht[j].lchild==temp)
ht[i].s+='0';
if(ht[j].rchild==temp)
ht[i].s+='1';
}
reverse(ht[i].s.begin(),ht[i].s.end()); //编码结果倒序
}
}
哈夫曼树译码
译码结果以字符串返还
string decodeHFMTree(string st,HFMTreeNode ht[],int N)
{
int i=0;
string re,te;
stringstream result(""),temp("");
while(i<st.length()){
temp<<st.at(i++);
te=temp.str();
for(int j=1;j<=N;j++){
if(!te.compare(ht[j].s))
{
result<<ht[j].Data;
temp.str("");
break;
}
}
}
re=result.str();
return re;
}
最后测试的结果如下: