哈夫曼树，和哈夫曼编码 是二叉树里面的一个重要应用，理解起来也比较困难，但是只要敲两下 就差不多了，下面就是我的代码，频率的话就是所有的变成整数就行了 比如某字符出现频率是0.21，还有一些。。。反正加起来为1嘛 ，权重就是21撒
// An highlighted block
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX_SIZE 1024
using namespace std;
typedef struct{
char c;
int start;
int weight;
char code[MAX_SIZE];
}Code,*HfCode; //这个用来记录 哈夫曼的编码的
typedef struct {
int weight;
char c;
int parent;
int Lch;
int Rch;
}HtNode,*Huffmantree; //这个是哈夫曼树 通过数组的方式来弄二叉树 所以没有用指针 数组便于合并
typedef struct Strcount{
char c;
int cnt;
}Strcount;//这个是记录字符频率的结构体
Strcount strcount[MAX_SIZE];//全局定义全局使用
int cdstr_len=0;//下面记录这个字符长度的 后面常用
int cmp(Strcount t1,Strcount t2)//sort 的一个性质
{
return t1.cnt>t2.cnt;
}
void Countstr(char *str)//统计单词出现的频率 即权重
{
int len = strlen(str);
int temp[MAX_SIZE];
memset(temp,0,sizeof(temp));
int i,j;
for(i=0;i<len;i++)
{
temp[(str[i]+'0')]++;//记录出现的频率
}
for(i=0;i<len;i++)
{
for(j=0;j<cdstr_len;j++)
{
if(strcount[j].c==str[i])
{
break;
}
}
if(j==cdstr_len)//结构体记录
{
strcount[cdstr_len].c=str[i];
strcount[cdstr_len].cnt = temp[str[i]+'0'];
cdstr_len++;
}
}
sort(strcount,strcount+cdstr_len,cmp);//给权重排序 sort(数组首地址，数组的尾地址，比较函数)
cout<<"字符总数为："<<len<<"\r\n";
for(i=0;i<cdstr_len;i++)
{
printf("%c出现的次数是:%d\n",strcount[i].c,strcount[i].cnt);
}
cout<<"\r\n";
}
int Min_index(Huffmantree &Ht,int k)
{
int i,min;
int minweight = 100;//设置权重为很大，所以然后返回最小
for(i=1;i<=k;i++)//循环去找
{
if(Ht[i].parent==0&&Ht[i].weight<minweight)
{
min = i;
minweight = Ht[i].weight;
}
}
Ht[min].parent=k+1;//规避下一次s2的选取 不然会选到同一个 并且把现在的双亲设为前面 CreateHuffman里面的i 双亲对接
return min;
}
void Select(Huffmantree Ht,int i,int &s1,int &s2)//找到双亲为0且最小的两个
{
s1 = Min_index(Ht,i-1);//我们传的是ht[i]是没值的，要在i-1里面去找
s2 = Min_index(Ht,i-1);
}
void CreateHuffman(Huffmantree &Ht)
{
int m=2*cdstr_len-1;//最终只用两倍少一个
Ht = new HtNode[m+1];//但要多申请一个
int i;
for(i=1;i<=m;i++)//初始化每个为0 避免后面指错
{
Ht[i].parent=0;
Ht[i].Lch=0;
Ht[i].Rch=0;
}
int cnt=0;
for(i=1;i<=cdstr_len;i++)//权重和字母赋值
{
Ht[i].weight= strcount[i-1].cnt;
Ht[i].c = strcount[i-1].c;
}
int minadress1,minadress2;//
for(i=cdstr_len+1;i<=m;i++)
{
Select(Ht,i,minadress1,minadress2);//这里找到了前面所有数的最小的两个数 并且没有双亲 的
Ht[i].Lch=minadress1;// 前面MIn_index 完成了双亲的对接 这里 只需要完整 孩子的对接
Ht[i].Rch= minadress2;
Ht[i].weight = Ht[minadress1].weight+Ht[minadress2].weight;//给他们赋值 后面的都是没有 实际字符的
}
}
void CreateHuffCode(Huffmantree Ht,HfCode &Hc)//创建码的
{
int i;
Code tempcd;//这里来个临时的编码结构体
int nownode,parentnode;
for(i=1;i<=cdstr_len;i++)
{
tempcd.start=cdstr_len;//这个开始的位置是和字符一样长 倒序存入 然后一直减减 最后再正序输出
tempcd.c=Ht[i].c;
tempcd.weight = Ht[i].weight;//对应的赋值
nownode=i;//现在的结点
parentnode = Ht[i].parent; //现在结点的双亲
while( parentnode!=0)
{
tempcd.start--;
if(Ht[parentnode].Lch==nownode)
{
tempcd.code[tempcd.start]='0';
}
else{
tempcd.code[tempcd.start]='1';//如果我是属于双亲的的右儿子 就是1 反之为 0
}
nownode = parentnode; //倒序编码 所以接着往上走
parentnode = Ht[parentnode].parent;
}//of while
Hc[i]=tempcd;
}//of for
}
int main()
{
FILE *fp;
char savecd[MAX_SIZE];
char str[1024];
fp=fopen("hafuman.txt","r+");//读取文件
fgets(str,1024,fp);
fclose(fp);
Countstr(str);
Huffmantree Ht;
CreateHuffman(Ht);
int i,j,k;
HfCode mycode = new Code[MAX_SIZE]; //创建编码 的结构体 存储
CreateHuffCode(Ht,mycode);
//每个字符的哈夫曼 编码
for(i=1;i<=cdstr_len;i++)
{
printf("%c的哈夫曼编码是：",mycode[i].c);
for(j=mycode[i].start;j<cdstr_len;j++)
{
cout<<mycode[i].code[j]<<" ";
}
printf("\r\n");
}
cout<<"所以"<<str<<"的编码是:\n";
int savecnt=0;
for(i=0;i<cdstr_len;i++)
{
for(j=1;j<=cdstr_len;j++)//挨个的找，如果字符对应上就行
{
if(str[i]==mycode[j].c)
{
for( k=mycode[j].start;k<cdstr_len;k++)
{
cout<<mycode[j].code[k];
savecd[savecnt++]=mycode[j].code[k];
}
break;
}
}
cout<<" ";
}
cout<<endl;
savecd[savecnt]='\0';
cout<<savecd;
fp=fopen("hafumancode.txt","w+");
fputs(savecd,fp); //保存到文件当中去
fclose(fp);
// for(i=1;i<=2*cdstr_len-1;i++)
// {
// cout<<i<<"\t"<<Ht[i].weight<<"\t"<<Ht[i].parent<<"\t"<<Ht[i].Lch<<"\t"<<Ht[i].Rch<<endl;
// }
}
这是文件的代码
最后结果是这样的