[求助]Huffman树周4就要交了急啊！！ - 数据结构与算法

问题点数：0 回复次数：11

[求助]Huffman树周4就要交了急啊！！

设字符集为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
频度：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
字符：空格
频度：186

要求：哈夫曼树的建立求编码器的实现
具体内容：先生成一棵哈夫蔓树再打印各字符对应的哈夫曼编码

建树的权植大小左小右大，若相等时，则先后次序分左右

哪位高手帮帮忙啊最好要有主函数的啊谢谢啊等救命的啊！

搜索更多相关主题的帖子: Huffman　哈夫曼编码　频度　字符　

第 2 楼

得分:0

马甲

日出东方，唯我不败！做任何东西都是耐得住寂寞,任何一个行业要有十年以上的积累才能成为专家

第 3 楼

得分:0

又是马甲？？

奋斗改变一切！！

第 4 楼

得分:0

马甲？？我有点糊涂了
Huffman树么

，以前牛虻写过一个，我可是记得很亲楚（

骗了我1000大洋啊）
唉，置顶的那个索引帖子

[分享]数据结构版面经典帖子集合(长期更新, 新人必看!)
明明写了新人必看了，连颜色也漂成紫色了，为什么没人去看呢？我可是花了好长时间才整理出来的啊。
里面有Huffman树的完整代码连接。

我的征途是星辰大海

第 5 楼

得分:0

#include <stdio.h>

#define max 500//定义存储的最大结点数

typedef struct //定义结点

               char data;//结点值

               int weight;//权重

               int parent;//父结点

               int left;//左孩子结点

               int right;//右孩子结点

}huffnode;

typedef struct

               char cd[max];

               int start;

}huffcode;

char elem[1000];

char input[1000];

int weight[1000]={0};

int m=0;

int find_char(char a[],char c,int n)//在数组中查找某一个元素，返回其位置

               int i;

               for(i=0;i<=n;i++)

                               if(a[i]==c) return i;

               return -1;

int get_elem_weight()

//从输入中得到除空格和回车之外的所有字符类型及其权值

               int i,n=-1;

               for(i=0;i<100;i++)

    elem[i]=' ';

               char c;

               while(1)

                               c=getchar();

                               input[m++]=c;

                               if(c==10) break;

                               else if(c!=' ')

                                              if(find_char(elem,c,n)==-1)

                                              {   n++;

                                                             elem[n]=c;

                                                             weight[n]=1;

                                              else weight[find_char(elem,c,n)]+=1;

               printf("除空格和回车之外各字符的出现频率如下：\n");

//打印字符极其权值

               for(i=0;i<=n;i++)

                               printf("%c %d",elem[i],weight[i]);

                               printf("\n");

               return n+1;

main()

               huffnode ht[2*max];

               huffcode htd[max],d;

               int i,k,f,l,r,n,c,m1,m2,j;

               printf("请输入一个字符串，以回车结束\n");

               n=get_elem_weight();

               for(i=1;i<=n;i++)

                               ht[i].data =elem[i-1];

                               ht[i].weight =weight[i-1];

               for(i=1;i<=2*n-1;i++)

                               ht[i].parent =ht[i].left =ht[i].right =0;//叶结点初始化

               for(i=n+1;i<=2*n-1;i++)

                               m1=m2=32767;

                               l=r=0;

                               for(k=1;k<=i-1;k++)

                                              if(ht[k].parent ==0)

                                              //寻找当前结点中权值最小的两个结点

                                                             if(ht[k].weight <m1)

                                                                            m2=m1;

                                                                            r=l;

                                                                             m1=ht[k].weight ;

                                                                            l=k;

                                                             else if(ht[k].weight <m2)

                                                                            m2=ht[k].weight ;

                                                                            r=k;

                                                             ht[l].parent =i;//建立父结点信息

                                                             ht[r].parent =i;

                                                             ht[i].weight =ht[l].weight +ht[r].weight ;

                                                             ht[i].left =l;

                                                             ht[i].right =r;

               for(i=1;i<=n;i++)//由建立的结点生成Huffman编码

                               d.start =n+1;

                               c=i;

                               f=ht[i].parent ;

                               while(f!=0)

                                              if(ht[f].left ==c)

                                                             d.cd[--d.start ]='0';

                                              else

                                                             d.cd [--d.start ]='1';

                                              c=f;

                                              f=ht[f].parent ;

                               htd[i]=d;

               printf("输出编码\n");

               for(i=1;i<=n;i++)

                               printf("%c:",ht[i].data );

                               for(k=htd[i].start ;k<=n;k++)

                                              printf("%c",htd[i].cd[k]);

                               printf("\n");

               printf("你所输入的字符串为\n");

               for(i=0;i<m-1;i++) printf("%c",input[i]);

               printf("\n");

               printf("经过编码之后\n");//打印编码后结果

               for(i=0;i<m-1;i++)

                  if(input[i]!=' ')

                                 for(k=1;k<=n;k++)

                                                if(ht[k].data ==input[i]) break;

                                                for(j=htd[k].start ;j<=n;j++)

                                                                printf("%c",htd[k].cd [j]);

                  else printf("%c",input[i]);

    printf("\n");

第 6 楼

得分:0

好象忘了换行了，不好意思啊
#include <stdio.h>
#define max 500//定义存储的最大结点数
typedef struct //定义结点
{
char data;//结点值
int weight;//权重
int parent;//父结点
int left;//左孩子结点
int right;//右孩子结点
}huffnode;
typedef struct
{
char cd[max];
int start;
}huffcode;
char elem[1000];
char input[1000];
int weight[1000]={0};
int m=0;
int find_char(char a[],char c,int n)
//在数组中查找某一个元素，返回其位置
{
int i;
for(i=0;i<=n;i++)
{
if(a[i]==c) return i;
}
return -1;
}
int get_elem_weight()
//从输入中得到除空格和回车之外的所有字符类型及其权值
{
int i,n=-1;
for(i=0;i<100;i++)
elem[i]=' ';
char c;
while(1)
{
c=getchar();
input[m++]=c;
if(c==10) break;
else if(c!=' ')
{
if(find_char(elem,c,n)==-1)
{ n++;
elem[n]=c;
weight[n]=1;
}
else weight[find_char(elem,c,n)]+=1;
}
}
printf("除空格和回车之外各字符的出现频率如下：\n");
//打印字符极其权值
for(i=0;i<=n;i++)
{
printf("%c %d",elem[i],weight[i]);
printf("\n");
}
return n+1;
}
main()
{
huffnode ht[2*max];
huffcode htd[max],d;
int i,k,f,l,r,n,c,m1,m2,j;
printf("请输入一个字符串，以回车结束\n");
n=get_elem_weight();
for(i=1;i<=n;i++)
{
ht[i].data =elem[i-1];
ht[i].weight =weight[i-1];
}
for(i=1;i<=2*n-1;i++)
ht[i].parent =ht[i].left =ht[i].right =0;//叶结点初始化
for(i=n+1;i<=2*n-1;i++)
{
m1=m2=32767;
l=r=0;
for(k=1;k<=i-1;k++)
if(ht[k].parent ==0)
//寻找当前结点中权值最小的两个结点
if(ht[k].weight <m1)
{
m2=m1;
r=l;
m1=ht[k].weight ;
l=k;
}
else if(ht[k].weight <m2)
{
m2=ht[k].weight ;
r=k;
}
ht[l].parent =i;//建立父结点信息
ht[r].parent =i;
ht[i].weight =ht[l].weight +h[r].weight ;
ht[i].left =l;
ht[i].right =r;
}
for(i=1;i<=n;i++)//由建立的结点生成Huffman编码
{
d.start =n+1;
c=i;
f=ht[i].parent ;
while(f!=0)
{
if(ht[f].left ==c)
d.cd[--d.start ]='0';
else
d.cd [--d.start ]='1';
c=f;
f=ht[f].parent ;
}
htd[i]=d;
}
printf("输出编码\n");
for(i=1;i<=n;i++)
{
printf("%c:",ht[i].data );
for(k=htd[i].start ;k<=n;k++)
printf("%c",htd[i].cd[k]);
printf("\n");
}
printf("你所输入的字符串为\n");
for(i=0;i<m-1;i++) printf("%c",input[i]);
printf("\n");
printf("经过编码之后\n");//打印编码后结果
for(i=0;i<m-1;i++)
{
if(input[i]!=' ')
{
for(k=1;k<=n;k++)
if(ht[k].data ==input[i]) break;
for(j=htd[k].start ;j<=n;j++)
printf("%c",htd[k].cd [j]);
}
else printf("%c",input[i]);
}
printf("\n");
}

第 7 楼

得分:0

以下是引用starrysky在2006-5-28 19:37:00的发言：
马甲？？我有点糊涂了
Huffman树么

，以前牛虻写过一个，我可是记得很亲楚（

骗了我1000大洋啊）
唉，置顶的那个索引帖子

对哦..这家伙可没少费心思啊...

我也很佩服你整理的东西..很有用

[此贴子已经被作者于2006-5-29 20:34:35编辑过]

[glow=255,violet,2]闭关修炼ing...[/glow] [FLASH=360,180]http://www./chinaren.swf[/FLASH]

第 8 楼

得分:0

以下是引用墨斗鱼在2006-5-29 11:36:00的发言：

#include <stdio.h>

#define max 500//定义存储的最大结点数

typedef struct //定义结点

               char data;//结点值

               int weight;//权重

               int parent;//父结点

               int left;//左孩子结点

               int right;//右孩子结点

}huffnode;

typedef struct

               char cd[max];

               int start;

}huffcode;

char elem[1000];

char input[1000];

int weight[1000]={0};

int m=0;

int find_char(char a[],char c,int n)//在数组中查找某一个元素，返回其位置

               int i;

               for(i=0;i<=n;i++)

                               if(a[i]==c) return i;

               return -1;

int get_elem_weight()

//从输入中得到除空格和回车之外的所有字符类型及其权值

               int i,n=-1;

               for(i=0;i<100;i++)

    elem[i]=' ';

               char c;

               while(1)

                               c=getchar();

                               input[m++]=c;

                               if(c==10) break;

                               else if(c!=' ')

                                              if(find_char(elem,c,n)==-1)

                                              {   n++;

                                                             elem[n]=c;

                                                             weight[n]=1;

                                              else weight[find_char(elem,c,n)]+=1;

               printf("除空格和回车之外各字符的出现频率如下：\n");

//打印字符极其权值

               for(i=0;i<=n;i++)

                               printf("%c %d",elem[i],weight[i]);

                               printf("\n");

               return n+1;

main()

               huffnode ht[2*max];

               huffcode htd[max],d;

               int i,k,f,l,r,n,c,m1,m2,j;

               printf("请输入一个字符串，以回车结束\n");

               n=get_elem_weight();

               for(i=1;i<=n;i++)

                               ht[i].data =elem[i-1];

                               ht[i].weight =weight[i-1];

               for(i=1;i<=2*n-1;i++)

                               ht[i].parent =ht[i].left =ht[i].right =0;//叶结点初始化

               for(i=n+1;i<=2*n-1;i++)

                               m1=m2=32767;

                               l=r=0;

                               for(k=1;k<=i-1;k++)

                                              if(ht[k].parent ==0)

                                              //寻找当前结点中权值最小的两个结点

                                                             if(ht[k].weight <m1)

                                                                            m2=m1;

                                                                            r=l;

                                                                             m1=ht[k].weight ;

                                                                            l=k;

                                                             else if(ht[k].weight <m2)

                                                                            m2=ht[k].weight ;

                                                                            r=k;

                                                             ht[l].parent =i;//建立父结点信息

                                                             ht[r].parent =i;

                                                             ht[i].weight =ht[l].weight +ht[r].weight ;

                                                             ht[i].left =l;

                                                             ht[i].right =r;

               for(i=1;i<=n;i++)//由建立的结点生成Huffman编码

                               d.start =n+1;

                               c=i;

                               f=ht[i].parent ;

                               while(f!=0)

                                              if(ht[f].left ==c)

                                                             d.cd[--d.start ]='0';

                                              else

                                                             d.cd [--d.start ]='1';

                                              c=f;

                                              f=ht[f].parent ;

                               htd[i]=d;

               printf("输出编码\n");

               for(i=1;i<=n;i++)

                               printf("%c:",ht[i].data );

                               for(k=htd[i].start ;k<=n;k++)

                                              printf("%c",htd[i].cd[k]);

                               printf("\n");

               printf("你所输入的字符串为\n");

               for(i=0;i<m-1;i++) printf("%c",input[i]);

               printf("\n");

               printf("经过编码之后\n");//打印编码后结果

               for(i=0;i<m-1;i++)

                  if(input[i]!=' ')

                                 for(k=1;k<=n;k++)

                                                if(ht[k].data ==input[i]) break;

                                                for(j=htd[k].start ;j<=n;j++)

                                                                printf("%c",htd[k].cd [j]);

                  else printf("%c",input[i]);

    printf("\n");

谢谢拉！！非常感谢~
回去调试一下呵呵

第 9 楼

得分:0

以下是引用starrysky在2006-5-28 19:37:00的发言：
马甲？？我有点糊涂了
Huffman树么

，以前牛虻写过一个，我可是记得很亲楚（

骗了我1000大洋啊）
唉，置顶的那个索引帖子

我去看了但是没有是时间想了啊
把你的网址都保存了
交差后再饿补咯只好
谢谢哦！

第 10 楼

得分:0

哇，好多的高手啊！我为何学不好呢？