数据结构关于哈夫曼树的问题？ 数据结构哈夫曼编码
【数据结构】关于画哈夫曼树的问题
不一定，但wpl相同
你的与书上的方法是不同的吧
相同的方法是唯一的
只要wpl最小就是最优的吧
一般我们总是取当前根节点最小的两棵树合并的
2 3 4 7 8 9
第一次
二三合并为5
5 4 5 7 8 9
2 3
第二次
4 5 合并为9
9 7 8 9
5 4
2 3
第三次
7 8合并为 15
15 9 9
7 8 5 4
2 3
第四次
9 9合并
18 15
9 9 7 8
4 5
2 3
第五次
18 15 合并
31
18 15
9 9
4 5
2 3
吧
数据结构的问题,求一个构造哈夫曼树的算法
void haffmantree(int weight[],int n,struct haffnode hafftree[],char data[])
/*建立叶结点个数为n，权值数组为weight[]的哈夫曼树*/
{int i,j,m1,m2,x1,x2;
/*哈夫曼树hafftree[]初始化，n个叶结点共有2n-1个结点*/
for(i=0;i<2*n-1;i++)
{if(i<n) {hafftree[i].data=data[i];
hafftree[i].weight=weight[i]; /*叶结点*/
}
else {hafftree[i].weight=0; /*非叶结点*/
hafftree[i].data='\0';
}
hafftree[i].parent=0; /*初始化没有双亲结点*/
hafftree[i].flag=0;
hafftree[i].leftchild=-1;
hafftree[i].rightchild=-1;
}
for(i=0;i<n-1;i++) /*构造哈夫曼树n-1个非叶结点*/
{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+i;
hafftree[x2].parent=n+i;
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;
}
}
void haffmancode(struct haffnode hafftree[],int n,struct haffcode haffcode[])
{/*由n个结点的哈夫曼树hafftree[]构成的哈夫曼编码haffcode[]*/
int i,j,child,parent;
struct haffcode newcode;
struct haffcode *cd;
cd=&newcode;
for(i=0;i<n;i++) /*求n个结点的哈夫曼编码*/
{cd->start=MAXBIT-1; /*不等长编码的最后一位是n-1*/
cd->weight=hafftree[i].weight;
cd->data=hafftree[i].data; /*取得编码对应值的字符*/
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(j=cd->start+1;j<MAXBIT;j++) /*保存每个叶结点的编码和等长编码的起始位*/
haffcode[i].bit[j]=cd->bit[j];
haffcode[i].data=cd->data;
haffcode[i].start=cd->start;
haffcode[i].weight=cd->weight;
}
}
用c语言解决数据结构哈夫曼树问题
#include "string.h"
#include "stdio.h"
#define MAXVALUE 1000 /*定义最大权值*/
#define MAXLEAF 30 /*定义哈夫曼树叶结点个数*/
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 30 /*定义哈夫曼编码的最大长度*/
typedef struct
{ int bit[MAXBIT];
int start;
} HCODETYPE;
typedef struct
{ int weight;
int parent;
int lchild;
int rchild;
} HNODETYPE;
char *getcode1(char *s1,char *s2,char *s3) /*首先去掉电文中的空格*/
{ char temp[128]="",*p,*q;
p=s1;
while ((q=strstr(p,s2))!=NULL)
{ *q='\0';
strcat(temp,p);
strcat(temp,s3);
p=q+strlen(s2); }
strcat(temp,p);
strcpy(s1,temp);
return s1;
}
/*再去掉重复出现的字符（即压缩电文），提取哈夫曼树叶结点*/
char * getcode (char *s1)
{ char s2[26],s5[26];
char temp[200]="",*p,*q,*r,*s3="";
int m,e,n=0;
m=strlen(s1);
while(m>0)
{ p=s1;
s2[0]=s1[0];
s2[1]='\0';
r=s2;
e=0;
while((q=strstr(p,r))!=NULL)
{ *q='\0';
strcat(temp,p);
strcat(temp,s3);
p=q+strlen(s2);
e++; }
m-=e;
strcat(temp,p);
strcpy(s1,temp);
s5[n]=s2[0];
n++;
strcpy(temp,"");
}
s5[n]='\0';
strcpy(s1,s5);
printf(" 压缩后的电文（即叶结点）: %s\n",s1);
return s1;
}
HNODETYPE huffmantree(char *s2,char s3[])
{ HNODETYPE huffnode[MAXNODE];
HCODETYPE huffcode[MAXLEAF],cd;
int sum,i,j,n1,n2,x1,x2,p,k,c;
char s1[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m',
'n','o','p','q','r','s','t','u','v','w','x','y','z'};
char s5[MAXLEAF];
int ww[26]={0},n=0;
strcpy( s5,s2);
sum=strlen(s2);
for(i=0;i<26;i++) /*统计所有字符出现的频度*/
for(j=0;j<sum;j++)
if(s2[j]==s1[i]) ww[i]++;
n=strlen(s3);
for (i=0;i<2*n-1;i++)
{ huffnode[i].weight=0;
huffnode[i].parent=-1;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1; }
for(i=0;i<n;i++) /*分配给各叶结点权值*/
for(j=0;j<26;j++)
if (s3[i]==s1[j]) huffnode[i].weight=ww[j];
for (i=0;i<n-1;i++) /*构造哈夫曼树*/
{ n1=n2=MAXVALUE;
x1=x2=0;
for(j=0;j<n+i;j++)
{ if (huffnode[j].parent==-1 && huffnode[j].weight<n1)
{ n2=n1;
x2=x1;
n1=huffnode[j].weight;
x1=j; }
else
if (huffnode[j].parent==-1 && huffnode[j].weight<n2)
{ n2=huffnode[j].weight; x2=j;}
}
huffnode[x1].parent=n+i;
huffnode[x2].parent=n+i;
huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;
huffnode[n+i].lchild=x1;
huffnode[n+i].rchild=x2;
}
for(i=0;i<n;i++) /*求每个叶结点的哈夫曼编码*/
{ cd.start=n-1;
c=i;
p=huffnode[c].parent;
while (p!=-1)
{ if (huffnode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=huffnode[c].parent;
}
for (j=cd.start+1;j<n;j++)
huffcode[i].bit[j]=cd.bit[j];
huffcode[i].start=cd.start;
}
printf(" 各叶结点对应哈夫曼编码 : ");/*输出每个叶结点的哈夫曼编码*/
for(i=0;i<n;i++)
{ for(j=huffcode[i].start+1;j<n;j++)
printf("%d",huffcode[i].bit[j]);
printf(" ");}
printf("\n 电文的全部哈夫曼编码 : ");/*输出电文的全部哈夫曼编码*/
for(k=0;k<sum;k++)
for(i=0;i<n;i++)
if(s2[k]==s3[i])
{ for(j=huffcode[i].start+1;j<n;j++)
printf("%d",huffcode[i].bit[j]);
printf(" "); }
printf("\n");
}
main()
{
char s1[MAXLEAF],s2[MAXLEAF];
printf("\n 请输入电文 : ");
gets(s1);
strcpy(s2,getcode1(s1," ",""));
huffmantree(s1,getcode(s2));
}
数据结构中赫夫曼数的构造问题
一般是以序列的前两个最小数为所选（也就是7和紧跟在它后面的那个8）