| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 568 人关注过本帖
标题:哈夫曼树.帮帮忙看下错
只看楼主 加入收藏
mylzy159
Rank: 2
等 级:论坛游民
帖 子:61
专家分:23
注 册:2009-4-12
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:2 
哈夫曼树.帮帮忙看下错
huffmancode.rar (307.35 KB)
图片附件: 游客没有浏览图片的权限,请 登录注册
搜索更多相关主题的帖子: 哈夫曼 
2010-06-23 22:14
longxuan1011
Rank: 2
等 级:论坛游民
威 望:1
帖 子:4
专家分:20
注 册:2010-6-19
收藏
得分:20 
看我的吧,你的设计的不好
# include <stdio.h>      
# include <stdlib.h>
# include <conio.h>
# include <string.h>
# define MAX_LENGTH 100
typedef char **HuffmanCode;
//**********数据结构*************
typedef struct   
{   int weight; //权值
    int parent,lchild,rchild; //双亲,左右孩子
}HTNode,*HuffmanTree;   //结点和指针
//**********select函数**************
void Select(HuffmanTree HT,int i,int &s1,int &s2)
{ //在建立哈夫曼树的所有结点中选择权值最小的两个结点存放在s1,s2中
   int j,k=1;               
   while(HT[k].parent!=0)
       k++;
   s1=k;
   for(j=1;j<=i;++j)
      if(HT[j].parent==0&&HT[j].weight<HT[s1].weight)
   s1=j;
   k=1;
   while(HT[k].parent!=0||k==s1)
      k++;
   s2=k;
   for(j=1;j<=i;++j)
      if(HT[j].parent==0&&HT[j].weight<HT[s2].weight&&j!=s1)
   s2=j;
}
//**********构建哈夫曼树***********************


void HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,int *w,int n)
{
    int m,i,s1,s2,start,c,f;
    HuffmanTree p;
   if(n<=1)
     return;
   m=2*n-1;//由得到的叶子数而计算结点总数
   HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//分配存储空间
   for(p=HT+1,i=1;i<=n;++i,++p,++w)
     { p->weight=*w;//为结点初始化权值
       //cout<<endl<<"HT["<<i<<"].weight="<<p->weight<<" ";  
       printf("\nHT[%d].weight=%d ",i,p->weight);
       p->parent=0;
       p->lchild=0;
       p->rchild=0;
     }
   for(;i<=m;++i,++p)   
     { p->weight=0;
       p->parent=0;
       p->lchild=0;
       p->rchild=0;
     }//初始化双亲和左右孩子,使他们成为孤立的
  // cout<<endl<<endl<<"哈弗曼树创建的顺序如下:";
   printf("\n\n赫夫曼树创建的顺序如下:");
   for(i=n+1;i<=m;++i)
   {
      Select(HT,i-1,s1,s2); //调用select函数
      HT[s1].parent=i;
      HT[s2].parent=i;
      HT[i].lchild=s1;
      HT[i].rchild=s2;
      HT[i].weight=HT[s1].weight+HT[s2].weight;//新结点的权值是s1和s2权值的和
     // cout<<endl<<"HT["<<s1<<"] and HT["<<s2<<"] create";
      printf("\nHT[%d] and HT[%d] create",s1,s2);
    //  cout<<" HT["<<i<<"].weight="<<HT[i].weight;
      printf("\tHT[%d].weight=%d",i,HT[i].weight);
     
   }//每次选择最小的两个结点做左右孩子,权值和为新的结点的权值和,删去连个小的结点
   //*********哈夫曼编码*****************
   HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
   char *cd;
   cd=(char *)malloc(n*sizeof(char));
   cd[n-1]='\0';
   //cout<<endl<<endl<<"HuffmanTree编码是:"<<endl;
    printf("\n\nHuffmanTree编码是:\n");
   for(i=1;i<=n;++i)//从底下往上寻回编码
   { start=n-1;
      for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
        if(HT[f].lchild==c)
           cd[--start]='0';
         else
          cd[--start]='1';
      HC[i]=(char*)malloc((n-start)*sizeof(char));
      strcpy(HC[i],&cd[start]);
      printf("\nHT[%d] node's Huffman code is: %s",i,HC[i]);
   }
   free(cd);
}
//****************主函数部分********************
void main()              
{  HuffmanTree HT;
   HuffmanCode HC;
   int n,i;
   int *w,W[MAX_LENGTH];
  // cout<<"***********本实验实现的是哈夫曼树的建立以及编码*********";//交互信息
   printf("***********本实验实现的是赫夫曼树的建立以及编码**********");
  // cout<<endl<<"请输入哈弗曼树元素的个数: ";
   printf("\n请输入赫夫曼树元素的个数:");
  // cin>>n;
   scanf("%d",&n);
   for(i=0;i<n;++i)
   {
       //cout<<"请输入第 "<<i+1<<"个元素的权值(0~255的整数): ";
       printf("请输入第%d个元素的权值(0~255的整数):",i+1);
      // cin>>W[i];
       scanf("%d",&W[i]);
   }
   w=W;
   HuffmanCoding(HT,HC,w,n);
   getch();
}

2010-06-24 21:49
mylzy159
Rank: 2
等 级:论坛游民
帖 子:61
专家分:23
注 册:2009-4-12
收藏
得分:0 
回复 楼主 mylzy159
嗯.我错误调试出来了..你这个好像跟书上的好像一样的..我就是不想跟书上做一样的.
  不过还是谢谢你.
2010-06-24 22:45
快速回复:哈夫曼树.帮帮忙看下错
数据加载中...
 
   



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

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