关于哈夫曼编码的问题！急啊！！！

哈夫曼编码问题~~~高手进。。急急急急~

#include
using namespace std;
struct HTNode
{
int weight; //权值
int parent; //父节点
int lchild; //左孩子节点
int rchild; //右孩子节点
};
typedef HTNode *HuffmanTree;
typedef char **HuffmanCode;
void select(HuffmanTree HT,int n,int &s1,int &s2)
{
//选择两个最小值，将他们的位序输出到s1,s2
int m=0,k=0;
for(k=1;k<=n;++k) //得到第一个父节点为零的节点
{
if(0==HT[k].parent)
{
m=HT[k].weight;
s1=k;
break;
}
}
for(;k<=n;++k) //得到最小值
{
if(0==HT[k].parent && HT[k].weight<m)
{
m=HT[k].weight;
s1=k;
}
}
for(k=1;k<=n;++k) //得到第一个父节点为零的节点
{
if(k!=s1 && 0==HT[k].parent)
{
m=HT[k].weight;
s2=k;
break;
}
}
for(;k<=n;++k) //求得次小元
{
if(0==HT[k].parent && k!=s1 && HT[k].weight<m)
{
m=HT[k].weight;
s2=k;
}
}

}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w,int n)
{
//w存放n个字符的权值（均>0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC
if(n<=1)
{
exit(0);
}
int m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用
HuffmanTree p;
int i;
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}

for(;i<=m;++i,++p)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}

int s1=0,s2=0;
for(i=n+1;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].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}


//从叶子到跟逆向求每个字符的赫夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
//分配n个字符编码的头指针向量
char * cd;
cd=(char *)malloc(n*sizeof(char));
//分配求编码的工作空间
cd[n-1]='\0'; //编码结束符
int start;
int c=0,f=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); //释放工作空间
}

void main()
{
int *w; //用于存储序列权值
int n=0,i=0; //存储字符序列权值的个数
cout<<"请输入字符序列权值的个数：";
cin>>n;
w=(int *)malloc(n * sizeof(int));
cout<<"请输入字符序列的权值：";
for(i=0;i<n;++i) //输入字符序列权值
{
cout<<endl<<i+1<<" ";
cin>>w[i];
}
cout<<endl<<endl<<endl;
HuffmanTree HT; //存储赫夫曼树
HuffmanCode HC; //存储编码表
HuffmanCoding(HT,HC,w,n); //构建赫夫曼树，得到赫夫曼编码
cout<<"字符序号"<<""<<"字符权值"<<""<<"赫夫曼编码"<<endl;
for(i=1;i<=n;++i) //输出赫夫曼编码
{
cout<<i<<""<<w[i-1]<<""<<HC[i]<<endl<<endl;
}
cout<<endl;
}

我自己编的,已经在在线平台上测试通过,可以输出需要的字符总个数个数,你稍微改一下即可.实现代码,c++,运行环境:VC 6.0/Dev
------------------------------------------------------------

#include
using namespace std;
using std::fixed;
#include
using std::setprecision;

#include
#include
#include
#include
struct node
{
int times;
struct node *child1;
struct node *child2;

friend bool operator<( const node &a,const node &b )
{
return ( a.times < b.times );
}
friend bool operator>( const node &a1,const node &b1 )
{
return ( a1.times > b1.times );
}
};



int main()
{
priority_queue,greater > que;

char a;
char string1[4] = {'0'};
int letter[28] = {0};
bool judge = 1;

while( judge )
{
int count = 0;
int i,j,k;
memset( letter,0,sizeof(letter) );
while( que.size() > 0 )
que.pop();

while( ( a = cin.get() ) != '
' )
{

if( count <= 3 )
string1[count] = a;

count++;

if( a == '_' )
letter[27]++;
if( a != '_' )
{
k = a-'A'+1;
letter[k]++;
}
}
if( count == 3 && string1[0] == 'E' && string1[1] == 'N' && string1[2] == 'D' )
{
judge = 0;
break;
}

int count1 = 0;
for( i = 1;i <= 27;i++ )
{
if( letter[i] > 0 )
{
node p;
p.times = letter[i];
p.child1 = NULL;
p.child2 = NULL;
que.push(p);
count1 += letter[i];

}
}
if( que.size() == 1 )
{
cout<<count1*8<<' '<<count1<<" 8.0"<<endl;
continue;
}

int total = 0;
node *t1,*t2,*t3;
while( que.size() >= 2 )
{
t1 = new node;
t2 = new node;
*t1 = que.top();
que.pop();

*t2 = que.top();
que.pop();

t3 = new node;
t3->times = t1->times + t2->times;
t3->child1 = t1;
t3->child2 = t2;
que.push( *t3 );

total += ( t1->times + t2->times );

}

if( total != 0 )
{
double t = 1.0*8*count/total;
cout<<8*count1<<' '<<total<<' '<<setprecision(1)<<fixed<<t<<endl;

}

}


return 0;

}

先将9个字符串全部编成哈夫曼码
1001000
1000101
1000011
1001000
1010101
1000001
01001110
1011010
1001001

这是二进制的编码 应该是对应十进制的
72
69
67
72
85
65
78
90
73

这么大的数字对应的明显不是字母表，如果没有猜错的话对应当应该是ASCLL码表
这九个数字对应的ASCLL码是：
H
E
C
H
U
A
N
Z
I

连起来应该就是答案了：HECHUANZI

虽然我不知道什么意思 但是应该是一个人名 HE CHUAN ZI
这什么破密码 绕这么多弯子 40分是不是太少了一点 出于人道主义还是加点分吧

1111

---

乌兰察布市18732151160： 哈夫曼编码问题请教; - ？
顾楠丽智： 两个最小的编码没有左右之分.是不同,哈夫曼编码不是唯一的,但是它们的WPL(带权路径长度)都是一样的.如果,最下面有两个二叉树,那么也不用考虑左右的问题,你只将最下面两个二叉树当作两个节点就可以了.记住:哈夫曼编码不...

乌兰察布市18732151160： 求解,关于数据结构的哈夫曼编码的问题 - ？
顾楠丽智： 方案一应该指的就是下面那个图了.下面那个图是一棵二进制的哈夫曼树,其中因为是二进制编码,所以使用的是0\1的边.那么对于每一个叶子节点来说,从根节点到叶子节点走过的边就是这个数字的编码.那么举一个例子,比如频数=2的也就是最...

乌兰察布市18732151160： 求助有关哈夫曼树编码的问题?急! - ？
顾楠丽智： 我去年数据结构课程设计做的就是这个,具体什么意思也忘得差不多了 反正做了好多天的 把这段代码复制给你void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC, LNode &L,int n){ //构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC ...

乌兰察布市18732151160： 一道关于哈夫曼编码的题该怎么做? - ？
顾楠丽智： 首先,亲请记住,无论是数学题政治题C语言,任何情况下都不可以选“以上都不是”.哈夫曼编码是非常经典的一种变长编码方案.我偷个懒,方法描述如下:首先,将符号按照概率由大到小排队.编码时,从最小概率的两个符号开始,可选...

乌兰察布市18732151160： 哈夫曼编码是怎么回事啊? - ？
顾楠丽智： 哈夫曼编码是一种编码方式,是可变字长编码(VLC)的一种.以哈夫曼树—即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩. 在计算机信息处理中,“哈夫曼编码”是一种一致性编码法(又称＂熵编码法＂),用于数据的...

乌兰察布市18732151160： 数据结构题目,关于哈弗曼编码,用C语言来做(非常急的,谢谢了) - ？
顾楠丽智： void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) { // w存放n个字符的权值(均>0),构造哈夫曼树HT, // 并求出n个字符的哈夫曼编码HC int i, j, m, s1,s2; char *cd; int p; int cdlen; if (n m = 2 * n - 1; HT = (HuffmanTree)...

乌兰察布市18732151160： 哈夫曼编码是一种可变长,信源中某符号发生概率越低,其码长越 - --怎么? - ？
顾楠丽智： 哈夫曼编码的原理是:一个符号发生频率越高,其码长越短,反之则越长.很好理解:要使总长最短,出现越多次的符号的编码就要越短.打个不恰当的比方,现在用的最多的几个汉字“个”“的”“们”“什”“么”什么的笔画不是都很少吗?这就是文字演变的规律,也就是哈夫曼编码的原理.

乌兰察布市18732151160： 急求 多媒体技术中哈夫曼编码的码长和熵的计算公式,大学阶段的.不要C里面的,就是要两个公式. 谢谢了 - ？
顾楠丽智： 展开全部1:码长是否是平均码长?如果是,码长=(所有种类字符累加(字符出现的次数*该字符哈夫曼编码是的长度))/所有字符的个数 例:字符串aabbb a编码为10011 -----5位 b编码为010011 -------6位 码长=(2*5+3*6)/5 (分母5代表aabbb的长度为5)2:信息熵:信息熵Eta=累加(Pi*log2(1/Pi))(i从1累加到n,Pi表示对应第i个字符在字符串中出现的概率,如字符“a”在长度为1000的字符串中出现6次,为第一个字符,则P1=6/1000)

乌兰察布市18732151160： 哈夫曼树每个字符可以有不同的编码方式,但是每个字符的编码长度是一样的吗? - ？
顾楠丽智： 主可以去看看最优二叉树的编码问题. 1、哈夫曼编码 在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符.例如,需传送的报文为“AFTER DATA EAR ARE ART AREA”,这里用到的字符集为“A,E,R,T,...

乌兰察布市18732151160： 有关哈夫曼编码的问题!(请高手帮帮忙,谢谢了哦!)？
顾楠丽智： 提问者只给了7个字母的权值,故,按7个字母求解. 由于各人不同,所构造的哈夫曼编码可能不同,先给出一种编码形式 a 0101 b 10 c 01000 d 00 e 01001 f 11 g 011 二进制表示易知. 与二进制比,此方法在保证准确的情况下,比较节省时间空间.