带权路径长度怎么求？
# include <stdio.h>
#define n 6
#define m 2*n-1
typedef struct{
float weight;
int parent,lchild,rchild;
}hufmtree;
hufmtree tree[m];
void Hufmtree()
{
int i,j,p1,p2;
float small1,small2,f,maxval=10000.00;
int WPL=0;
printf("\n\t\t请输入%d棵树(叶子)的权值\nplease:\n\n",n);
for (i=0;i<m;i++)
{ tree[i].parent=0;
tree[i].lchild=0;
tree[i].rchild=0;
tree[i].weight=0.0;
}
for (i=0;i<n;i++)
{ printf("tree[%d].weight=",i);
scanf("%f",&f);
tree[i].weight=f;
}
for (i=n;i<m;i++)
{ p1=0; p2=0;
small1=maxval; small2=maxval;
for (j=0;j<=i-1;j++)
if (tree[j].parent==0)
if (tree[j].weight<small1)
{ small1= tree[j].weight;
p2=p1; p1=j;
}
else
if (tree[j].weight<small2)
{ small2=tree[j].weight;
p2=j;
}
tree[p1].parent=i+1;
tree[p2].parent=i+1;
tree[i].lchild=p1+1;
tree[i].rchild=p2+1;
tree[i].weight=tree[p1].weight+ tree[p2].weight;
}printf("\n");
for(i=n;i<m;i++)
{ printf("tree[%d].weight=%.2f\n",i,tree[i].weight);}
}
void main()
{
Hufmtree();
}
[解决办法]
自己去找灵感！
- C/C++ code
/*------------------------------------------------------ 假设字符串序列{A,B,C,D},对应的权重为{1,3,6,9}.设计一个 哈弗曼树，并输出对应的哈弗曼编码。--------------------*/#include<stdio.h>#include<string.h>#include<malloc.h>typedef struct { int weight; int parent,lchild,rchild;}HTNode,*Huffman;Huffman HuffmanTree;char **HuffmanCode;//用于存放每个字符的哈弗曼编码int MIN; //用于存放最小的权值，因为我们要将权值最小的节点放在哈夫曼树的最右下端 //其编码值为1，从而和其他节点相区分void InitHuffmanTree(int *hw,int n);void CtreateHuffmanTree(int *hw,int n,int max);void SelectMin(int *hw,int n,int *k);void GetHuffmanCode(int n);void Reverse(char *str);int main(){ int m,n,i; int HuffmanWeight[]={1,3,6,9}; char HuffmanString[]="ABCD"; n=strlen(HuffmanString); m=2*n-1;//因为有n个叶子节点，则需要建立的哈夫曼树总节点个数为2*n-1个 HuffmanCode=(char **)malloc(n*sizeof(char *)); //分配空间 HuffmanTree=(Huffman)malloc(m*sizeof(HTNode)); InitHuffmanTree(HuffmanWeight,n); CtreateHuffmanTree(HuffmanWeight,n,m); GetHuffmanCode(n); for(i=0;i<n;i++) { printf("权值为%d的哈弗曼编码为:%s\n",HuffmanTree[i].weight,HuffmanCode[i]); } return 0; }void InitHuffmanTree(int *hw,int n){ int i,j; for(i=0,j=0;i<n&&j<n;i++,j++) //前n个单元用于存放叶子节点即需要编码的节点 { HuffmanTree[i].weight=hw[j]; HuffmanTree[i].parent=0; HuffmanTree[i].lchild=0; HuffmanTree[i].rchild=0; } HuffmanTree[2*n-2].parent=-1; //使根节点的父节点为-1 }void CtreateHuffmanTree(int *hw,int n,int max){ int i=0,j,k; SelectMin(hw,n,&k); HuffmanTree[k].parent=n; HuffmanTree[n].lchild=k; HuffmanTree[n].weight+=HuffmanTree[k].weight; MIN=HuffmanTree[k].weight; //将最小的权值存放于MIN SelectMin(hw,n,&k); HuffmanTree[k].parent=n; HuffmanTree[n].rchild=k; HuffmanTree[n].weight+=HuffmanTree[k].weight; for(i=2,j=n+1;i<n&&j<max;i++,j++) { SelectMin(hw,n,&k); HuffmanTree[k].parent=HuffmanTree[j-1].parent=j; HuffmanTree[j].lchild=k; HuffmanTree[j].rchild=j-1; HuffmanTree[j].weight=HuffmanTree[k].weight+HuffmanTree[j-1].weight; }}void SelectMin(int *hw,int n,int *k) /*筛选出权值最小的节点，并将其下标存于k*/{ int i; int min=1000; /*这里为了方便先将min初始化为一个较大的数*/ for(i=0;i<n;i++) { if(HuffmanTree[i].weight<min&&HuffmanTree[i].parent==0) { min=HuffmanTree[i].weight; *k=i; } } HuffmanTree[*k].parent=1; /*这里将其parent赋值为1表示已被筛选过了*/}void GetHuffmanCode(int n){ int p=0,i=0,j; char buffer[10]={0}; while(p<n) { j=p; while(HuffmanTree[j].parent!=-1) { if(j>=n||HuffmanTree[j].weight==MIN) buffer[i++]='1'; //右节点值为1 else buffer[i++]='0'; //左节点值为0 j=HuffmanTree[j].parent; } buffer[i]='\0'; Reverse(buffer); //先将字符串翻转 HuffmanCode[p]=(char*)malloc(sizeof(char)*10); strcpy(HuffmanCode[p],buffer); i=0; /*初始化缓冲区*/ p++; }}void Reverse(char *str){ int i,j; char c; for(i=0,j=strlen(str)-1;i<j;i++,j--) { c=str[i]; str[i]=str[j]; str[j]=c; }}/*权值为1的哈弗曼编码为:111权值为3的哈弗曼编码为:110权值为6的哈弗曼编码为:10权值为9的哈弗曼编码为:0Press any key to continue*/