huffman.c

一个完整的哈夫曼c代码

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <ctype.h>
#include <string.h>


/*树结构和全局结构指针*/
struct node
{
    int num;/*结点编号*/
    char c;
    int weight;
    int parent;
    int lchild,rchild;
}*ht;

/*常量文件名*/
const char *TableFileName    = "HfmTbl.txt";
const char *SourceFileName   = "SrcText.txt";
const char *CodeFileName     = "HfmCode.txt";
const char *DecodeFileName   = "DecodeText.txt";
const char *TreeViewFileName = "TreeView.txt";
/*打印格式字符串常量*/
const char *PrintFormatStr = "%4d %13c %13d %13d %13d %13d\r\n";
/*读取格式字符串常量*/
const char *ReadFormatStr  = "%d %c %d %d %d %d";
/*打印参数宏*/
#define PRINT_PARAM(i) ht[(i)].num,ht[(i)].c,ht[(i)].weight,ht[(i)].parent,ht[(i)].lchild,ht[(i)].rchild
/*读取参数宏*/
#define READ_PARAM(i) &ht[(i)].num,&ht[(i)].c,&ht[(i)].weight,&ht[(i)].parent,&ht[(i)].lchild,&ht[(i)].rchild
/*打印格式和参数宏*/
#define READ_FORMAT_PARAM(i) ReadFormatStr,READ_PARAM(i)
/*读取格式和参数宏*/
#define PRINT_FORMAT_PARAM(i) PrintFormatStr,PRINT_PARAM(i)

/*内存交换函数，用于结构体变量交换*/
void MemSwap(void *buf1, void *buf2, size_t buflen)
{
    if(buf1!=buf2)
    {
        void *p = malloc(buflen);
        memmove(p,buf1,buflen);
        memmove(buf1,buf2,buflen);
        memmove(buf2,p,buflen);
        free(p);
    }
}

/*打印表*/
void PrintHT(int from, int to)
{
    int i;
    for(i=from;i<=to;i++)
    {
        printf(PRINT_FORMAT_PARAM(i));
    }
    printf("\n");
}
/*选择法排序*/
void SelectSort(int from, int to)
{
    int i,j,k;
    for(i=from;i<to;i++)  /*sort */
    {
        for(k=i,j=i+1;j<=to;j++)
            if(ht[j].weight<ht[k].weight)
                k=j;
        if(k!=i)
            MemSwap(&ht[k],&ht[i],sizeof(struct node));
        PrintHT(from,to);
    }
}

/*释放ht*/
void free_ht()
{
    if(ht != NULL)
    {
        free(ht);
        ht = NULL;
    }
}

/*从文件读取数据保存到全局堆中，调用后记得释放*/
int ReadFromFile()
{
    int i;
    int m;
    FILE *h;
    
    if((h=fopen(TableFileName,"r"))==NULL)
    {
        printf("不能打开 %s\n", TableFileName);
        getch();
        return 0;
    }
    fscanf(h,"%d",&m);
    free_ht();
    ht=(struct node *)calloc(m+1,sizeof(struct node));
    for(i=1;i<=m;i++)
    {
        fscanf(h,READ_FORMAT_PARAM(i)); //fscanf(h,"%d %c %d %d %d %d",&ht[(i)].num,&ht[(i)].c,&ht[(i)].weight,&ht[(i)].parent,&ht[(i)].lchild,&ht[(i)].rchild);
    }
    fclose(h);
    return m;
}

/*吃掉无效的垃圾字符*/
void EatCharsUntilNewLine()
{
    while(getchar()!='\n') 
        continue; 
}

/*按节点序号重新排序*/
void SortByNum(int m)
{
    int i = 0, j;
    size_t len = sizeof(struct node);
    for(i = 1; i < m; i ++)
    {
        for(j = i + 1; j <= m; j ++ )
        {
            if (ht[j].num == i)
            {
                MemSwap(&ht[i],&ht[j],len);
                break;
            }
        }
    }
}

/*初始化并写入文件*/
void Initialize()
{
    int i=0,x=0,y=0,n,m;
    FILE *h;

    puts("请输入总共会会出现的字符数 n:");
    scanf("%d",&n);
    EatCharsUntilNewLine();


    m=2*n-1;	/*  一开始有n个初始节点，最后有2n-1个节点。*/

    ht=(struct node *)calloc(m+1,sizeof(struct node));	、/*     分配m+1个节点，第0个节点不使用。*/

    /*遍历叶子结点进行初始化*/
    for(i=1;i<=n;i++)
    {
        puts("请输入一个字符:");
        scanf("%c",&ht[i].c);
        EatCharsUntilNewLine();
        
        puts("请输入该字符的权值:");
        scanf("%d",&ht[i].weight);        
        EatCharsUntilNewLine();

        ht[i].num=i;
    }
    PrintHT(1,n);

    for(i=n+1;i<=m;i++) /*添加树干*/
    {
        ht[i].c='#';
        ht[i].num=i;
    }
    PrintHT(n+1,m);

    SelectSort(1,n); /*用选择法将第1到n个元素从小到大排序*/
    PrintHT(1,n);

    for(x=1,i=n+1;i<=m;i++,x+=2)   /*构建huffman树，精华所在*/
    {
        y=x+1;
        ht[x].parent=ht[y].parent=i;
        ht[i].lchild=ht[x].num;
        ht[i].rchild=ht[y].num;
        ht[i].weight=ht[x].weight+ht[y].weight;
        SelectSort(1, i); /*排序*/
    }

    /*察看排序效果*/
    PrintHT(1,m);
    getch();

    SortByNum(m);
    /*察看恢复序号效果*/
    PrintHT(1,m);
    getch();
    
    /*数据写入文件并输出至屏幕*/
    if((h=fopen(TableFileName,"wb"))==NULL)
    {
        printf("不能写入文件%s\n", TableFileName);
        getch();
        return;
    }
    printf("哈夫曼树为:\n");
    printf("  结点号         字符         权值          父结点        左孩子        右孩子\n");

    /*首行写入数据行数*/
    fprintf(h,"%d\r\n",m);
    /*循环写入每行同时向屏幕输出*/
    for(i=1;i<=m;i++)
    {
        printf(PRINT_FORMAT_PARAM(i));
        fprintf(h,PRINT_FORMAT_PARAM(i));
    }
    free_ht();
    fclose(h);
}


/*编码并写入文件*/
void Encode()
{
    int i,mm,c,f,start; /*mm定义为存储每个字符的密码*/
    char wr,*cd = (char *)NULL, ch;  /*cd用以存储编码*/
    char **HC = (char **)NULL;
    FILE *fp1, *fp2;
    int m = ReadFromFile();
    int n = (m+1)/2;  /*m为哈夫曼树的结点数，n为字符数*/
    
    if(HC!=NULL) free(HC);
    HC=(char **)calloc(n+1,sizeof(char *));  /*用与存储编码的结点，第0个不使用*/
    if(HC==NULL) return;

    if(cd!=NULL) free(cd);
    cd=(char *)calloc(n,sizeof(char));
    if(cd==NULL) return;

    for(i=1;i<=n;i++)   /*逐个求哈夫曼编码，精华所在*/
    { 
        start=n-1;   /*倒着求*/
        for(c=i,f=ht[i].parent; f!=NULL; 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]);
    }
    free(cd);
    
    for(i=1;i<=n;i++)
        printf("%c----%s\n",ht[i].c,HC[i]);

    printf("如果想输入文本进行加密，请按A或a,否者从文件%s中读取请按回车.\n",SourceFileName);
    printf("请选择：");
    scanf("%c",&wr);

 
    if(wr=='a'||wr=='A')
    {
        if((fp1=fopen(SourceFileName,"w+"))==NULL)
        { 
            printf("不能打开文件%s\n", SourceFileName);
            getch();
            return;
        }
        printf("请输入文本，按#结束输入。\n");
        ch=getch();
        while(ch!='#')
        { 
            fputc(ch,fp1);
            putchar(ch);
            ch=getch();
        }
        rewind(fp1);
        printf("\n");
    }
    else
    {
        if((fp1=fopen(SourceFileName,"r"))==NULL)
        { 
            printf("不能打开文件%s\n", SourceFileName);
            getch();
            return;
        }
    }
    if((fp2=fopen(CodeFileName,"w"))==NULL)
    {
        printf("不能建立文件%s\n", CodeFileName);
        getch();
        return;
    }
    while(!feof(fp1))
    { 
        ch=fgetc(fp1); /*从文件中取得字符*/
        for(i=1;i<=n;i++) 
            if(ht[i].c==ch) /*如果得到的字符和某个结点的字符一样*/
                for(mm=0;HC[i][mm]!='\0';mm++)
                {
                    fputc(HC[i][mm],fp2);
                    printf("%c",HC[i][mm]);
                }
    }
    printf("\n");
    for(i=1;i<=n;i++)
        fprintf(fp1,"\r\n%c----%s",ht[i].c,HC[i]);
    for(i=1;i<=n;i++)
        fprintf(fp2,"\r\n%s----%c",HC[i],ht[i].c);
    for(i = 1; i <= n; i ++)
    {
        free(HC[i]);
    }
    free(HC);
    free_ht();
    fclose(fp1);
    fclose(fp2);
}

 
/*解码写入文件并输出*/
void Decode()
{
    FILE *CodeFileP, *TextFileP;
    char ch = '\0';
    int f;
    int m = ReadFromFile();
    f = m;
    if((CodeFileP=fopen(CodeFileName,"r"))==NULL)
    {
        printf("不能打开编码后的文件%s\n", CodeFileName);
        getch();
        return;
    }
    if((TextFileP=fopen(DecodeFileName,"w"))==NULL)
    { 
        printf("不能建立解码后的文件%s\n", DecodeFileName);
        getch();
        return;
    }

    while(!feof(CodeFileP)&&ch!='\n')
    { 
        ch=fgetc(CodeFileP);  
        if(ch=='0')
            f=ht[f].lchild;
        if(ch=='1')
            f=ht[f].rchild;
        if(!ht[f].lchild&&!ht[f].rchild) 
        { 
            fputc(ht[f].c,TextFileP);
            printf("%c",ht[f].c);
            f=m; 
        }
    }
    free_ht();
    fclose(CodeFileP);
    fclose(TextFileP);
    printf("\n");
}
/*不解码直接输出文件中的huffman编码*/
void PrintCode()
{
    int i=0;
    char ch = 0;
    FILE *CodeFileP;
    if((CodeFileP=fopen(CodeFileName,"r"))==NULL)
    { 
        printf("不能打开编码后的文件%s\n",CodeFileName);
        getch();
        return;
    }
    while(!feof(CodeFileP)&&ch!='\n')
    { 
        if(i++==50)  /*每一行显示50个字符*/
        {
            printf("\n"); 
            i=0; 
        } 
        ch=fgetc(CodeFileP);
        printf("%c",ch);
    }
    printf("\n");
    fclose(CodeFileP);
}

 
/*输出Huffman树*/
void PrintTree()
{ 
    int i,k,top,p;
    int *level,*stack;
    FILE *TreePrintFileP;
    int m = ReadFromFile();
    int n = (m+1)/2;

    if((TreePrintFileP=fopen(TreeViewFileName,"w"))==NULL)
    { 
        printf("不能建立哈夫曼树文件%s\n", TreeViewFileName);
        getch();
        return; 
    }

    printf("哈夫曼树为：\n");
    fprintf(TreePrintFileP,"哈夫曼树为:\n");
    level=(int *)malloc(n*sizeof(int));
    stack=(int *)malloc(n*sizeof(int));

    if(m!=0) /*用栈的方法来输出*/
    { 
        top=1; 
        stack[top]=m;
        level[top]=2;
        while(top>0)
        {
            p=stack[top];   
            k=level[top];    
            for(i=1;i<=k;i++) 
            {
                printf(" ");
                fprintf(TreePrintFileP," ");
            }
            printf("%d",ht[p].weight);
            fprintf(TreePrintFileP,"%d",ht[p].weight);
            top--;
            if(ht[p].rchild!=0)
            { 
                top++; 
                stack[top]=ht[p].rchild; 
                level[top]=k+2;
                printf("\n");
            }
            if(ht[p].lchild!=0)
            {
                top++;
                stack[top]=ht[p].lchild; 
                level[top]=k-2;
            }
        }
    }
    free(level);
    free(stack);
    fclose(TreePrintFileP);
}


 
int prompt()
{
    char en;
    puts("\n\t********************* 用哈夫曼树对文件进行编码与解码 *****************");
    puts("\t*                                                                    *");
    puts("\t*i/I---初始化（首先）  e/E---编码输入      d/D---解码输出            *");
    puts("\t*t/T---打印哈夫曼树    p/P---不解码输出    q/Q---退出程序            *");
    puts("\t*                                                                    *");
    puts("\t********************* 用哈夫曼树对文件进行编码与解码 *****************");
    puts("请选择各功能选项，按字母继续：");
    printf(">>>>>>>>");
    scanf("%c",&en);
    EatCharsUntilNewLine();
    return tolower(en);
}

void main()
{
    while(1)
    {
        switch(prompt())
        {
            case 'i':
                Initialize();
                break;
            case 'e':
                Encode();
                break;
            case 'd':
                Decode();
                break;
            case 'p':
                PrintCode();
                break;
            case 't':
                PrintTree();
                break;
            case 'q':
                free_ht();
                return;
        }
    }
}