文档章节

C++ 哈弗曼编码的实现与反编码

milin
 milin
发布于 2014/12/15 23:38
字数 1870
阅读 21
收藏 0

#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;

typedef struct{
     int weight;
	 int parent,lchild,rchild;
	 int asc;
}HTNode,*HuffmanTree;    //定义赫夫曼存储结构

struct node{
      int ASCII;
      int n;
};
struct node a[127];
struct node w[127];    
//一些全局变量
int count;
HTNode H_T[250];
char ** HC;
char filename[20];

//函数声明
void menu1();     //菜单1
HuffmanTree HeapSort(HuffmanTree HT,int length);    //堆排序
void MinHeapify(HuffmanTree HT, int k,int len);     //调整成一个小顶堆
void buildMinHeap(HuffmanTree HT,int len);          //建一个小顶堆
void swap(HTNode &t1,HTNode &t2);                   //交换两结构体
void savefile();                            //把输入的英文文章保存到文件
void loadfile();                           //从文件中读取文章
HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n);    //建立赫夫曼数并存入文件
void BianMa(HuffmanTree HT,int n );                                  //字符编码
void BianMa_all(HuffmanTree HT,char**HC,char *filename);             //整篇文章编码
int loadfile2();                                         //从文件读入文章
void JieMa();                                            //解码



//主函数
void main()
{    
    char s;
	while(s!='0')
	{
                system("cls");
	            cout<<"/n/n/n";
                cout<<"/t/t/t/t赫夫曼编码/译码器"<<endl<<endl<<endl<<endl<<endl;
	            cout<<"/t/t/t/t  1.编码"<<endl<<endl<<endl<<endl;
	            cout<<"/t/t/t/t  2.译码"<<endl<<endl<<endl<<endl;
	            cout<<"/t/t/t/t  0.退出"<<endl<<endl<<endl<<endl;
	            cout<<"/t请输入0—2进行选择,按回车确认";
	            cin>>s;
		        switch(s)
				{
			     case '1':  menu1(); break;
			     case '2':
				  { 
					  system("cls"); 
					  JieMa();
					  system("pause");
					  break;
				  }
		
				}
	    
	}
}
    
    
	
	

//菜单1	
void menu1(){
    char s;
	int i;
	int a;
	char c;
	char fpname[20]="article.txt";
	HuffmanTree HT;
while(s!='0'){
 
	      system("cls");
	      cout<<"/n/t/t/t/t编码界面";
	      cout<<"/n/n/n/t/t/t/t1.输入英文文章"<<endl;
	      cout<<"/n/n/t/t/t/t2.从文件中读入文章"<<endl;
	      cout<<"/n/n/t/t/t/t0.返回上一层"<<endl;
          cout<<"/n/t请输入0—2进行选择,按回车确认";
	      cin>>s;
  switch(s){
	      case'1': 
			 system("cls");
		     savefile();
			 loadfile();
			 CreateHuffman(HT,w,count);
			 BianMa(HT,count);
			 BianMa_all(HT,HC,fpname);
			 system("cls");
			 cout<<"出现字符种类共计:";
			 cout<<count<<endl;
			 for(i=1;i<=count;i++)
			 { a=HT[i].asc;
			   c=(char)a;
			   
			   
			   cout<<"________________________________________________________________________________"<<endl;
			   cout<<"/t/t/t字符:";
			   cout<<c<<endl;
			   cout<<"/t/t/tASCII码:";
			   cout<<a<<endl;
			   cout<<"/t/t/t频数:";
			   cout<<HT[i].weight<<endl;
			   cout<<"/t/t/t赫夫曼编码:";
			   cout<<HC[i]<<endl;
			   
			 
			 
			 }
			 cout<<"________________________________________________________________________________";
			 cout<<"/n/t/t整篇文章的编码已存入文件“赫夫曼编码.txt”"<<endl;
			 
			 system("pause");
			 break;
	
	case'2': 
		     system("cls");
		     if(loadfile2())
			 { system("pause");
			 return;}
             CreateHuffman(HT,w,count);
			 BianMa(HT,count);
			 BianMa_all(HT,HC,filename);
			 system("cls");
			 cout<<"出现字符种类共计:";
			 cout<<count<<endl;
			 for(i=1;i<=count;i++)
			 { a=HT[i].asc;
			   c=(char)a;
			   
			   
			   cout<<"________________________________________________________________________________"<<endl;
			   cout<<"/t/t/t字符:";
			   cout<<c<<endl;
			   cout<<"/t/t/tASCII码:";
			   cout<<a<<endl;
			   cout<<"/t/t/t频数:";
			   cout<<HT[i].weight<<endl;
			   cout<<"/t/t/t赫夫曼编码:";
			   cout<<HC[i]<<endl;
			   
			 
			 
			 }
			 cout<<"________________________________________________________________________________";
			 cout<<"/n/t/t整篇文章的编码已存入文件“赫夫曼编码.txt”"<<endl;
			 system("pause");
			 break;
		 }

}
	
}
	




//交换结构体
void swap(HTNode &t1,HTNode &t2)
{
   HTNode m;
   
	m = t1;
	t1 = t2;
	t2 = m;
 }
	

//从键盘输入文章并保存
void savefile(){
	
	FILE *fp;
	char article;
	if((fp=fopen("article.txt","w"))==NULL){

        printf("打开文件不成功!");
		exit(0);
     }
	cout<<"请输入英文文章,以#结束:";
    getchar();
	article=getchar();
	while(article!='#'){
	
		fputc(article,fp);
					
		article=getchar();
	}
   fclose(fp);
}



//从文件读取文章,并统计字符出现频数
void loadfile(){
     

	FILE *fp;
	char ch;
	int i,k,j=0;
	count=0;
	for(i=0;i<=127;i++)   //把所有字符的ascii码存在数组
	{ a[i].ASCII=i;
	  a[i].n=0;
	  
	}
 if((fp=fopen("article.txt","r"))==NULL){
	
	  printf("打开文件不成功!");
	  exit(0);
	}
       ch=fgetc(fp);
       k=(int)ch;
	   a[k].n++;
      while(!feof(fp)){
	      ch=fgetc(fp);
		  k=(int)ch;
	      a[k].n++;
       }
	  fclose(fp);
    
	 for(i=0;i<=127;i++)      //统计字符种类总数
	 {
		ch=(char)i;
		if(a[i].n){
		 count++;
		}
	 }
	 for(i=0;i<=127;i++)
	 {  
		 for(;j<count;)
		 {
			 if(a[i].n)
			 {
				w[j].n=a[i].n;
				w[j].ASCII=a[i].ASCII;
				j++;
				break;
			 }
			  else break;
		 }
	  }
	 
}



//调整为小顶堆
void MinHeapify(HuffmanTree HT, int k,int len)   
{
    int left=k*2;
    int right=k*2+1;
    int large;
	int l=len;
    
    large = k;
    if (left<=l&&HT[left].weight<HT[large].weight)
        large = left;

    if (right<=l&& HT[right].weight<HT[large].weight)
        large=right;
    
    if (large!=k)
    {
        swap(HT[k],HT[large]);
        MinHeapify(HT,large,l);
    }
}


//建立小顶堆
void buildMinHeap(HuffmanTree HT,int len)  
{
    int i;
    for (i=len/2;i>=1;i--)
    {
        MinHeapify(HT,i,len);
    }
}


//堆排序
HuffmanTree HeapSort(HuffmanTree HT,int length)
{
    int i;
    int l=length;
    buildMinHeap(HT,length);
    for (i=length;i>= 2;i--)
    {
        swap(HT[1],HT[i]);
        length--;
        MinHeapify(HT,1,length);
    }
	
	
	return HT;
}


   
//建立赫夫曼数
HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n)
{
    int i,m,s1,s2,k1,k2,j,x,a;
	FILE *fp,*fp2;
	
	
	if(n<=1) return HT;
    m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0不用
  
	for(i=1,j=0;i<=n;i++,j++)
	{   HT[i].asc=w[j].ASCII;
		HT[i].weight=w[j].n;
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
	for(;i<=m;i++)
	{ a=250+i;
	  HT[i].asc=a;//父亲节点的asc可以是大于127的任意值
	  HT[i].weight=0;
	  HT[i].parent=0;
	  HT[i].lchild=0;
	  HT[i].rchild=0;
	}
    for(i=1;i<=n;i++){
	
       H_T[i].asc=HT[i].asc;
	   H_T[i].parent=HT[i].parent;
	   H_T[i].lchild=HT[i].lchild;
	   H_T[i].rchild=HT[i].rchild;
	   H_T[i].weight=HT[i].weight;
	}
	  
	for(i=n+1,x=n;i<=m;i++,x--)
	{  
	 
		HeapSort(H_T,x);
	    k1=H_T[x].asc;
		k2=H_T[x-1].asc;
	   for(j=1;j<=127;j++)
	   {
		   if(HT[j].asc==k1)
		   { s1=j;break;}
	   
	   }
	    
       for(j=1;j<=127;j++)
	   {  
	      if(HT[j].asc==k2)
		  {	s2=j;break;}
	   
	   
	   }
	    
	   HT[s2].parent=i;
	   HT[s1].parent=i;
	   HT[i].lchild=s1;
	   HT[i].rchild=s2;
	   HT[i].weight=HT[s1].weight+HT[s2].weight;

	   H_T[x-1].asc=HT[i].asc;
       H_T[x-1].lchild=HT[i].lchild;
       H_T[x-1].parent=HT[i].parent;
       H_T[x-1].rchild=HT[i].rchild;
       H_T[x-1].weight=HT[i].weight;
	   
	}
   if((fp2=fopen("count.txt","w"))==NULL)        //保存赫夫曼树
   {   
       cout<<"文件打开不成功!"<<endl;
        exit(0);
   }
	   fputc(count,fp2);
   if((fp=fopen("HuffmanTree.dat","wb"))==NULL)
   {  cout<<"文件打开不成功!"<<endl;
      exit(0);
   
   }
     
   for(i=1;i<=(2*count-1);i++){
	 fwrite(&HT[i],sizeof(HTNode),1,fp);
   }
   fclose(fp);
   fclose(fp2);
  return HT;

}
	   
	  


//逆向编码
void BianMa(HuffmanTree HT,int n){
   char *cd,temp;
   
   int c,f,i,j,len,p,q;
     
   cd=(char *)malloc(n*sizeof(char));
   HC=(char * *)malloc(n*sizeof(char*));
   for(i=1;i<=n;i++){
	 for(c=i,f=HT[i].parent,j=0;f!=0;c=f,f=HT[f].parent,j++)
	 {	 if(HT[f].lchild==c) cd[j]='0';
		 else cd[j]='1';
		 if(HT[f].parent==0)
			cd[j+1]='/0';
		  
	 }
     
	 
	 len=strlen(cd);
	 for(p=0,q=len-1;p<=q;p++,q--)
	 {
		 temp=cd[q];
		 cd[q]=cd[p];
		 cd[p]=temp;
	 }
	 cd[len]='/0';
	 HC[i]=(char*)malloc((len+10)*sizeof(char));
     strcpy(HC[i],cd);

   } 
   
   

}





//整篇文章编码,并存入文件
void BianMa_all(HuffmanTree HT,char**HC,char *filename){
      char ch;
	  int k,i;
	  FILE *fp,*fp2;
	  
	 char code[100];
  if((fp=fopen(filename,"r"))==NULL){

        printf("打开文件不成功!");
		exit(0);
     }
 if((fp2=fopen("赫夫曼编码.txt","w"))==NULL){

        printf("打开文件不成功!");
		exit(0);
     }
     ch=fgetc(fp);
	 k=(int)ch;
	 while(!feof(fp))
	{
         
	  for(i=1;i<=count;i++)
	  {
		 if(k==HT[i].asc)
		 strcpy(code,HC[i]);
		 
	  }  
	    fputs(code,fp2);
	    ch=fgetc(fp);
		 k=(int)ch;
	 
	 }
    fclose(fp);
	fclose(fp2);

    

}

void JieMa(){
     int i,k,a,t,n=0;
     FILE *fp1,*fp2,*fp3;
	 char ch,c;
	 HuffmanTree ht;
	 if((fp3=fopen("count.txt","r"))==NULL)     //从文件读出字符总数
	 {    
        printf("打开文件不成功!");
		exit(0);
	 }
       n=fgetc(fp3);
     ht=(HuffmanTree)malloc(2*n*sizeof(HTNode));
    if((fp1=fopen("赫夫曼编码.txt","r"))==NULL)
    {

        printf("打开文件不成功!");
		exit(0);
    }

  if((fp2=fopen("HuffmanTree.dat","rb"))==NULL)
   {  cout<<"文件打开不成功!"<<endl;
      exit(0);
   
   }
for(i=1;i<=2*n-1;i++)

  fread(&ht[i],sizeof(HTNode),1,fp2);
  

  for(i=1;i<=2*n-1;i++)
  {
	if(ht[i].parent==0){t=k=i;break;}
  }       
 
 ch=fgetc(fp1);
 while(!feof(fp1)){
	 if(ch=='0')
	 {
	   k=ht[k].lchild;
	   if(ht[k].lchild==0)
	   {a=ht[k].asc;
	    c=(char)a;
		printf("%c",c);;
		
		k=t;
	   }
	 }
	if(ch=='1')
	{
	 k=ht[k].rchild;
	 if(ht[k].lchild==0)
	 {  a=ht[k].asc;
	    c=(char)a;
		printf("%c",c);
		
		k=t;
	 }
	 
	}

 
   ch=fgetc(fp1);
 }
  fclose(fp1);
  fclose(fp2);

}




//读取文件中的文章,可自己选择文件
int loadfile2(){
     
    
	FILE *fp;
	char ch;
	int i,k,j=0;
	count=0;
	for(i=0;i<=127;i++)
	{ a[i].ASCII=i;
	  a[i].n=0;
	  
	}
	cout<<"/n/n/n/t/t/t请输入你要打开的文件名:";
	cin>>filename;
   if((fp=fopen(filename,"r"))==NULL){
	
	  printf("打开文件不成功!");
	  return 1;
	}
       ch=fgetc(fp);
       k=(int)ch;
	   a[k].n++;
      while(!feof(fp)){
	      ch=fgetc(fp);
		  k=(int)ch;
	      a[k].n++;
       }
	  fclose(fp);
    
	 for(i=0;i<=127;i++){
		ch=(char)i;
		if(a[i].n){
		 count++;
		}
	}
	 for(i=0;i<=127;i++)
	 {  
		 for(;j<count;)
		 {
			 if(a[i].n)
			 {
				w[j].n=a[i].n;
				w[j].ASCII=a[i].ASCII;
				j++;
				break;
			 }
			  else break;
		 }
	  }
	 return 0;
}

本文转载自:http://blog.csdn.net/afgasdg/article/details/5596409

共有 人打赏支持
milin
粉丝 10
博文 94
码字总数 19598
作品 0
郑州
高级程序员
私信 提问
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
0
0
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆
2011/12/03
0
0
HuffmanTree----文件压缩

所谓Huffmantree又称为最优二叉树,是一种带权路径长度最短的二叉树;在Huffmantree中只有叶子节点才是有效数据节点,其他的非叶子节点是为了构造Huffmantree引入的。 一、首先要知道哈弗曼树...

七十七快
2018/06/26
0
0
HuffmanTree----文件压缩

所谓Huffmantree又称为最优二叉树,是一种带权路径长度最短的二叉树;在Huffmantree中只有叶子节点才是有效数据节点,其他的非叶子节点是为了构造Huffmantree引入的。 一、首先要知道哈弗曼树...

科技小能手
2017/11/12
0
0
QString乱谈(2)

长期以来,很多人都清楚,一旦C++源码中直接使用了中文,这样的源码想要跨平台(I18N)会非常困难。 随着: Windows下:MSVC2010成为主流 Linux下:GCC升级到4.6 C++中的中文问题 才算有了一个...

晨曦之光
2012/05/08
203
0

没有更多内容

加载失败,请刷新页面

加载更多

Go Timer实现原理剖析

简介 快速使用 操作介绍

恋恋美食
1分钟前
0
0
记录一个奇怪的问题

环境:jdk1.8虚拟机参数:-verbose:gc -XX:+PrintGCDetails -Xmx20m -Xms20m -Xmn10m -XX:SurvivorRatio=8  -XX:+HeapDumpOnOutOfMemoryError 可以看出,eden占8M却放不下6M数据,发生了......

暗中观察
29分钟前
0
0
创建多个git账号

实习开发中我们可能一个机子上配置多个git账号,如github.com,oschina.com 或者工作账号,私人账号,这时候就2个账号用一个key,肯定会冲突,有一个会提示没权限(账号和密码对应不上) ssh ...

echojson
31分钟前
1
0
rabbitmq安装教程

RabbitMQ有Windows与Linux版本的,这里先写Windows版本的安装。 以前安装软件总是在百度上找某某安装教程,结果能按照教程安装好的软件真的不多。想起先前以为大牛说的一句话,去官网按照官网...

em_aaron
今天
7
0
Android 贝塞尔曲线实践——波浪式运动

一、波浪效果如下 贝塞尔曲线自定义波浪效果的案例很多,同样方法也很简单,大多数和本案例一样使用二次贝塞尔曲线实现,同样还有一种是PathMeasure的方式,这里我们后续补充,先来看贝塞尔曲...

IamOkay
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部