1）编写函数实现选择parent为0且权值最小的两个根结点的算法
成都创新互联公司-专业网站定制、快速模板网站建设、高性价比丰城网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式丰城网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖丰城地区。费用合理售后完善，十多年实体公司更值得信赖。
2）编写函数实现统计字符串中字符的种类以及各类字符的个数。
3）编写函数构造赫夫曼树。
4）编写函数实现由赫夫曼树求赫夫曼编码表。
5）编写函数实现将正文转换为相应的编码文件。
6）编写函数实现将编码文件进行译码。
7）编写主控函数，完成本实验的功能。
建议： 用类似的方法，可以将某一学科的总分统计出来，并填入第48行相应的单元格中。
class HaffmanNode //哈夫曼树的结点类
{
int weight; //权值
int parent,left,right; //父母结点和左右孩子下标
public HaffmanNode(int weight)
{
this.weight = weight;
this.parent=-1;
this.left=-1;
this.right=-1;
}
public HaffmanNode()
{
this(0);
}
public String toString()
{
return this.weight+", "+this.parent+", "+this.left+", "+this.right;
}
return code;
}
public static void main(String[] args)
{
int[] weight={5,29,7,8,14,23,3,11}; //指定权值集合
HaffmanTree htree = new HaffmanTree(weight);
System.out.println("哈夫曼树的结点数组:\n"+htree.toString());
String[] code = htree.haffmanCode();
System.out.println("哈夫曼编码:");
for (int i=0; icode.length; i++)
System.out.println(code[i]);
}
}
#includestdio.h
#includestring.h
#define N 50 //叶子结点数
#define M 2*N-1 //树中结点总数
typedef struct
{ char data[5]; //节点值
int weight; //权重
int parent; //双亲结点
int lchild; //左孩子结点
int rchild; //右孩子结点
}htnode;
typedef struct
{ char cd[N]; //存放哈夫曼码
int start;
}hcode;
void createht(htnode ht[],int n) //构造哈夫曼树
{ int i,k,lnode,rnode;
int min1,min2;
for(i=0;i2*n-1;i++) //所有结点的相关域置初值-1
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for(i=n;i2*n-1;i++) //构造哈夫曼树
{ min1=min2=32767; //lchild和rchild为最小权重的两个结点位置
lnode=rnode=-1;
for(k=0;k=i-1;k++)
if(ht[k].parent==-1) //只在尚未构造二叉树的结点中查找
{ if(ht[k].weightmin1)
{ min2=min1;
rnode=lnode;
min1=ht[k].weight;
lnode=k;
}
else if(ht[k].weightmin2)
{ min2=ht[k].weight;
rnode=k;
}
}
ht[lnode].parent=i;
ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;
ht[i].rchild=rnode;
}
}
void createhcode(htnode ht[],hcode hcd[],int n) //构造哈夫曼编码
{ int i,f,c;
hcode hc;
for(i=0;in;i++) //根据哈夫曼树求哈夫曼编码
{ hc.start=n;
c=i;
f=ht[i].parent;
while(f!=-1) //循序直到树根结点
{ if(ht[f].lchild==c) //处理左孩子结点
hc.cd[hc.start--]='0';
else
hc.cd[hc.start--]='1'; //处理右孩子结点
c=f;
f=ht[f].parent;
}
hc.start++; //start指向哈夫曼编码最开始字符
hcd[i]=hc;
}
}
void disphcode(htnode ht[],hcode hcd[],int n) // 输出哈夫曼编码
{ int i,k;
int sum=0,m=0,j;
printf("输出哈夫曼编码：\n");
for(i=0;in;i++)
{ j=0;
printf(" %s:\t",ht[i].data);
for(k=hcd[i].start;k=n;k++)
{ printf("%c",hcd[i].cd[k]);
j++;
}
m+=ht[i].weight;
sum+=ht[i].weight*j;
printf("\n");
}
printf("\n平均长度=%g\n",1.0*sum/m);
}
void main()
{ int n=15,i;
char *str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123};
htnode ht[M];
hcode hcd[N];
for(i=0;in;i++)
{ strcpy(ht[i].data,str[i]);
ht[i].weight=fnum[i];
}
printf("\n");
createht(ht,n);
createhcode(ht,hcd,n);
disphcode(ht,hcd,n);
printf("\n");
}
真懒啊你真懒啊你真懒啊你真懒啊你真懒啊你真懒啊你真懒啊你真懒啊你真懒啊你真懒啊你
