Question

哈夫曼树的一些问题

我的程序有些错误，而且错误都是一个类的，不知道怎么修改，请高手帮忙看看，有追加，只要帮我解决问题了，追加50-100吧

问题太长了，所以只好这样了http://hi.baidu.com/%B5%FB%C6%C6%D1%E6%B3%BA/blog/item/bf294038d8cbd423b9998f41.html

Answer 1

//这是我以前做的，附带对字母的编码译码，你可以参考参考

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct htnode
{
int ww,parent,llink,rlink;
char cc,buffer[20]; //cc用来存放字母，buffer用来存放编码字符
}datatype;

struct httree
{
int m;
datatype * ht;
};
typedef struct httree * phttree;

phttree creatht(int m,char * n,int * w)
{
phttree pht;
int x1,x2,m1,m2;
pht=(phttree)malloc(sizeof(struct httree));
if(pht==NULL)
{
printf("申请空间失败！！\n");
return pht;
}
pht->m=m;
pht->ht=(datatype *)malloc(sizeof(datatype)*(2*m-1));
for(int i=0;i<2*m-1;i++)
{
pht->ht[i].llink=-1;
pht->ht[i].rlink=-1;
pht->ht[i].parent=-1;
if(i<m)
{
pht->ht[i].ww=w[i];
pht->ht[i].cc=n[i];
}
else
{
pht->ht[i].ww=-1;
pht->ht[i].cc='^';
}
}
for(i=0;i<m-1;i++)
{
m1=1000000; //有可能溢出
m2=m1;
x1=-1;x2=-1;
for(int j=0;j<m+i;j++)
{
if(pht->ht[j].ww<m1 && pht->ht[j].parent==-1) //寻找最小的数
{
m2=m1;
x2=x1;
m1=pht->ht[j].ww;
x1=j;
}
else if(pht->ht[j].ww<m2 && pht->ht[j].parent==-1) //寻找次小的数
{
m2=pht->ht[j].ww;
x2=j;
}
}
pht->ht[x1].parent=m+i; //构造内部结点
pht->ht[x2].parent=m+i;
pht->ht[m+i].ww=m1+m2;
pht->ht[m+i].llink=x1;
pht->ht[m+i].rlink=x2;
}
return pht;
}

void bianma(phttree pht,FILE *f) //哈夫曼树编码
{
int p,w;
for(int i=0;i<pht->m;i++)
{
int x=1,y=0;
char bm[20];
p=pht->ht[i].parent; //取其父结点
w=i; //取本次循环的数组下标
printf("%c: ",pht->ht[i].cc);
fprintf(f,"%c: ",pht->ht[i].cc);
for(int j=0;j<20;j++) //令字符数组全为空
{
pht->ht[i].buffer[j]='\0'; //令哈夫曼编码数组所有元素为结束符，否则会出错
bm[j]=' '; //令bm数组所有元素为空字符，以便用来判断
}
bm[19]='\0'; //令bm数组最后一个元素为结束符，否则会出错
while(p!=-1) //当前结点为树根的时候停止循环
{
if(pht->ht[p].llink==w) //如果其左孩子为当前数组下标，则令编码为0
{
bm[19-x]='0';
}
else if(pht->ht[p].rlink==w) //如果其右孩子为当前数组下标，则令编码为1
{
bm[19-x]='1';
}
x+=1;
w=p; //转换数组下标
p=pht->ht[p].parent; //向上取父结点
}
for(j=0;j<20;j++) //输出字符数组的元素
{
if(bm[j]!=' ' && bm[j]!='\0')
{
pht->ht[i].buffer[y]=bm[j]; //如果bm元素不为空字符，则赋值给哈夫曼编码数组
printf("%c",pht->ht[i].buffer[y++]);
}
}
fprintf(f,"%s",pht->ht[i].buffer);
y=0;
printf("\n");
fputc('\n',f);
}
}

void main()
{
int m=27,r,i,j,k=0,l;
char c[500],e[20];
char a[]=" ";
FILE * f;

/////////////// 初始化哈夫曼树 //////////////////////////////////////////

char n[27]={' ','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'};

int w[27]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};
for(j=0;j<20;j++) //初始化数组
e[j]='\0'; //令e数组的所有元素都为结束符，以便与哈夫曼编码比较
f=fopen("data.txt","wr"); //打开文件
if( f==NULL)
{
printf("文件打开失败！\n");
exit(1);
}
phttree tree=creatht(m,n,w); //创建哈夫曼树

////////////// 打印哈夫曼树 ///////////////////////////////////////////
fprintf(f,"\t%s\t%s\t%s\t%s\t%s\n","字符","频度","父结点","左孩子","右孩子");
printf("\t字符\t频度\t父结点\t左孩子\t右孩子\n");
for(i=0;i<(m*2-1);i++)
{
printf("%d\t%c\t%d\t%d\t%d\t%d\n",i,tree->ht[i].cc,tree->ht[i].ww,
tree->ht[i].parent,tree->ht[i].llink,tree->ht[i].rlink);
fprintf(f,"%d\t%c\t%d\t%d\t%d\t%d\n",i,tree->ht[i].cc,tree->ht[i].ww,
tree->ht[i].parent,tree->ht[i].llink,tree->ht[i].rlink);
}
///////////// 打印哈夫曼编码 ////////////////////////////////////////////

printf("\n此哈夫曼编码为：\n");
fprintf(f,"%s","\n此哈夫曼编码为：\n");
bianma(tree,f);

//////////// 对字符串编码 /////////////////////////////////////////////////
printf("\n请输入要编码的字符串(以回车键结束输入):");
fprintf(f,"%s","\n请输入要编码的字符串(以回车键结束输入):");

gets(c); //获取字符串
r=strlen(c); //获取字符串长度
fprintf(f,"%s",c);
printf("\n对应字符串的编码为：");
fprintf(f,"\n\n%s","对应字符串的编码为：");

for(i=0;i<r;i++) //用循环将字符编码
{
for(j=0;j<m;j++) //从哈夫曼树中用循环寻找对应字符
{
if(c[i]==tree->ht[j].cc) //找到对应字符，然后编码
{
printf("%s",tree->ht[j].buffer);
fprintf(f,"%s",tree->ht[j].buffer);
break;
}
}
}
printf("\n");
fputc('\n',f);

/////////////// 对编码进行译码 //////////////////////////////////////////////////////

printf("\n请输入要译码的编码：");
fprintf(f,"\n%s","请输入要译码的编码：");

gets(c); //获取字符串
fprintf(f,"%s",c);
printf("\n对应编码的字符串为：");
fprintf(f,"\n\n%s","对应编码的字符串为：");
r=strlen(c); //获取字符串长度

for(i=0;i<r;i++)
{
e[k++]=c[i]; //将第i个编码字符赋值给用来比较的数组

for(j=0;j<tree->m;j++) //循环搜索哈夫曼编码
{
if(strcmp(e,tree->ht[j].buffer)==0) //判断编码字符串与哈夫曼某个编码是否一样
{
for(l=0;l<20;l++) //重新初始化e数组
{
e[l]='\0'; //令e数组的所有元素都为结束符，以便与哈夫曼编码比较
}
printf("%c",tree->ht[j].cc); //找到符合的编码，然后打印对应的字符
fprintf(f,"%c",tree->ht[j].cc);
k=0; //使K指向e数组的首数组元素，以便重新装载编码字符
break;
}
}
}
printf("\n\n");
fclose(f); //关闭文件,写出数据到文件
}

Answer 2

结构定义错误。