数据结构与算法:哈夫曼树(源码)!-阿里云开发者社区

开发者社区> 人工智能> 正文

数据结构与算法:哈夫曼树(源码)!

简介:

 

复制代码
#include<iostream> 
#define MAXVALUE 100000
using namespace std;
const int n=4;//叶子节点个数 
//构造哈夫曼树结点 
typedef struct{
int weight;//权值 
int parent;//父节点 
int lchild;//左子树 
int rchild;//右子树 
}HNodeType;

HNodeType HFMTree[
2*n-1];//结点数 

//构造哈夫曼编码数组
typedef struct{
int bit[n];
int start;
}HCodeType;

HCodeType HFMCode[n];
//创建哈夫曼树 
void createHFMTree(HNodeType HFMTree[],int n){
int m1,x1,m2,x2;
int i,j;
//初始化
for(i=0;i<2*n-1;i++){
   HFMTree[i].weight
=0;
   HFMTree[i].parent
=-1;
   HFMTree[i].lchild
=-1;
   HFMTree[i].rchild
=-1;
}
cout
<<"请输入结点权值:"<<endl; 
for(i=0;i<n;i++){                
   cin
>>HFMTree[i].weight;
}
for(i=0;i<n-1;i++){
   x1
=x2=MAXVALUE;
   m1
=m2=0;
   
for(j=0;j<n+i;j++){
    
if(HFMTree[j].parent==-1&&HFMTree[j].weight<x1){
     x2
=x1;
     m2
=m1;
     x1
=HFMTree[j].weight;
     m1
=j;
    }
    
else if(HFMTree[j].parent==-1&&HFMTree[j].weight<x2){
     x2
=HFMTree[j].weight;
     m2
=j;
    }
   }
   HFMTree[m1].parent
=n+i;HFMTree[m2].parent=n+i;
   HFMTree[n
+i].weight=HFMTree[m1].weight+HFMTree[m2].weight;
   HFMTree[n
+i].lchild=m1;
   HFMTree[n
+i].rchild=m2;
}
}
//转化编码 
void createHFMCode(HNodeType HFMTree[],HCodeType HFMCode[]){
HCodeType cd;
int i,j,c,p;
for(i=0;i<n;i++){
   cd.start
=n-1;
   c
=i;
   p
=HFMTree[c].parent;
   
while(p!=-1)
   {
    
if(HFMTree[p].lchild==c)cd.bit[cd.start]=0;
    
else cd.bit[cd.start]=1;
    cd.start
--;
    c
=p;
    p
=HFMTree[c].parent;
   }
   
for(j=cd.start+1;j<n;j++)
    HFMCode[i].bit[j]
=cd.bit[j];
   HFMCode[i].start
=cd.start+1;
}
}
//主函数 
int main()
{
int i,j;
//创建树 
createHFMTree(HFMTree,n);
//转码 
createHFMCode(HFMTree,HFMCode);
cout
<<endl;
for(i=0;i<n;i++)
{
   
for(j=HFMCode[i].start;j<=n-1;j++)
   {
    cout
<<HFMCode[i].bit[j];
   }
   cout
<<endl;
}
return 0;
}
复制代码

 

这个是雏形,下面我们要实现的功能是,输入一个含有N位A,B,C,D四种字母的字符串。

然后转换成只含有0,1的代码串。之所以要使用哈夫曼树是因为哈夫曼树是最优树。根据权值来实现最短编码。

下面是实现自动转码的程序:

 

复制代码
#include<iostream> 
#define MAXVALUE 100000
using namespace std;
const int n=4;//叶子节点个数 
string l;
int size;
//构造哈夫曼树结点 
typedef struct{
int weight;//权值 
int parent;//父节点 
int lchild;//左子树 
int rchild;//右子树 
}HNodeType;

HNodeType HFMTree[
2*n-1];//结点数 

//构造哈夫曼编码数组
typedef struct{
int bit[n];
int start;
}HCodeType;

HCodeType HFMCode[n];
//创建哈夫曼树 
void createHFMTree(HNodeType HFMTree[],int n){
int m1,x1,m2,x2;
int i,j;
//初始化
for(i=0;i<2*n-1;i++){
   HFMTree[i].weight
=0;
   HFMTree[i].parent
=-1;
   HFMTree[i].lchild
=-1;
   HFMTree[i].rchild
=-1;
}
cout
<<"*******************哈夫曼树字符串最优转码程序***********************"<<endl; 
cout
<<"请输入一个字符串:(只含有A,B,C,D四种字符,输入回车结束)"<<endl; 
cin
>>l;
std::
string str(l);
  size
=str.size();    
  
for(int i=0;i<size;++i){   
   
if(str.at(i)=='A')HFMTree[0].weight++;
   
else if(str.at(i)=='B')HFMTree[1].weight++;
   
else if(str.at(i)=='C')HFMTree[2].weight++;
   
else if(str.at(i)=='D')HFMTree[3].weight++;
   
else
   cout
<<"输入有误!"<<endl;
   
break;
   }
}

for(i=0;i<n-1;i++){
   x1
=x2=MAXVALUE;
   m1
=m2=0;
   
for(j=0;j<n+i;j++){
    
if(HFMTree[j].parent==-1&&HFMTree[j].weight<x1){
     x2
=x1;
     m2
=m1;
     x1
=HFMTree[j].weight;
     m1
=j;
    }
    
else if(HFMTree[j].parent==-1&&HFMTree[j].weight<x2){
     x2
=HFMTree[j].weight;
     m2
=j;
    }
   }
   HFMTree[m1].parent
=n+i;HFMTree[m2].parent=n+i;
   HFMTree[n
+i].weight=HFMTree[m1].weight+HFMTree[m2].weight;
   HFMTree[n
+i].lchild=m1;
   HFMTree[n
+i].rchild=m2;
}
}
//转化编码 
void createHFMCode(HNodeType HFMTree[],HCodeType HFMCode[]){
HCodeType cd;
int i,j,c,p;
for(i=0;i<n;i++){
   cd.start
=n-1;
   c
=i;
   p
=HFMTree[c].parent;
   
while(p!=-1)
   {
    
if(HFMTree[p].lchild==c)cd.bit[cd.start]=0;
    
else cd.bit[cd.start]=1;
    cd.start
--;
    c
=p;
    p
=HFMTree[c].parent;
   }
   
for(j=cd.start+1;j<n;j++)
    HFMCode[i].bit[j]
=cd.bit[j];
   HFMCode[i].start
=cd.start+1;
}
}
//主函数 
int main()
{
int i,j;
//创建树 
createHFMTree(HFMTree,n);
//转码 
createHFMCode(HFMTree,HFMCode);
cout
<<endl;
int k=65;
for(i=0;i<n;i++)
{
   cout
<<(char)k<<"的编码:";
   
for(j=HFMCode[i].start;j<=n-1;j++)
   {
    cout
<<HFMCode[i].bit[j];
   }
   k
++;
   cout
<<endl;
}
cout
<<"转码后的字符串为:"<<endl;
std::
string str(l);
  size
=str.size();    
  
for(int i=0;i<size;++i){   
   
if(str.at(i)=='A'){
   
for(j=HFMCode[0].start;j<=n-1;j++)
   cout
<<HFMCode[0].bit[j];
   }
   
else if(str.at(i)=='B'){
   
for(j=HFMCode[1].start;j<=n-1;j++)
   cout
<<HFMCode[1].bit[j];
   }
   
else if(str.at(i)=='C'){
   
for(j=HFMCode[2].start;j<=n-1;j++)
   cout
<<HFMCode[2].bit[j];
   }
   
else if(str.at(i)=='D'){
   
for(j=HFMCode[3].start;j<=n-1;j++)
   cout
<<HFMCode[3].bit[j];
   }
   
else
   cout
<<"输入有误!"<<endl;
   
break;
   }
}
return 0;
}
复制代码

 

程序本机测试通过,可以放心运行!


本文转自施杨博客园博客,原文链接:http://www.cnblogs.com/shiyangxt/archive/2008/12/05/1348174.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章