用C语言构建哈夫曼树,正数测试结果通过,但小数测试结果未通过。
#include "HuffmanTree.h"
#include
#include
int CreateHuffman(bnode HT[], double w[], int n){
int i,min1,min2;
double sum;
for (i=0;i { //建立n个单结点的树
HT[i].lchild=-1;
HT[i].rchild=-1;
HT[i].parent=-1; // parent=-1表示是树根
HT[i].weight=w[i];
HT[i].pos=i;
}
for (i=n;i<2*n;i++){
SelectTwoMin(HT, i, min1, min2); //选择树根权值最小的两棵树
HT[min1].parent=i;
HT[min2].parent=i;
HT[i].lchild=min1;
HT[i].rchild=min2;
HT[i].parent=-1;
HT[i].weight= HT[min1].weight+ HT[min2].weight;
HT[i].pos=i; }
}
void SelectTwoMin(bnode HT[],int len, int &min1, int &min2){
// 在HT数组中,在前面的len个元素中寻找两个权值最小的根结点的位置,给min1和min2赋值
// begin
int m1=1000, m2=1000;
for(int i=1; i<=len; i++){
if(HT[i].parent==-1&&HT[i].weight{
m1=HT[i].weight;
min1=i;
}
}
for(int i=1; i<=len; i++){
if(HT[i].parent==-1 && HT[i].weight{
m2=HT[i].weight;
min2=i;
}
}
//end
}
void FillLength(bnode HT[], int root, int h_root){ //填写一个树上各结点的路径长度
HT[root].length=h_root;
if (HT[root].lchild!=-1) FillLength(HT, HT[root].lchild,h_root+1);
if (HT[root].rchild!=-1) FillLength(HT, HT[root].rchild,h_root+1);
return;
}
double WPL(bnode HT[],int n){
double L=0;
int i;
FillLength(HT,2*n-2, 0); //计算结点的路径长度
for (i=0;i
L+=HT[i].weight*HT[i].length;
return L;
}
我尝试将int更改为float等方法,但是小数那一组数据测试结果始终错误。
希望第二组小数数据测试能通过
请看这个帖子下面的 ‘相关推荐’, 你会得到很多启发。
在搜索的那个函数里面的i是从1开始遍历的,漏掉啦
不知道你这个问题是否已经解决, 如果还没有解决的话: