哈夫曼树的建立及应用
发布网友
发布时间：2022-05-06 21:50
共2个回答
热心网友
时间：2023-09-22 08:46
#include<iomanip.h>
const int n=8;
const int m=2*n-1;
struct tree
{
float weight;
int parent;
int lch,rch;
};
struct codetype
{
int bits[n+1];
int start;
char ch;
};
tree hftree[m+1];
struct codetype code[n+1];
void creathuffmantree()
{
int i,j,p1,p2;
float s1,s2;
for(i=1;i<=m;i++)
{
hftree[i].parent=0;
hftree[i].lch=0;
hftree[i].rch=0;
hftree[i].weight=0; }
cout<<"输入"<<n<<"个权值"<<endl;
for(i=1;i<=n;i++)
cin>>hftree[i].weight;
for(i=n+1;i<=m;i++)
{
p1=p2=0;
s1=s2=32767;
for(j=1;j<=i-1;j++)
if(hftree[j].parent==0)
if(hftree[j].weight<s1)
{
s2=s1;
s1=hftree[j].weight;
p2=p1;
p1=j;
}
else
if(hftree[j].weight<s2)
{
s2=hftree[j].weight;p2=j;
}
hftree[p1].parent=i;
hftree[p2].parent=i;
hftree[i].lch=p1;
hftree[i].rch=p2;
hftree[i].weight=hftree[p1].weight+hftree[p2].weight;
}
}void huffcode()
{
codetype cd;
int c,p;
for(int i=1;i<=n;i++)
{
cd.start=n+1;
cd.ch=96+i;
c=i;
p=hftree[i].parent;
while(p!=0)
{
cd.start--;
if(hftree[p].lch==c)cd.bits[cd.start]=0;
else cd.bits[cd.start]=1;
c=p;
p=hftree[p].parent;
}
code[i]=cd;
}
for(i=1;i<=n;i++)
{
cout<<"字符"<<code[i].ch<<"的权值为："<<hftree[i].weight<<setw(5)<<"编码为：";
for(int j=code[i].start;j<=n;j++)
cout<<code[i].bits[j]<<" ";
cout<<endl;
}}void trancode()
{
int i=m;char b;
cout<<"请输入一串二进制编码（0、1以外的数结束）";
cin>>b;
while((b=='0')||(b=='1'))
{
if(b=='0')i=hftree[i].lch;
else i=hftree[i].rch;
if(hftree[i].lch==0)
{
cout<<code[i].ch;
i=m;
}
cin>>b;
}}void main()
{
creathuffmantree();
huffcode();
trancode();
}
热心网友
时间：2023-09-22 08:46
void HuffmanTree(HuffmanTree &HT, int * w, int n)
{
//w 存放n 个字符的权值（均>0），构造赫夫曼树HT
if (n<=1) return;
m=2* n-1;
HT=(HuffmanTree)malloc(m+1) * sizeof(HTNode); //分配存储空间
//用给定的n个权值，构造n棵只有一个根结点的二叉树
for (p=1, i=1, j=0; i<=n; ++i, ++p, ++j)
HT[p]={ w[j], 0, 0, 0}; //HT[0]未用
//按构造哈夫曼树的步骤2、3、4，建哈夫曼树
for (; i<m; ++i;) {
//在HT[1..i-1] 选择parent为0且weight最小的两个结点，
//其序号分别为s1和s2。
Select(HT, i-1, s1, s2);
HT[s1]. parent =i; HT[s2].parent=i; //HT[i]存放新子树的根结点，
HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight; }
}
