哈夫曼编译码器的实现使用文件

客官°小女子只卖身不卖艺 2022-08-19 01:52 127阅读 0赞

两天做出的哈夫曼编译码器 还算稳定 只有一个字符的时候不能实现

//============================================================================
    // Name : katherine
    // Author : katherine
    // Version : 1.0    2015-12-27 22:09:05
    // Copyright : made by katherine
    // Description : Ansi-style
    // Last Modified time : 2015-12-30 12:07:32
    //============================================================================
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <conio.h>
    
    #define N 100
    #define M 2*N-1
    #define EOF (-1)
    
    typedef struct Huffmantree
    {
        char data;
        int weight;
        int parent;
        int lchild;
        int rchild;
    }HuffmanTree[M];//哈夫曼树存储节点结构体
    
    typedef struct Huffmancode
    {
        char data;
        char bits[N];
    }HuffmanCode[N];//哈夫曼编码的存储结构体
    
    typedef struct  str
    {
        char data;
        char num;
    }str;//字符数组
    int read(str s2[],char name[]);
    void SelectMin(HuffmanTree ht,int i,int *p1,int *p2);
    void CrtHuffmanTree(HuffmanTree ht,str s[],int n);
    void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int k);
    void WriteToFile(HuffmanCode hc,int n,char name[],char name1[]);
    void DecodeHuffmanCode(HuffmanTree ht,int n,char name1[],char name2[]);
    void compare(int n,char name[],char name2[]);
    int main() {
        int k,;
        HuffmanTree ht;
        HuffmanCode hc;
        str s2[128];
    
        char name[30];
        char name1[30];
        char name2[30];
        printf("Please enter the filename you need coding:  \n");
        scanf("%s",name);
        k = read(s2,name);
        CrtHuffmanTree(ht,s2,k);
        CrtHuffmanCode(ht,hc,k);
        printf("Please enter the filename you need save:  \n");
        scanf("%s",name1);
        WriteToFile(hc,k,name,name1);
        printf("Please enter the filename you need save decoding:  \n");
        scanf("%s",name2);
        DecodeHuffmanCode(ht,k,name1,name2);
    
        compare(k,name,name2);
        getchar();
    }
    int read(str s2[],char name[])
    {
        FILE *fp;//声明fp是指针，用来指向FILE类型的对象
        char ch;
        int i;
        int k;
        str s1[128];
        for (i = 0; i <128; i++)
        {
            s1[i].data =0;
            s1[i].num =0;
            s2[i].data =0;
            s1[i].num =0;
    
        }
        if((fp=fopen(name,"r"))==NULL)// fopen标准函数
        {
            printf("File open failed\n");
            getch();
            exit(1);
        }
        printf("The string to read is:\n");
        ch  = fgetc(fp);
        while(!feof(fp))
        {
            printf("%c",ch);
            s1[ch].num++;
            s1[ch].data = ch;
            ch  = fgetc(fp);//自动移动机制
        }
        fclose(fp);
        for (i=1,k=0;i<=128;i++)
        {
            if(s1[i].num!=0 )
            {   k++;
                s2[k].num = s1[i].num;
                s2[k].data = s1[i].data;
            }
        }
        printf("\nStatistical results are:\n");
        printf("\n<character   Code> \n");
        for(i=1;i<=k;i++)
        {
            printf("<%c            %d>\n",s2[i].data,s2[i].num);
        }
        printf("There are %d kinds of characters\n",k);
        return k ;
    }
    
    void SelectMin(HuffmanTree ht,int i,int *p1,int *p2)
    {
        int j,min1,min2;
        min1 = min2 =-1;
        for (j=1;j<=i;j++)
        {
            if(ht[j].parent == 0)//找到还未加入到树里面的节点
            {
                if(ht[j].weight<min1||min1==-1)//找小的或者还没有赋给权值的
                {
                    if(min1!=-1)
                    {
                        min2=min1;//min1总是最小的那个
                        *p2=*p1;//p1总是指向最小的那个
                    }
                    min1 = ht[j].weight;//先赋给权值
                    *p1=j;
    
                }
                else if(ht[j].weight<min2||min2==-1)
                {
                    min2=ht[j].weight;
                    *p2=j;
                }
            }
        }
    }
    
    void CrtHuffmanTree(HuffmanTree ht,str s[],int n)
    {
        int i,m,p1,p2;
        for (i=1;i<=n;i++)
        {
    
            //strcpy(ht[i].data,&s[i].data);
            ht[i].data = s[i].data;
            printf("%c ",ht[i].data);
            ht[i].weight= s[i].num;
            ht[i].parent=0;
            ht[i].lchild=0;
            ht[i].rchild = 0;
        }
        m = 2*n-1;
        for (i = n+1;i<=m;i++)
        {
            //strcpy(ht[i].data,NULL);
            ht[i].data=0;
            ht[i].weight=0;
            ht[i].parent = 0;
            ht[i].lchild=0;
            ht[i].rchild=0;
        }
        for (i = n+1;i<=m;i++)
        {
            SelectMin(ht,i-1,&p1,&p2);
            ht[i].weight=ht[p1].weight+ht[p2].weight;
            ht[p1].parent=i;
            ht[p2].parent=i;
            ht[i].lchild=p1;
            ht[i].rchild=p2;
        }
        printf("\nThe establishment of the Huffman tree for:\n");
        printf("number\tdata\tweight\tlchild\trchild\tparent\n");
        for(i=1;i<=n;i++)
        {
            printf("%d:\t%c\t%d\t%d\t%d\t%d\n",i,ht[i].data,ht[i].weight,ht[i].lchild,ht[i].rchild,ht[i].parent);
        }
    
    }
    
    void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int k)
    {
        int c,p,i;
        char cd[N+1];
        int start;
        for(i=1;i<=k;i++)
        {
            //strcpy(hc[i].data,&ht[i].data);
            hc[i].data = ht[i].data;
            start = k-1;//深度
            cd[start] = '\0';
            c=i;
            while((p=ht[c].parent)!=NULL)
            {
                cd[--start] = (ht[p].lchild==c)?'0':'1';
                c=p;
            }
            strcpy(hc[i].bits,&cd[start]);
    
        }
        printf("\n\nEach character corresponds to the encoding:\n");
        for(i=1;i<=k;i++)
            printf("<%d     %c     %s>   \n",i,hc[i].data,hc[i].bits);
    }
    
    void WriteToFile(HuffmanCode hc,int n,char name[],char name1[]){
        FILE *fp1,*fp2;
        char ch;
        int i;
    
        if((fp1=fopen(name,"r"))==NULL)
        {
            printf("File open failed");
            getch();
            exit(1);
        }
        if((fp2=fopen(name1,"w"))==NULL)
        {
            printf("File open failed");
            getch();
            exit(1);
        }
        ch = fgetc(fp1);
        while(ch!=EOF)
        {
            for(i=1;i<=n;i++)
            if(ch==hc[i].data)
            {
            fputs(hc[i].bits,fp2);
            }
            ch = fgetc(fp1);
        }
        fclose(fp1);
        fclose(fp2);
    
        printf("File save Success\n");
    
    }
    void DecodeHuffmanCode(HuffmanTree ht,int n,char name1[],char name2[])
    {
        FILE *fp1,*fp2;
        char ch;
        int p,k;
    
        if((fp1 = fopen(name1,"r"))==NULL)
        {
            printf("File open failed");
            getch();
            exit(1);
        }
        if((fp2= fopen(name2,"w"))==NULL)
        {
            printf("File open failed");
            getch();
            exit(1);
        }
        p = k = 2*n-1;
        ch = fgetc(fp1);
    
        while(!feof(fp1))
        {  if(ch=='0')
            {
                p = ht[p].lchild;
            }
            if(ch=='1')
            {
                p = ht[p].rchild;
            }
            if(ht[p].data!=0)
            {
                printf("%c",ht[p].data);
                fprintf(fp2,"%c",ht[p].data);
                p = k;
            }
            ch = fgetc(fp1);
        }
        printf("\n");
        fclose(fp1);
        fclose(fp2);
    }
    void compare(int n,char name[],char name2[])
    {
        FILE *fp1,*fp2;
        char s1[N], s2[N];
        int i = 1,j = 1;
        if((fp1 = fopen(name,"rt"))==NULL)
        {
            printf("File open failed");
            getch();
            exit(1);
        }
        if((fp2= fopen(name2,"rt"))==NULL)
        {
            printf("File open failed");
            getch();
            exit(1);
        }
        printf("Source file is:");
        for(i=1;(s1[i]=fgetc(fp1))!=EOF;i++)
        {
            printf("%c",s1[i]);
        }
        printf("\nDeCode file is:");
        for(i=1;(s2[i]=fgetc(fp2))!=EOF;i++)
        {
            printf("%c",s1[i]);
        }
        printf("\n");
        fclose(fp1);
        fclose(fp2);
        while(j<n)
        {
            if(s1[j]==s2[j])
            {
               j++;
            }
            else
            {
                printf("Sorry compiler failed\n");
                break;
            }
        }
        if(j==n)
        {
            printf("*****Congratulations to compile successfully*****");
        }
        getch();
    }