| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2550 人关注过本帖, 1 人收藏
标题:[求助]Huffman树 周4就要交了 急啊!!
只看楼主 加入收藏
Faraway
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2006-5-28
收藏(1)
 问题点数: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 哈夫曼编码 频度 字符 
2006-05-28 15:22
论坛
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1372
专家分:0
注 册:2006-3-27
收藏
得分:0 
马甲

日出东方,唯我不败! 做任何东西都是耐得住寂寞,任何一个行业要有十年以上的积累才能成为专家
2006-05-28 15:58
独角龙
Rank: 1
等 级:新手上路
帖 子:221
专家分:0
注 册:2006-5-5
收藏
得分:0 
又是马甲??



奋斗改变一切!!
2006-05-28 19:19
starrysky
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:华中科技大学EI -T0405
等 级:版主
威 望:11
帖 子:602
专家分:1
注 册:2005-9-12
收藏
得分:0 
马甲??我有点糊涂了
Huffman树么
,以前牛虻写过一个,我可是记得很亲楚(骗了我1000大洋啊)
唉,置顶的那个索引帖子
[分享]数据结构版面经典帖子集合(长期更新, 新人必看!)
明明写了新人必看了,连颜色也漂成紫色了,为什么没人去看呢?我可是花了好长时间才整理出来的啊。
里面有Huffman树的完整代码连接。

我的征途是星辰大海
2006-05-28 19:37
墨斗鱼
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2006-4-10
收藏
得分: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");
}

2006-05-29 11:36
墨斗鱼
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2006-4-10
收藏
得分: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");
}

2006-05-29 11:40
SunShining
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:31
帖 子:2215
专家分:0
注 册:2006-2-17
收藏
得分:0 
以下是引用starrysky在2006-5-28 19:37:00的发言:
马甲??我有点糊涂了
Huffman树么
,以前牛虻写过一个,我可是记得很亲楚(骗了我1000大洋啊)
唉,置顶的那个索引帖子
[分享]数据结构版面经典帖子集合(长期更新, 新人必看!)
明明写了新人必看了,连颜色也漂成紫色了,为什么没人去看呢?我可是花了好长时间才整理出来的啊。
里面有Huffman树的完整代码连接。




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

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

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


[glow=255,violet,2]闭关修炼ing...[/glow] [FLASH=360,180]http://www./chinaren.swf[/FLASH]
2006-05-29 20:30
Faraway
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2006-5-28
收藏
得分: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");
}

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


2006-06-04 16:04
Faraway
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2006-5-28
收藏
得分:0 
以下是引用starrysky在2006-5-28 19:37:00的发言:
马甲??我有点糊涂了
Huffman树么
,以前牛虻写过一个,我可是记得很亲楚(骗了我1000大洋啊)
唉,置顶的那个索引帖子
[分享]数据结构版面经典帖子集合(长期更新, 新人必看!)
明明写了新人必看了,连颜色也漂成紫色了,为什么没人去看呢?我可是花了好长时间才整理出来的啊。
里面有Huffman树的完整代码连接。

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


2006-06-04 16:07
yingwufenghua
Rank: 1
等 级:新手上路
帖 子:18
专家分:0
注 册:2008-10-25
收藏
得分:0 
哇,好多的高手啊!我为何学不好呢?
2008-11-29 15:15
快速回复:[求助]Huffman树 周4就要交了 急啊!!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.043969 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved