高分求助两道C++数据结构题目，过程请详细点（授之以鱼，不如授之以渔！），谢谢。
1、定权集W={9，5，67，7，89，12，15，19，21}，请构造关于W的一棵哈夫曼树，并求带权路径长度WPL的值。
2、已知关键序列{46，55，13，42，94，5，17，70}，用堆排序由大到小排序，并图示排序过程。
【过程要详细，谢谢。】
我要的是答案和详细解题过程。
我要验证自己写的答案对没有！
会的一下就搞定，懵懵懂懂的就算了、
明晚结束问题谢谢！
W={9，5，67，7，89，12，15，19，21}
首先找两个最小的：5,7求和-->12
然后 12代替5,7 与剩余的进行比较找最小，即{9,12,12,15,19，21,67,89}
找最小的两个，求和：即 9+12-->21
21与剩余的进行比较找最小即{12，15,19,21,21,67,89}
找最小两个：12+15 =27
{19,21,21,27,67,89}---->19+21=40-->{21,27,40,67,89}-->27+21=48---->{40,48,67,89}-->40+48=88--->{67,88,89}-->67+88=155-->{155,89}-->244
244
/\
89 155
/ \
67 88
/ \
40 48
/ \ / \
21 19 21 27
/\ /\
9 12 12 15
/\
5 7
WSL= 5*6+7*6+9*5+12*5+15*5+19*4+21*4+67*2+89*1
第二个太麻烦，不写了。。不为积分
首先找两个最小的：5,7求和-->12
然后 12代替5,7 与剩余的进行比较找最小，即{9,12,12,15,19，21,67,89}
找最小的两个，求和：即 9+12-->21
21与剩余的进行比较找最小即{12，15,19,21,21,67,89}
找最小两个：12+15 =27
{19,21,21,27,67,89}---->19+21=40-->{21,27,40,67,89}-->27+21=48---->{40,48,67,89}-->40+48=88--->{67,88,89}-->67+88=155-->{155,89}-->244
244
/\
89 155
/ \
67 88
/ \
40 48
/ \ / \
21 19 21 27
/\ /\
9 12 12 15
/\
5 7
WSL= 5*6+7*6+9*5+12*5+15*5+19*4+21*4+67*2+89*1
第二个太麻烦，不写了。。不为积分
温馨提示：内容为网友见解，仅供参考
第1个回答 2011-05-07
能看的就行 完整最重要 谢谢 谢谢 我的全吧！归佛 已发至你邮箱！注意查收！ 记得采纳！ 已经发给你了追问
发哪了，我还没留邮箱呢！
有得就在这里公布吧！大家一起都能看。
有图的自己贴上来。
第2个回答 2011-05-09
堆排序我们还没有学到
huffman我搞定了 不求分 只求交流
#include<stdio.h>
#include<stdlib.h>
typedef struct{
int weight,parent,lchild,rchild;
}HTNode,*huffmantree;
void Select(huffmantree HT,int m,int *s1,int *s2);
void HuffmaCoding(huffmantree HT,int *w,int n){
int m=2*n-1,i,s1=0,s2=0;
huffmantree p;
for(p=HT,i=1;i<=n;++i,++w){
p[i].weight=*w;
p[i].parent=0;
p[i].lchild=0;
p[i].rchild=0;
}
for(;i<=m;++i){
p[i].weight=0;
p[i].parent=0;
p[i].lchild=0;
p[i].rchild=0;
}
for(i=n+1;i<=m;++i){
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;
}
}
void Select(huffmantree HT,int m,int *s1,int *s2){
int i,j=1;
huffmantree temp,*p;
p=(huffmantree *)malloc((m+1)*sizeof(huffmantree));
for(i=1;i<=m;i++){
if(HT[i].parent==0){
p[j]=&HT[i];
j++;
}
}
m=j-1;
for(i=1;i<=m;++i)
for(j=1;j<=m-i;++j){
if(p[j]->weight>p[j+1]->weight){
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
}
*s1=p[1]-HT;
*s2=p[2]-HT;
}
int Distance(huffmantree HT,int m){
int i=0;
while(HT[m].parent!=0){
m=HT[m].parent;
++i;
}
return i;
}
int main(){
int n=8,w[8]={5,29,7,8,14,23,3,11},m=2*n,i,total=0;
huffmantree HT,p;
HT=(huffmantree)malloc(m*sizeof(HTNode));
HuffmaCoding(HT,w,n);
p=HT+1;
for(i=1;i<m;p++,i++){
printf("%5d%5d%5d%5d\n",p->weight,p->parent,p->lchild,p->rchild);
}
for(i=1;i<=n;i++){
total+=HT[i].weight*Distance(HT,i);
}
printf("WPL=%d",total);
}
带权路径 和存储的形态
huffman我搞定了 不求分 只求交流
#include<stdio.h>
#include<stdlib.h>
typedef struct{
int weight,parent,lchild,rchild;
}HTNode,*huffmantree;
void Select(huffmantree HT,int m,int *s1,int *s2);
void HuffmaCoding(huffmantree HT,int *w,int n){
int m=2*n-1,i,s1=0,s2=0;
huffmantree p;
for(p=HT,i=1;i<=n;++i,++w){
p[i].weight=*w;
p[i].parent=0;
p[i].lchild=0;
p[i].rchild=0;
}
for(;i<=m;++i){
p[i].weight=0;
p[i].parent=0;
p[i].lchild=0;
p[i].rchild=0;
}
for(i=n+1;i<=m;++i){
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;
}
}
void Select(huffmantree HT,int m,int *s1,int *s2){
int i,j=1;
huffmantree temp,*p;
p=(huffmantree *)malloc((m+1)*sizeof(huffmantree));
for(i=1;i<=m;i++){
if(HT[i].parent==0){
p[j]=&HT[i];
j++;
}
}
m=j-1;
for(i=1;i<=m;++i)
for(j=1;j<=m-i;++j){
if(p[j]->weight>p[j+1]->weight){
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
}
*s1=p[1]-HT;
*s2=p[2]-HT;
}
int Distance(huffmantree HT,int m){
int i=0;
while(HT[m].parent!=0){
m=HT[m].parent;
++i;
}
return i;
}
int main(){
int n=8,w[8]={5,29,7,8,14,23,3,11},m=2*n,i,total=0;
huffmantree HT,p;
HT=(huffmantree)malloc(m*sizeof(HTNode));
HuffmaCoding(HT,w,n);
p=HT+1;
for(i=1;i<m;p++,i++){
printf("%5d%5d%5d%5d\n",p->weight,p->parent,p->lchild,p->rchild);
}
for(i=1;i<=n;i++){
total+=HT[i].weight*Distance(HT,i);
}
printf("WPL=%d",total);
}
带权路径 和存储的形态
相似回答
