cpp1.cpp

这是一个哈夫曼编译器,是我学数据结构的时候老师要求做的一个作业

#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#define n 27      /* 字符集的容量 */
#define MAXVALUE 1000           /*权值的最大值*/
#define MAXNODE 35
#define MAXD 100

typedef struct    /* 字符集的元素结构 */
{char data;
 int weight;
}elemtype;

typedef struct    /* 哈夫曼树的元素结构 */
{char data;
 int flag;
 int weight;
 int parent,lchild,rchild;
}htnode,*huffmantree;
typedef char * *HuffmanCode;


void readdata(elemtype *w);
huffmantree createhuff(elemtype *w);
char * *huffmancode(huffmantree ht);
void encoding(huffmantree ht,char **hc);
void decoding(huffmantree ht);


void readdata(elemtype *w)
{ 
 w[0].data=' ' ;w[0].weight=186 ;
 w[1].data='a' ;w[1].weight=64 ;
 w[2].data='b' ;w[2].weight=13 ;
 w[3].data='c' ;w[3].weight=22 ;
 w[4].data='d' ;w[4].weight=32 ;
 w[5].data='e' ;w[5].weight=103 ;
 w[6].data='f' ;w[6].weight=21 ;
 w[7].data='g' ;w[7].weight=15 ;
 w[8].data='h' ;w[8].weight=47 ;
 w[9].data='i' ;w[9].weight=57 ;
 w[10].data='j' ;w[10].weight=1 ;
 w[11].data='k' ;w[11].weight=5 ;
 w[12].data='l' ;w[12].weight=32 ;
 w[13].data='m' ;w[13].weight=20 ;
 w[14].data='n' ;w[14].weight=57 ;
 w[15].data='o' ;w[15].weight=63 ;
 w[16].data='p' ;w[16].weight=15 ;
 w[17].data='q' ;w[17].weight=1 ;
 w[18].data='r' ;w[18].weight=48 ;
 w[19].data='s' ;w[19].weight=51 ;
 w[20].data='t' ;w[20].weight=80 ;
 w[21].data='u' ;w[21].weight=23 ;
 w[22].data='v' ;w[22].weight=8 ;
 w[23].data='w' ;w[23].weight=18 ;
 w[24].data='x' ;w[24].weight=1 ;
 w[25].data='y' ;w[25].weight=16 ;
 w[26].data='z' ;w[26].weight=1 ;


return;
}

huffmantree createhuff(elemtype *w)
{int i,j,x1,x2;
 int m1,m2,m;
 huffmantree HT,p;
 m=2*n-1;
 HT=(huffmantree)malloc((m+1)*sizeof(htnode));
 p=HT;p++;
 for(i=1;i<=m;i++,p++,w++)
  {if(i<=n)
    {
     p->data=w->data;
     p->weight=w->weight;
    }
   else
    {
     p->data='\0';
     p->weight=0;
    }
   p->parent=0;
   p->lchild=0;
   p->rchild=0;
   p->flag=0;
  }
 for(i=1;i<n;i++)
  {m1=m2=MAXVALUE;
   x1=x2=0;
   p=HT;
   for(j=1;j<=n-1+i;j++)
    {
     if(p[j].weight<m1&&p[j].flag==0)
      { m2=m1;
        x2=x1;
 	m1=p[j].weight;
	x1=j;
      }
     else if(p[j].weight<m2&&p[j].flag==0)
      { m2=p[j].weight;
 	x2=j;
      }
    }
   p[x1].parent=n+i;
   p[x2].parent=n+i;
   p[x1].flag=1;
   p[x2].flag=1;
   p[n+i].weight=p[x1].weight+p[x2].weight;
   p[n+i].lchild=x1;
   p[n+i].rchild=x2;
  }
  
  return(HT);

}


HuffmanCode huffmancode(huffmantree ht)
{ char* cd;
  int c,i,f,start;
  HuffmanCode HC;
  HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
  cd=(char*)malloc(n*sizeof(char));
  cd[n-1]='\0';
  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]);
   }
/* for(i=1;i<=n;i++)
  puts(HC[i]);
*/
  free(cd);
 return(HC) ;
}

void encoding(huffmantree ht,char **hc)
{int i,j,k;
 char sstring[MAXNODE] ;
 
 flushall();
cout<<"翻译字母"<<endl<<"例如，键入i love c programme按回车就会翻译出代码"<<endl;
 gets(sstring);
 for(i=0;i<strlen(sstring);i++)
  {for(j=1;j<=n;j++)
    if(sstring[i]==ht[j].data)
      {k=j;
       break;
      }
    if(k<=0||k>MAXNODE)
      {printf("there isn't NO.%d char\n",i);
       continue;
      }
   printf("%c\tweight=%3d\t%s\n",ht[k].data,ht[k].weight,hc[k]);
  }
}








void decoding(huffmantree ht)
{char a[MAXD];
 int m,i;
 cout<<"代码值翻译成字母"<<endl<<"例如键入1010按回车就会出现相应的字母a"<<endl;
 scanf("%s",a);
 m=2*n-1;
 for(i=0;a[i]!='\0';i++)
    {if(a[i]=='0') m=ht[m].lchild;
     else m=ht[m].rchild;
     if(m<=n)
      {printf("%c",ht[m].data);
       m=2*n-1;
      }
    }
}



void main()
{elemtype w[n];               /* 字符和频度集合类型 */
 char ch;
 huffmantree ht;            /* 哈夫曼树类型 */
 HuffmanCode hc;             /* 编码类型 */
 cout<<"哈夫曼编译器"<<endl<<"********菜单***********"<<endl<<"键入q退出程序"<<endl<<"键入e，翻译字母"<<endl<<"键入d,代码值翻译成字母"<<endl;
readdata(w); /* 初始化(readdata)，读取数据 */
ht=createhuff(w); /* 建立哈夫曼树(createhuff) */
 cin>>ch;
 while(ch!='q')             /* 当键入’q’时程序运行结束 */
  {
   while(ch!='e'&&ch!='d'&&ch!='q')
   cin>>ch;                             /* 选取功能 */
   switch(ch)
   {          
           
    case 'e': hc=huffmancode(ht);encoding(ht,hc);break;
              /* 求字符集的哈夫曼编码(huffmancode)和求测试数据的编码(encoding)*/
    case 'd': decoding(ht);break;       /* 译码(decoding) */
    case 'q': return;                 /* 程序结束，返回 */
  }
 cin>>ch;
 }
}