test.cpp

MySQL数据库 其他数据库 汇编语言 SCSI/ASPI 编译器/解释器 磁盘工具 语音合成与识别 编辑器/阅读器 杀毒 中文信息处理

#include<iostream.h>   
  #include   <stdlib.h>   
  #include<string.h>   
  const   int   MaxValue=5000;                         //初始设定的权值最大值         
  const   int   MaxBit=5000;                                   //初始设定的最大编码位数   
  const   int   MaxN=3000;                                       //初始设定的最大结点个数   
    
  struct   HaffNode                                             //哈夫曼树的结点结构   
  {       char   ch;   
  int   weight;                                             //权值   
  int   flag;                                                 //标记   
  int   parent;                                             //双亲结点下标   
  int   leftChild;                                       //左孩子下标   
  int   rightChild;                                     //右孩子下标   
  };   
    
  struct   Code                                                     //存放哈夫曼编码的数组元数结构   
  {   
  int   bit[MaxN];                                       //数组   
  int   start;                                               //编码的起始下标   
  int   weight;                                             //字符的权值     
  char   ch;                                                                                       
  };   
  //建立叶结点个数为n权值为的weight哈夫曼树haffTree   
  void   Haffman(char   ch[],int   weight[],int   n,HaffNode   haffTree[])   
  {   
  int   j,m1,m2,x1,x2;   
  //哈夫曼树haffTree[]初始化,n个叶结点共有个2n-1结点   
  for(int   i=0;i<2*n-1;i++)   
  {   
  if(i<n)   
                  haffTree[i].ch=ch[i],haffTree[i].weight=weight[i];   
  else   
  haffTree[i].weight=0;   
  haffTree[i].parent=0;   
  haffTree[i].flag=0;   
  haffTree[i].leftChild=-1;   
  haffTree[i].rightChild=-1;   
  }   
    
  //构造哈夫曼树haffTree[]的个n-1非叶接点   
  for(i=0;i<n-1;i++)   
  {   
  m1=m2=MaxValue;   
  x1=x2=0;   
  for(j=0;j<n+i;j++)   
  {   
  if(haffTree[j].weight<m1   &&   haffTree[j].flag==0)   
  {   
  m2=m1;   
  x2=x1;   
  m1=haffTree[j].weight;   
  x1=j;   
  }   
  else   if(haffTree[j].weight<m2   &&   haffTree[j].flag==0)   
  {   
  m2=haffTree[j].weight;   
  x2=j;   
  }   
  }   
    
  //将找出的两棵权值最小的子树合并成为一棵树   
  haffTree[x1].parent=n+i;   
  haffTree[x2].parent=n+i;   
  haffTree[x1].flag=1;   
  haffTree[x2].flag=1;   
  haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;   
  haffTree[n+i].leftChild=x1;   
  haffTree[n+i].rightChild=x2;   
  }   
  }   
    
  //由n个结点的哈夫曼树haffTree[]构造哈夫曼编码haffCode[]   
  void   HaffmanCode(HaffNode   haffTree[],char   ch[],int   n,Code   haffCode[])   
  {   
  Code   *cd=new   Code;   
  int   child,parent;   
    
  //求n个叶结点的哈夫曼编码   
  for(int   i=0;i<n;i++)   
  {         
  cd->ch=haffTree[i].ch;   
          cd->start=n-1;                                                       //不等长编码的最后一位为n-1   
  cd->weight=haffTree[i].weight;                       //取得编码对应权值的字符   
  child=i;   
  parent=haffTree[child].parent;   
    
  //由叶结点向上直到根结点   
  while(parent!=0)   
  {   
  if(haffTree[parent].leftChild==child)   
  cd->bit[cd->start]=0;                                 //左孩子结点编码0   
  else   
  cd->bit[cd->start]=1;                                 //右孩子结点编码1   
  cd->start--;   
  child=parent;   
  parent=haffTree[child].parent;   
  }   
    
  //保存每个叶结点的编码和不等长编码的起始位   
  for(int   j=cd->start+1;j<n;j++)   
  haffCode[i].bit[j]=cd->bit[j];   
  haffCode[i].start=cd->start;   
  haffCode[i].weight=cd->weight;                               //记住编码对应权值的字符   
  }   
  }   
  void   trans(HaffNode   haffTree[],int   n,int   m,char   data[])   
  {   
    
                  int   k=0;   
  for(int   i=0;i<m;i++)   
  {   
  int   x=2*n-2;   
  int   p=0;   
  while(p!=1)   
  {         
  if(haffTree[x].leftChild!=-1)   
  {   
  switch(data[k])   
  {   
                          //case'-1':cout<<endl;cout<<"译码结束。";break;   
  case   '0':x=haffTree[x].leftChild;   
  break;   
  case   '1':x=haffTree[x].rightChild;   
  break;   
  default:cerr<<"输入出错!";break;   
  }   
                          k++;i=k;   
  }   
  else   
  {   
  cout<<haffTree[x].ch;   
  p=1;   
  }   
  }   
  }   
    
        }     
    
  void   main()   
  {         
          static   char   ch[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',':',';','   ','?','!'};     
          int   i,j;   int   n=31;   
    
  int   weight[]={64,13,22,32,103,21,15,47,57,1,5,33,20,58,63,16,2,48,51,80,23,8,18,3,16,4,100,186,96,164,134};   
          HaffNode   *myHaffTree=new   HaffNode[2*n-1];   
  Code   *myHaffCode=new   Code[n];   
  if(n>MaxN)   
  {   
  cout<<"定义的n越界,修改MaxN"<<endl;   
  exit(1);   
  }   
  Haffman(ch,weight,n,myHaffTree);   
  HaffmanCode(myHaffTree,ch,n,myHaffCode);   
            
          //输出每个叶结点的哈夫曼编码   
  for(i=0;i<n;i++)   
  {         
  cout<<"编码的字符："<<myHaffTree[i].ch<<"       ";   
  cout<<"Weight   =   "<<myHaffCode[i].weight<<"     Code   =   ";   
  for(j=myHaffCode[i].start+1;j<n;j++)   
  cout<<myHaffCode[i].bit[j];   
          cout<<endl;   
    
  }   
          char   str[200];int   k,p;   
            
              
            cout<<"请输入要编码的电文:"<<endl;   
              
    cin.getline(str,200,'\n');   
            
  cout<<"编码后输出为：   ";   
  for(p=0;p<n;p++)   
          {         
  for(k=0;k<n;k++)   
                  if(str[p]==ch[k])       
                  {     
      for(int   t=myHaffCode[k].start+1;t<n;t++)   
      cout<<myHaffCode[k].bit[t];   
                
                  }   
  }   
          cout<<endl;cout<<"编码结束。";cout<<endl;   
    
            char   data[200];   
    
    cout<<"请输入要编译的电文序列:"<<endl;   
    cin.getline(data,200,'\n');//>>data[10];   
            //cin.getline(data,10,'\n');//>>data[10];   
      
    cout<<"译码后输出为："<<endl;   
              int   m=strlen(data);   
            trans(myHaffTree,n,m,data);cout<<endl;   
                cout<<"译码结束。";cout<<endl;   
  }