huffmancode.cpp

这是一个赫夫曼加密算法

#include<iostream.h>
#include<iomanip.h>
#include<fstream.h>
#include<stdlib.h>
#include<stdio.h>
#include<string>

//**********************************
//定义HuffmanTree的结构
//**********************************
struct HTNode{
	int weight;
	int parent;
	int lchild;
	int rchild;
}HTNode;

//***********************************
//定义堆元素的数据结构
//***********************************
struct SqList{
	int num;
	int weight;
}SqList;
	
typedef char ** HuffmanCode;

//***************
//全局变量
//***************
struct SqList *list;  //用来进行堆排序
int total=0;

//***************
//函数声明
//***************
void Choice(void);
void ShowMessage(void);
void WeightTotal(ifstream,int &n,char wchar[],int w[]);
void HuffmanCoding(void);
void Select(int,int &,int &);
void SaveHuffmanCode(ofstream &,ifstream,char wchar[],HuffmanCode HC);
void UnHuffmancode(void);
void Select1(int n,int &s1,int &s2,struct HTNode*);
void HeapAdjust(int s,int m);
void HeapSort(int &s1,int &s2);


//**************************************************************
//
//主函数
//
//**************************************************************

void main(void)
{
	Choice();//调用主介面函数
}

//**************************************************************
//
//主介面
//有四个分支
//**************************************************************
void Choice(void)
{

	 char choice;
     while(1)
	 {
	      cout<<"                              Huffman code\n";
	      cout<<"                              1     编码\n";
	      cout<<"                              2     解码\n";
	      cout<<"                              3     查看编码\n";
	      cout<<"                              4     退出\n";

	      cout<<"按1-4键进行选择:";
	      do{
	          cin.get(choice);
	          cin.ignore(20,'\n');		 
    	      if(choice!='1'&&choice!='2'&&choice!='3'&&choice!='4')
	          cout<<"错误!请输入1到4进行选择:";

		  }while(choice!='1'&&choice!='2'&&choice!='3'&&choice!='4');
	 
 
         switch(choice)
		 {
	      case '1':system("cls");
	               HuffmanCoding();//编码
				   break;
   
          case '2':system("cls");
  	              UnHuffmancode();//解码
                  break;
  
          case '3':system("cls");//显示编码信息
	               ShowMessage();
                   break;
   
          case '4':exit(0);//退出
		}
	 }
}


//*********************************************************************
//
//计算各个字符出现的次数,即计算权值
//
//*********************************************************************
void WeightTotal(ifstream inFile,int &n,char wchar[],int w[])  
{
   char ch,str[81];
   int p[128];
   int i,j=1,k;

   n=0;

   for(i=0;i<128;i++)
	   p[i]=0;

  inFile.getline(str,81,'\n');//从文件中读取
  while(!inFile.eof())
  {
	  k=0;
	  while(k<80&&str[k]!='\0')
	  {   
		  ch=str[k];
		  p[int(ch)]++;
		  k++;
	  }
	  if(k!=80)  
	  {
		  ch='\n';
   	      p[int(ch)]++;
	  }
 
     inFile.getline(str,81,'\n');
  }
  k=0;
  while(k<80&&str[k]!='\0')
  {   
		  ch=str[k];
		  p[int(ch)]++;
		  k++;
  }
  if(k!=80)  
  {
		  ch='\n';
   	      p[int(ch)]++;
  }
  i=0;
  while(i<128)
  {
     if(p[i]!=0)
	 {
	   w[j]=p[i]; 
	   wchar[j]=char(i);
	   j++;
	   n++;
	 }
     i++;
 }
}


//***************************************************************
//
//构造HuffmanTree,并求出这些字符的编码
//
//***************************************************************
void HuffmanCoding(void)  
{
    ifstream inputFile;
 
    char inFileName[20],outFileName[20];
    char wchar[128];
    int w[128];
    int n;
    HuffmanCode HC;

    cout<<"                          编码介面\n\n";
    cout<<"请输入进行编码的文件名:";
	  
    cin>>inFileName;
    cin.ignore();
  
    inputFile.open(inFileName);
    if(inputFile.fail())
	{
          cout<<"ERROR OPENING THE FILE!"<<endl;
	      exit(0);
    }
 
    WeightTotal(inputFile,n,wchar,w); //调用统计权值函数


  
    if(n<=1)
	{
    	  system("cls");
    	  return;	  
	}
   int m,i;
   m=2*n-1;

   struct HTNode *HT;
   struct HTNode *p;

   HT=new struct HTNode[2*n];

   for(p=HT+1,i=1;i<=n;i++,p++)//初始化
   {
    	  p->weight=w[i];
    	  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;
   }

   int s1,s2;

   for(i=n+1;i<=m;i++)
   {//建哈夫曼树
    	list=new struct SqList[128];

        Select1(i-1,s1,s2,HT);

    	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;

    	delete list;
   }

   HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
   char *cd;
   cd=(char *)malloc(n*sizeof(char));
   cd[n-1]='\0';

   int start,c,f;

  
   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]);
   }
   free(cd);

   cout<<"正在储存编码信息到指定文件中......\n\n\n";

   ofstream outputFile;
   ofstream numinformation;
   ofstream charinformation;
   ofstream HTinformation;

   cout<<"请输入要保存的文件名:";
	  
   cin>>outFileName;
   cin.ignore();
  
   outputFile.open(outFileName);
   numinformation.open("num.dat",ios::out);
   charinformation.open("char.dat",ios::out);
   HTinformation.open("ht.dat",ios::out|ios::binary);
   
   inputFile.close();
   inputFile.open(inFileName);
  

   if(numinformation.fail()&&charinformation.fail()&&HTinformation.fail()&&inputFile.fail()&&outputFile.fail())
   {
           cout<<"ERROR OPENING THE FILE!"<<endl; 
    	   exit(0);
   }
    

   SaveHuffmanCode(outputFile,inputFile,wchar,HC);

   numinformation<<n;
   
   i=1;
   while(i<=n)
   {
          charinformation<<wchar[i]; 
    	  i++;
   }
   
   i=1;
   while(i<=m)
   {
    	  HTinformation.write((char*)(HT+i),sizeof(struct HTNode));
    	  i++;
   }

   numinformation.close();
   charinformation.close();
   HTinformation.close();
   outputFile.close();
   cout<<"文件保存到"<<outFileName<<endl;
   cout<<"储存完毕\n";
   cout<<"\n\n\n按回车键返回主介面";
   char ch;
   cin.get(ch);
   system("cls");
}


//************************************************************
//
//在HT[1..i-1]选择parent为0且weight最小的两个结点,其序号分别为s1,s2
//用堆排序实现
//************************************************************
void Select1(int n,int &s1,int &s2,struct HTNode *HT)
{
     int i;
   
     total=0;

     for(i=1;i<=n;i++)
	 {
         if(HT[i].parent==0)
		 {
    		  (list+total+1)->num=i;
    		  (list+total+1)->weight=HT[i].weight;
    		  total++;
		 }
	 }
     HeapSort(s1,s2);
}


//****************************************************
//
//进行堆排序
//
//****************************************************
void HeapAdjust(int s,int m)
{
     struct SqList list1;
     int j;

     list1.num=(list+s)->num;
     list1.weight=(list+s)->weight;

     for(j=2*s;j<=m;j=j*2)
	 {
    	  if(j<m&&(list+j)->weight<(list+j+1)->weight)
    		  j++;
    	  if(list1.weight>=(list+j)->weight)
    		  break;
    
    	  (list+s)->num=(list+j)->num;
	      (list+s)->weight=(list+j)->weight;
	      s=j;
	 }

     (list+s)->num=list1.num;
     (list+s)->weight=list1.weight;
}


//************************************************************
//
//进行堆排序	
//其权值最小的两个数的序号用s1,s2返回
//***********************************************************
void HeapSort(int &s1,int &s2)
{
     int i;
     struct SqList list2;

     for(i=total/2;i>0;i--)
	 {
         HeapAdjust(i,total);
	 }
   
     for(i=total;i>1;i--)
	 {
           list2.num=(list+1)->num;
	       list2.weight=(list+1)->weight;
	   
	       (list+1)->num=(list+i)->num;
	       (list+1)->weight=(list+i)->weight;

           (list+i)->num=list2.num;