aching.c

本程序以数据结构为基础 通过对文件的读写 然后进行的一个 HUFFMAN的编译码

                       #include <stdio.h>
#include <string.h>
#define n 128
#define m 2*n-1

typedef struct{
 char ch;
 char bits[100];
 int len;
 }CodeNode;
typedef CodeNode HuffmanCode[n+1];

typedef struct{
 int weight;
 int lchild,rchild,parent;
 }HTNode;
typedef HTNode HuffmanTree[m+1];
int num;



/*读取文件*/
int read_message(char s1[])
{
    FILE *fp;
    int i=0;
    char ch;
    if((fp=fopen("E:\\huffmantree.txt","rt"))==NULL)
    {
        printf("不能打开文件!\n");
        exit(1);
    }
    printf("文件内容:");
    ch=fgetc(fp);
    while(ch!=EOF)
    { putchar(ch);
       s1[i]=ch;
       ch=fgetc(fp);
       i++;
    }
    fclose(fp);
    getch();
}



/*建立哈夫曼树的三个函数*/
void select(HuffmanTree T,int k,int *s1,int *s2)          /*选取最小的值*/
{
    int i,j;
    int min=32767;
    for(i=1;i<=k;i++)
    { if(T[i].weight<min&&T[i].parent==0)
        {
            j=i;
            min=T[i].weight;
        }
        *s1=j;
    }
    min=32767;
    for(i=1;i<=k;i++)
    { if(T[i].weight<min&&T[i].parent==0&&i!=(*s1))
        {   j=i;
            min=T[i].weight;
        }
    }
    *s2=j;
}



int pinlv(char *s,int cnt[],char str[])
{
    char *p;
    int i,j,k=0;
    int temp[128]={0};
    for(p=s;*p!='\0';p++)
    {
        if(*p>=' '&&*p<=127)
      {
          k=*p-31;
          temp[k]++;
      }
    }
    for(i=1,j=0;i<=127;i++)
    {
        if(temp[i]!=0)
     {
        str[++j]=i+31;
        cnt[j]=temp[i];
     }
    }
    str[j+1]=0;
    return j;
}



void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[])
{
    int i,s1,s2;

    for(i=1;i<=2*num-1;i++)
    {
        HT[i].lchild=0; HT[i].rchild=0;
        HT[i].parent=0; HT[i].weight=0;
    }
    for(i=1;i<=num;i++)
    {
        HC[i].ch=str[i];
        HT[i].weight=cnt[i];
    }
    for(i=num+1;i<=2*num-1;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;
    }
}



/*生成哈夫曼编码文件的两个函数*/
void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC)
{
    int c,p,i;
    char cd[n];
    int start;
    cd[num]='\0';
    for(i=1;i<=num;i++)
    {
        start=num;
        c=i;
        while((p=HT[c].parent)>0)
      {
        cd[--start]=(HT[p].lchild==c)? '0':'1';
        c=p;
      }
    strcpy(HC[i].bits,&cd[start]);
    HC[i].len=num-start;
    }
}



void coding(HuffmanCode HC,char *str)
{
    int i,j;
    FILE*fp;
    fp=fopen("codefile.txt","w");
    while(*str)
    {
        for(i=1;i<=num;i++)
        if(HC[i].ch==*str)
        {
            for(j=0;j<HC[i].len;j++)
            fputc(HC[i].bits[j],fp);

            break;
        }
        str++;
    }
fclose(fp);
}



/*输出字符统计及编码表*/
void output(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[])
{
    int i=1;
    printf("\n字符   频数   编码");
    while(i<=num)
     printf("\n%1c     %2d      %4s",str[i-1],cnt[i++],HC[i].bits);
}



/*输出哈夫曼编码*/
int read_me()
{
    FILE *fp;
    int i=0;
    char ch;
    if((fp=fopen("codefile.txt","rt"))==NULL)
    {
        printf("不能打开文件!\n");
        exit(1);
    }
    printf("\n");
    ch=fgetc(fp);
    while(ch!=EOF)
    { putchar(ch);

       ch=fgetc(fp);
       i++;
    }
    fclose(fp);
    getch();
}



/*电文的译码*/
void  decode(HuffmanCode HC)
 {
    FILE*fp;
    char str[10000];
    static char cd[n+1];
    int i,j,k=0,cjs;
    fp=fopen("codefile.txt","r");
    while(!feof(fp))
   {
      cjs=0;
      for(i=0;i<num&&cjs==0&&!feof(fp);i++)
     {
        cd[i]=' ';cd[i+1]='\0';
        cd[i]=fgetc(fp);
        for(j=1;j<=num;j++)
        if(strcmp(HC[j].bits,cd)==0)
        {   str[k++]=HC[j].ch;
            cjs=1;
            break;
        }
     }
   }
   str[k]='\0';
   close(fp);
   fp=fopen("yima.txt","wt");
   printf("\n");
   fputs(str,fp);
   puts(str);
   fclose(fp);
}



void main()
{
   char st[10000]={0},*s,str[128]={0};
   int cn[128]={0};
   int choice;
   HuffmanTree HT;
   HuffmanCode HC;




   do
   {
      clrscr();
      printf(" \t\t****************哈夫曼编/解码工具******************\n\n\n");
      printf(" \t\t                1.读取文件\n\n");
      printf(" \t\t                2.字符统计\n\n");
      printf(" \t\t                3.输出编码\n\n");
      printf(" \t\t                4.输出译码\n\n");
      printf(" \t\t                0.退出系统\n\n");
      printf(" \t\t                请选择(0-4):");
      scanf("%d",&choice);
      switch(choice)
     {
       case 1: clrscr();
               read_message(st);break;
       case 2:
               clrscr();
               read_message(st);
               num=pinlv(st,cn,str);
               ChuffmanTree(HT,HC,cn,str);
               HuffmanEncoding(HT,HC);
               output(HT,HC,cn,str);
               getch();break;
       case 3:
               clrscr();
               read_message(st);
               num=pinlv(st,cn,str);
               ChuffmanTree(HT,HC,cn,str);
               HuffmanEncoding(HT,HC);
               coding(HC,st);
               printf("\n编码内容:");
               read_me();
               getch();break;
       case 4:
               clrscr();
               read_message(st);
               num=pinlv(st,cn,str);
               ChuffmanTree(HT,HC,cn,str);
               HuffmanEncoding(HT,HC);
               coding(HC,st);
               printf("\n译码文件:");
               decode(HC);
               getch();break;

       case 0:break;
      }
    }  while(choice!=0);

}