Question

求助有关哈夫曼树编码的问题?急!

即任意输入一串字符,统计每个字符出现的个数作为哈夫曼树中对应的叶子结点的权值,构建一棵哈夫曼树,请重点说明怎么统计出字符出现的频率后传给存放权值的数组?并输出来!例如:输入aabcbabd后,会输出a--3
b--3 c--1 d--1(数组也是动态分配内存的)
由于刚加入百度,积分很低,无法悬赏分值,请多多帮忙!

Answer 1

我去年数据结构课程设计做的就是这个,具体什么意思也忘得差不多了
反正做了好多天的
把这段代码复制给你
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC, LNode &L,int n)
{ //构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC

int m,i;
int s1,s2;

HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
LNode *L1;
L1=L.next; //统计出来的各结点的data,及字母出现的次数
for(p=*HT+1,i=1;i<=n;++i,++p,L1=L1->next) //初始化前 n个结点
{
(*p).num=i; //序号
(*p).weight=L1->n; //权重
(*p).data =L1->data;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}

for(;i<=m;++i,++p) //初始化剩下的结点
{
(*p).parent=0 ;
(*p).data='\0' ;
(*p).num=i;
}

HuffmanTree H_T; //辅助存储单元,用它进行堆排序调用
int j;
int r=n;

for(i=n+1;i<=m;i++) //m=1说明建HT完成,m是有用数据个数
{

H_T=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号空间不用
j=1;
for (i=1;i<=r;i++)
{
if ((*HT)[i].parent==0)
{
H_T[j].num=(*HT)[i].num; //复制HT中的数据；HT不能动!!!
H_T[j].weight=(*HT)[i].weight;
j++;
}
}
r++; //下次复制数据要多复制一位
//用堆筛选出weight最小的两个结点,返回下标s1,s2 ，s1是最小的
select(H_T,j-1,&s1); //分别调用函数,获得s1,s2
select(H_T,j-1,&s2);
// cout<<s1<<" "<<s2<<endl;
(*HT)[s1].parent=(*HT)[s2].parent=r;
(*HT)[r].lchild=s1;
(*HT)[r].rchild=s2;
(*HT)[r].weight=(*HT)[s1].weight+(*HT)[s2].weight;
free(H_T); //释放空间
}

/*for(i=1;i<=m;++i)
{
cout<<(*HT)[i].parent<<(*HT)[i].lchild<<(*HT)[i].rchild<<endl;

}*/ // 检查是否出错时调用它

ofstream code ; //将每个字符的Huffman编码存进文件
code.open("code.txt");

// 从叶子到根逆向求每个字符的赫夫曼编码
*HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); // 分配n个字符编码的头指针向量(0不用)

int c,f,start;

cd=(char*)malloc(n*sizeof(char));
cd[n-1]='\0'; // 编码结束符
for(i=1;i<=n;i++)
{ //求赫夫曼编码
start=n-1; // 编码结束符位置
for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent) // 从叶子到根逆向求编码

if((*HT)[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
(*HC)[i]=(char*)malloc((n-start)*sizeof(char)); // 为第i个字符编码分配空间

strcpy((*HC)[i],&cd[start]); //从cd复制编码(串)到HC
}
free(cd); // 释放工作空间

for (i=1;i<=n;i++)
{
code<<(*HT)[i].data <<(*HC)[i]<<endl; //将数据输入文件
}

cout<<endl;
cout<<"已经将字符编码写进文件"<<endl;
cout<<"是否要显示编码,如果需要,输入y:"<<endl;
char ff;
cin>>ff;
if(ff=='y')
{
for (i=1;i<=n;i++)//将编码输出
{
cout<<(*HT)[i].data<<"的编码是";
cout<<(*HC)[i]<<endl;
}
}

}