哈夫曼树和哈夫曼编码及保存

哈夫曼树,和哈夫曼编码 是二叉树里面的一个重要应用,理解起来也比较困难,但是只要敲两下 就差不多了,下面就是我的代码,频率的话就是所有的变成整数就行了 比如某字符出现频率是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;
//	}
	
} 

这是文件的代码
哈夫曼树和哈夫曼编码及保存
最后结果是这样的哈夫曼树和哈夫曼编码及保存
哈夫曼树和哈夫曼编码及保存

上一篇:C# 理解委托与事件


下一篇:海事监管新模式 | 智慧舰船三维可视化管理