hf.cpp

用C语言实现哈夫曼编码

#include<iostream.h> 
#include<string.h> 
#include<stdlib.h> 
#include<stdio.h> 
#include<malloc.h> 
#include<ctype.h> 
//定义结点结构 
typedef struct { 
        char ch; 
        unsigned int weight; 
        unsigned int parent, lchild,rchild; 
}htnode, *huffmantree;//动态分配数组存储哈夫曼树 
typedef char** huffmancode; //动态分配数组存储哈夫曼编码表 
int n, i; 
char str[100]; 
char coding[1000]; 
char inputchar()//字符输入 
{ 
        char st[80]; 
  gets(st); 
  if(st[1]==NULL) 
     return(st[0]); 
  else return ('45'); 
} 
int inputint()//整型输入 
{ 
        char st[87];int i,p=0; 
  gets(st); 
for(i=0;i<87;i++) 
  { 
           if(st[i]!=NULL) 
          if((st[i]>47)&&(st[i]<58)) 
             p=p*10+st[i]-48; 
         else 
         return(0); 
         else return(p); 
} 
} 
void select(huffmantree ht,int j,int*s1,int*s2) 
{ 
     int i; 
    (*s1)=(*s2)=0; 
    for(i=1;i<=j;i++) 
{ 
                  if(ht[i].weight<ht[(*s2)].weight&&ht[i].parent ==0&&(*s2)!=0) 
  { 
                          if(ht[i].weight<ht[(*s1)].weight) 
          { 
                                  (*s2)=(*s1); 
                      (*s1)=i; 
                          } 
                else (*s2)=i; 
                  } 
        if(((*s1)==0||(*s2)==0)&&ht[i].parent ==0) 
{ 
                if((*s1)==0) (*s1)=i; 
      else if((*s2)==0) 
{ 
                        if(ht[i].weight<ht[(*s1)].weight) 
{ 
                                (*s2)=(*s1); 
             (*s1)=i; 
                        } 
      else (*s2)=i; 
          } 
          } 
        } 
if(ht[(*s1)].weight >ht[(*s2)].weight ) 
{ 
            i=(*s1); 
     (*s1)=(*s2); 
        (*s2)=i; 
} 
return; 
} 
void huffmancoding(huffmantree *ht,huffmancode *hc,int)//哈夫曼函数 
{//初始化 
int m,j,k,w,s1,s2,f,start; 
char *cd; 
char c; 
cout<<"欢迎使用哈夫曼编码与译码器"<<endl; 
cout<<"请输入需要编码的字母的个数："<<endl; 
l:n=inputint(); 
//判断输入的是否为数字 
if(n<=1) 
{ 
        cout<<"输入错误!请输入大于1的正整数："<<endl; 
  goto l; 
} 
m=2*n-1; 
(*ht)=(huffmantree)malloc((m+1)*sizeof(htnode)); 
for(i=1;i<=n;i++) 
{ 
        cout<<"请输入第"<<i<<"个字母："<<endl; 
  loop:c=inputchar(); 
   if(c!=' ') 
         { 
         k=isalpha(c);  //判断输入的是否是字母 
        if(k==0) 
        { 
                cout<<"输入错误！请输入字母:"<<endl; 
        goto loop; 
        } 

  else { 
                for(k=1;k<i;k++)//判断是否是相同字母 
                { 
                        if((*ht)[k].ch==c) 
        { 
                                cout<<"错误!，您输入相同的字母,请重新输入第"<<i<<"个不同的字母："<<endl; 
             goto loop; 
                        } 
                } 
        } 
} 
(*ht)[i].ch=c; 
        cout<<"请输入每个字母相对应的权值："<<endl; 
w: w=inputint(); 
if(w==0)       //判断输入的是否为数字 
        { 
           cout<<"错误!请输入大于0的正整数："<<endl; 
    goto w; 
} 
  (*ht)[i].weight=w; 
  (*ht)[i].parent=0; 
  (*ht)[i].lchild=0; 
  (*ht)[i].rchild=0; 
  } 
for (;i<=m;i++) 
{ 
        (*ht)[i].parent=0; 
  (*ht)[i].lchild=0; 
  (*ht)[i].rchild =0; 
  (*ht)[i].ch=0; 
  (*ht)[i].weight=0; 
} 
for(i=n+1;i<=m;i++)//构造哈夫曼树 
{ 
        select(*ht,i-1,&s1,&s2); 
        (*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;} 
        cout<<"字母"<<"    "<<"权值"<<"    "<<"父亲"<<"    "<<"左孩子"<<"   " <<"右孩子"<<endl; 
        for(i=1;i<=n;i++) 
  cout<<(*ht)[i].ch<<"       "<<(*ht)[i].weight<<"       "<<(*ht)[i].parent <<"        "<<(*ht)[i].lchild <<"       "<<(*ht)[i].rchild <<endl; 
        for(i=n+1;i<=m;i++) 
  cout<<"        "<<(*ht)[i].weight<<"        "<<(*ht)[i].parent <<"       "<<(*ht)[i].lchild <<"        "<<(*ht)[i].rchild <<endl; 
(*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++) 
cout<<(*ht)[i].ch<<"  "<<(*hc)[i]<<endl; 
} 

void out(huffmantree ht,char *in){ 
int k,p,j; 
cout<<"请输入编码"<<endl; 
i=2*n-1; 
gets(in); 
cout<<"您的译码结果是:"<<endl; 
for(j=0;j<=strlen(in);) 
{ 
k=in[j]; 
if(i==2*n-1) 
{ 
if('0'==k)i=ht[i].lchild; 
else i=ht[i].rchild; 
j++; 
} 
else{if(ht[i].lchild==0){p=i; 
cout<<ht[p].ch; 
i=2*n-1; 
} 
else{if('0'==k)i=ht[i].lchild; 
else i=ht[i].rchild; 
j++; 
} 
} 
} 
} 
void main() 
{ 
huffmantree ht; 
huffmancode hc; 
char stri[1000]; 
huffmancoding(&ht,&hc,n); 
out(ht,stri); 
cout<<endl; 
cout<<"谢谢使用哈夫曼译码!"<<endl; 
}