哈夫曼树的问题？
以下是哈夫曼树的代码，但是有点错误，是逻辑错误，运行后不正确，不知道为什么？
找了好久找不到错误的所在，所以请大家帮帮忙！！！！
谢谢！！！！
代码如下：
#include<iostream>
#include<stdlib.h>
using namespace std ;
const float MaxValue = 2.0 ; //初始设定的权值最大值
const int MaxBit = 10 ; //初始设定的最大编码位数
const int MaxN = 20 ; //初始设定的最大结点个数
//哈夫曼数的结点结构
struct HaffNode
{
float weight ; //权值
int flag ; //标记
int parent ; //双亲结点下标
int leftchild ; //左孩子下标
int rightchild ; //右孩子下标
} ;
//存放哈夫曼编码的数组元素结构
struct Code
{
int bit[MaxN] ; //数组
int start ; //编码的起始下标
float weight ; //字符的权值
} ;
//建立叶结点个数为n权值数组为weight的哈夫曼树haffTree
void Haffman(float weight[] , int n , HaffNode haffTree[])
{
int j , x1 , x2 ;
float m1 , m2 ;
//哈夫曼树haffTree[]初始化。n个叶结点共有2n-1个结点
for(int i = 0 ; i < 2*n -1 ; i++)
{
if(i < n)
haffTree[i].weight = weight[i] ;
else
haffTree[i].weight = 0.0 ;
haffTree[i].parent = 0 ;
haffTree[i].flag = 0 ;
haffTree[i].leftchild = -1 ;
haffTree[i].rightchild = -1 ;
}
//构造哈夫曼树haffTree[]的n-1个非叶结点
for(int i = 0 ; i < n-1 ; i++)
{
m1 = m2 = MaxValue ;
x1 = x2 = 0 ;
for(j=0 ; j < n+i ; j++)
{
if(haffTree[j].weight < m1 && haffTree[j].flag == 0)
{
m2 = m1 ;
x2 = x1 ;
m1 = haffTree[j].weight ;
x1 = j ;
}
else
if(haffTree[j].weight < m2 && haffTree[j].flag == 0)
{
m2 = haffTree[j].weight ;
x2 = j ;
}
}
//将找出的两棵权值最小的子树合并为一棵子树
haffTree[x1].parent = n+1 ;
haffTree[x2].parent = n+1 ;
haffTree[x1].flag = 1 ;
haffTree[x2].flag = 1 ;
haffTree[n+i].weight = haffTree[x1].weight + haffTree[x2].weight ;
haffTree[n+i].leftchild = x1 ;
haffTree[n+i].rightchild = x2 ;
}
}
//由n个结点的哈夫曼树haffTree[]构造哈夫曼编码
void HaffmanCode(HaffNode haffTree[] , int n , Code haffCode[])
{
Code *cd = new Code ;
int child , parent ;
//求n个叶结点的哈夫曼编码
for(int i=0 ; i < n ; i++)
{
cd->start = n - 1 ;
cd->weight = haffTree[i].weight ;
child = i ;
parent = haffTree[child].parent ;
//由叶结点向上直到根结点
while(parent != 0)
{
if(haffTree[parent].leftchild == child)
cd->bit[cd->start] = 0 ; //左孩子结点的编码为0
else
cd->bit[cd->start] = 1 ; //右孩子结点的编码为1
cd->start -- ;
child = parent ;
parent = haffTree[child].parent ;
}
//保存每个叶结点的编码和不等长编码的起始位
for(int j = cd->start + 1 ; j < n ; j++)
{ haffCode[i].bit[j] = cd->bit[j] ; }
haffCode[i].start = cd->start ;
haffCode[i].weight = cd->weight ; //记住编码对应权值的字符
}
}
int main()
{
int i , j , n = 6 ;
float weight[] = {0.25 , 0.25 , 0.20 , 0.15 , 0.10 , 0.05} ;
HaffNode * myHaffTree = new HaffNode[2*n - 1] ;
Code * myHaffCode = new Code[n] ;
if(n > MaxN)
{
cout << "定义的n越界 ， 请修改MaxN." << endl ;
exit(1) ;
}
Haffman(weight , n , myHaffTree) ;
HaffmanCode(myHaffTree , n , myHaffCode) ;
for(i = 0 ; i < n ; i++)
{
cout << "Weight =" << myHaffCode[i].weight << " ; Code =" ;
for(j = myHaffCode[i].start + 1 ; j < n ; j++)
{ cout << myHaffCode[i].bit[j] ; }
cout << endl ;
}
system("pause") ;
}
问题点数：60、回复次数：6Top
1 楼kikikind（可乐）回复于 2006-03-04 15:19:26 得分 0
我发现错误了~~~修正如下:
#include<iostream>
#include<stdlib.h>
using namespace std ;
const float MaxValue = 2.0 ; //初始设定的权值最大值
const int MaxBit = 10 ; //初始设定的最大编码位数
const int MaxN = 20 ; //初始设定的最大结点个数
//哈夫曼数的结点结构
struct HaffNode
{
float weight ; //权值
int flag ; //标记
int parent ; //双亲结点下标
int leftchild ; //左孩子下标
int rightchild ; //右孩子下标
} ;
//存放哈夫曼编码的数组元素结构
struct Code
{
int bit[MaxN] ; //数组
int start ; //编码的起始下标
float weight ; //字符的权值
} ;
//建立叶结点个数为n权值数组为weight的哈夫曼树haffTree
void Haffman(float weight[] , int n , HaffNode haffTree[])
{
int j , x1 , x2 ;
float m1 , m2 ;
int index = n; //新增变量,用来记录父结点位置
//哈夫曼树haffTree[]初始化。n个叶结点共有2n-1个结点
for(int i = 0 ; i < 2*n -1 ; i++)
{
if(i < n)
haffTree[i].weight = weight[i] ;
else
haffTree[i].weight = 0.0 ;
haffTree[i].parent = 0 ;
haffTree[i].flag = 0 ;
haffTree[i].leftchild = -1 ;
haffTree[i].rightchild = -1 ;
}
//构造哈夫曼树haffTree[]的n-1个非叶结点
for(i = 0 ; i < n-1 ; i++)
{
m1 = m2 = MaxValue ;
x1 = x2 = 0 ;
for(j=0 ; j < n+i ; j++)
{
if(haffTree[j].weight < m1 && haffTree[j].flag == 0)
{
m2 = m1 ;
x2 = x1 ;
m1 = haffTree[j].weight ; //m1 保存当前最少值结点
x1 = j ; //当前最少值下标
}
else
if(haffTree[j].weight < m2 && haffTree[j].flag == 0)
{
m2 = haffTree[j].weight ; //m1 保存当前第二最少值结点
x2 = j ; //当前第二最少值下标
}
}
//将找出的两棵权值最小的子树合并为一棵子树
//haffTree[x1].parent = n+1 ; //有问题：
//haffTree[x2].parent = n+1 ;
haffTree[x1].parent =haffTree[x2].parent = index++;
haffTree[x1].flag = 1 ;
haffTree[x2].flag = 1 ;
haffTree[n+i].weight = haffTree[x1].weight + haffTree[x2].weight ;
haffTree[n+i].leftchild = x1 ;
haffTree[n+i].rightchild = x2 ;
}
}
//由n个结点的哈夫曼树haffTree[]构造哈夫曼编码
void HaffmanCode(HaffNode haffTree[] , int n , Code haffCode[])
{
Code *cd = new Code ;
int child , parent ;
//求n个叶结点的哈夫曼编码
for(int i=0 ; i < n ; i++)
{
cd->start = n - 1 ;
cd->weight = haffTree[i].weight ;
child = i ;
parent = haffTree[child].parent ;
//由叶结点向上直到根结点
while(parent != 0)
{
if(haffTree[parent].leftchild == child)
cd->bit[cd->start] = 0 ; //左孩子结点的编码为0
else
cd->bit[cd->start] = 1 ; //右孩子结点的编码为1
cd->start -- ;
child = parent ;
parent = haffTree[child].parent ;
}
//保存每个叶结点的编码和不等长编码的起始位
for(int j = cd->start + 1 ; j < n ; j++)
{
haffCode[i].bit[j] = cd->bit[j] ;
}
haffCode[i].start = cd->start ;
haffCode[i].weight = cd->weight ; //记住编码对应权值的字符
}
}
int main()
{
int i , j , n = 6 ;
float weight[] = {0.25 , 0.25 , 0.20 , 0.15 , 0.10 , 0.05} ;
HaffNode * myHaffTree = new HaffNode[2*n - 1] ;
Code * myHaffCode = new Code[n] ;
if(n > MaxN)
{
cout << "定义的n越界 ， 请修改MaxN." << endl ;
exit(1) ;
}
Haffman(weight , n , myHaffTree) ;
HaffmanCode(myHaffTree , n , myHaffCode) ;
for(i = 0 ; i < n ; i++)
{
cout << "Weight =" << myHaffCode[i].weight << " ; Code =" ;
for(j = myHaffCode[i].start + 1 ; j < n ; j++)
{
cout << myHaffCode[i].bit[j] ;
}
cout << endl ;
}
system("pause") ;
return 0;
}
---------------------------------
原处这里每次都将父结点指向同一地方了~~~
haffTree[x1].parent = n+1 ; //有问题：
haffTree[x2].parent = n+1 ;
所以要增加一个变里 index 初始值为 n
haffTree[x1].parent =haffTree[x2].parent = index++;
这样每次找出两个最小的值,就增它放在 haffTree[] 数组的第n+1位开始~~~~
(因为本身输入的初始结点放在了 0 ~ n-1的位置上~~~~所以n+1的位置就是从haffTree[n] 开始,所以index初始值为 n)
--------------------------
算法不错哦~~~~好好学习哦~!!:)Top
2 楼manplus（魅力加加）回复于 2006-03-04 15:54:32 得分 0
markTop
3 楼yuucyf（天赐）回复于 2006-03-04 16:48:23 得分 0
谢谢！
确实是这里错：
haffTree[x1].parent = n+1 ; //有问题：
haffTree[x2].parent = n+1 ;
把它改为这样就好了：
haffTree[x1].parent = n+i ;
haffTree[x2].parent = n+i ;
i和1，害我找不到！！！！
非常感谢你，是你帮我找到错误！！！
Top
4 楼kikikind（可乐）回复于 2006-03-05 11:07:37 得分 0
呵呵~~~~帮我加点分哈~~！Top
5 楼yuucyf（天赐）回复于 2006-03-05 12:15:14 得分 0
怎么加分呀！
晕！我以为回答了就有分呢！
不好意思！我想加，但不知道在那！！！Top
6 楼coziness（coziness）回复于 2006-05-28 20:49:31 得分 0
怎么没结贴呢？
点管理后，输入密码就可以给分解贴啊Top
