| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 617 人关注过本帖
标题:HUFFMAN编码 求解救
只看楼主 加入收藏
约束小朋友
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2013-5-28
结帖率:85.71%
收藏
已结贴  问题点数:20 回复次数:1 
HUFFMAN编码 求解救
结点值ABCDE这个地方不知道为什么i第一个数输入不进去
i是从第二个数输进去的
计算基本没问题
就是结点值输入出现了问题
调试后发现A是当i=1的时候输进去的
而非i=0的时候
求高手指点

如各个叶子值分别为A、B、C、D、E,各个权值分别为18,12,10,7,11。此部分信息由键盘一边输入,一边对数组初步赋值,结果如下:
数组下标    结点值    权值    左孩子    右孩子    双亲
0    A    18    -1    -1    -1
1    B    12    -1    -1    -1
2    C    10    -1    -1    -1
3    D    7    -1    -1    -1
4    E    11    -1    -1    -1
5                    
6                    
7                    
8                    
计算二叉树其余结点信息。
由于5个叶子结点,要合并4次。每次从还无双亲(无双亲代表还未合并过)的叶子结点中选择权值最小的两个叶子结点进行合并,新结点下标为这两个叶子的双亲,新结点的权值为这两个叶子权值之和,左孩子为最小结点下标,右孩子为次小结点下标,叶子值不需要,双亲为0。
如下为合并一次后的结果,如此循环4次即可:
数组下标    结点值    权值    左孩子    右孩子    双亲
0    A    18    -1    -1    -1
1    B    12    -1    -1    -1
2    C    10    -1    -1    5
3    D    7    -1    -1    5
4    E    11    -1    -1    -1
5        17    3    2    -1
6                    
7                    
8                    

以下是我写的程序


#include<stdio.h>

struct node
{
  int weight;
  int parent,lch,rch;
  char yezi;
};
struct node Htree[80];
int n;
creat_huff(struct node Htree[])
{
  int i,j,min1,min2,seat1,seat2;
  char yezi;
  printf("请输入叶子的个数(<10):");
  scanf("%d",&n);
  for(i=0;i<2*n-1;i++)
  {
    Htree[i].parent=-1;
    Htree[i].lch=-1;
    Htree[i].rch=-1;
   
  }
  printf("\n请输入各叶子的值:");
  for(i=0;i<=n;i++)
     {
      scanf("%c",&Htree[i].yezi);
  }
      printf("\n请输入各叶子权值:");
   for(i=0;i<n;i++)
   {      
      scanf("%d",&Htree[i].weight);
   }
   for(i=n;i<2*n-1;i++)
   {
     min1=min2=1000;
     seat1=seat2=0;
     for(j=0;j<i;j++)
     {
       if(Htree[j].parent==-1)
           if(Htree[j].weight<min1)
           {
              seat2=seat1;
              min2=min1;
              seat1=j;
              min1=Htree[j].weight;
           }
           else if(Htree[j].weight<min2)
           {
              seat2=j;
              min2=Htree[j].weight;
           }
     }
     Htree[seat1].parent=Htree[seat2].parent=i;
     Htree[i].weight=Htree[seat1].weight+Htree[seat2].weight;
     Htree[i].lch=seat1;
     Htree[i].rch=seat2;
   }
   Htree[2*n-2].parent=-1;
 
}
code_huff(struct node Htree[])
{
  int i,j,seatyezi,fumu;
  int code[80][80];
  for(i=0;i<n;i++)
  {
     j=n-2;
     seatyezi=i;
      
    while(Htree[seatyezi].parent!=-1)
    {
        fumu=Htree[seatyezi].parent;
        if(seatyezi==Htree[fumu].lch)
            code[i][j]=0;
        else  code[i][j]=1;
        j=j-1;
        seatyezi=fumu;
    }
    code[i][n-1]=j+1;
  }
     printf("\n叶子的编码为:\n");
     for(i=0;i<n;i++)
     {
         printf("%c:",Htree[i].yezi);
     for(j=code[i][n-1];j<n-1;j++)
         printf("%d",code[i][j]);
     
     printf("\n");     
    }
}
out_huff(struct node Htree[])
{
   int i;
    printf("\nleave weight parent lch rch\n");
   for(i=0;i<n;i++)
   printf("   %c   %2d     %2d     %2d  %2d \n",Htree[i].yezi,Htree[i].weight,Htree[i].parent,Htree[i].lch,Htree[i].rch);
   for(i=n;i<2*n-1;i++)
   printf("        %2d     %2d     %2d  %2d \n",Htree[i].weight,Htree[i].parent,Htree[i].lch,Htree[i].rch);
}
void main()
{
   
    creat_huff(Htree);
    out_huff(Htree);
    code_huff(Htree);
}
搜索更多相关主题的帖子: 键盘 信息 叶子 
2013-11-27 21:06
yuccn
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:何方
等 级:版主
威 望:167
帖 子:6815
专家分:42393
注 册:2010-12-16
收藏
得分:20 
http://blog.
HUFFMAN编码 的一个文章

我行我乐
公众号:逻辑客栈
我的博客:
https://blog.yuccn. net
2013-11-28 14:12
快速回复:HUFFMAN编码 求解救
数据加载中...
 
   



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

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