hafuman编码.c

来自「哈夫曼编码（hufuman code）c实现」· C语言 代码 · 共 236 行

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define leave 256
#define bignumber 987654321
#define max 256
int  n=0; /* 叶子树*/
int  m=0 ; /* 结点总数*/
char s[1000];/*输入字符串*/
int len;/*字符串长度*/
/***************统计字符与其频率的结构********/
struct letters
{
    char ch;
    int weight;
}letter[max];
/**************Huffman树的结构类型*************/
/* huffman树的静态三叉链表表示*/
typedef struct
{
    /* 结点型*/
    int weight; /* 权值*/
    int lchild; /* 左孩子链*/
    int rchild; /* 右孩子链*/
    int parent; /* 双亲链*/
}
HTNODE;
typedef HTNODE* HuffmanT;
HuffmanT T;
/************编码的结构类型************/
typedef struct
{
    char  ch;   //存储字符
    char  bits[leave+1]; //字符编码位串
}
CodeNode;
typedef CodeNode *HuffmanCode;
HuffmanCode H;
/****************************************/

void InitHT(HuffmanT T);//初始化
void InputW(HuffmanT T);/* 输入权值*/
void SelectMin(HuffmanT T,int k, int *p1,int * p2);//选择最小权值和次小权值

void CreartHT(HuffmanT T)/*构造huffam树，T[m-1]为其根*/
{
    int i ,p1 ,p2;

    InitHT(T);
    InputW(T);
    for (i = n;i < m;i++)
    {
        /*  n-1次合并最小和次小权值*/
        SelectMin(T, i-1, &p1, &p2);
        T[p1].parent =T[p2].parent = i ;
        T[i].lchild= p1;
        T[i].rchild= p2;
        T[i].weight =T[p1].weight + T[p2].weight;
    }
}
/*初始化huffman树，权值初始为0，父节点与儿子结点初始为-1*/
void InitHT(HuffmanT T)
{
    int i;

    for (i=0;i<m;i++)
    {
        T[i].weight=0;
        T[i].lchild=T[i].rchild=T[i].parent=-1;
    }
}
/********************根据字符频率，输入权值********************************/
void InputW(HuffmanT T)
{
    int i;
    for (i=0;i<n;i++)
    {
        T[i].weight=letter[i].weight;
    }
}
/************选择已经构造的内节点和外接点之中最小的和次小的权值**********/
void SelectMin(HuffmanT T,int k, int *p1,int * p2)
{
    int a,min1=bignumber,min2=bignumber;
    for (a=0;a<=k;a++)
        if (T[a].weight<min1&&T[a].parent==-1)
        {
            *p1=a;//得到最小权值
            min1=T[a].weight;//临时存放最小权值
        }
    for (a=0;a<=k;a++)
        if ((T[a].weight<min2)&&T[a].parent==-1&&a!=*p1)
        {
            *p2=a;//得到次小权值
            min2=T[a].weight;//临时存放次小权值
        }
}
/***********统计出现的字符，并存入相应的权值*****************/
void weight_count(char *s,int len)
{
    int i,j,k;
    j=k=0;
    for (i=0;i<len;i++)//将统计出现字符的结构初始化
    {
        letter[i].ch='\0';
        letter[i].weight=0;
    }
    for (i=0;i<len;i++)
    {
        for (k=0;k<=j;k++)
        {
            if (letter[k].ch==s[i])
            {
                letter[k].weight++;//对于出现过的字符，进行频率统计
                break;
            }
        }
        if (k==j+1)
        {
            letter[j].ch=s[i];//没出现的字符要将之储存
            letter[j++].weight++;
        }
    }
    n=j;
}
/**************编码************************/
void CharSetHuffmanEncoding(HuffmanT T, HuffmanCode H)/*编码*/
{
    /*根据Huffman树T 求Huffman编码表 H*/
    int c, p, i,k;           /* c 和p 分别指示T 中孩子和双亲的位置*/
    char cd[n+1];           /* 临时存放编码*/
    int start;             /* 指示编码在cd 中的位置 */

    memset(cd,'\0',sizeof(cd));                      /* 存储空间初始化*/
    for ( i =0; i <n;  i++)
    {
        /* 依次求叶子T[i]的编码 */
        H[i].ch=letter[i].ch;                        /* 读入叶子T[i]对应的字符*/
        start=n;                                     /* 编码起始位置的初值*/
        c =i;                                        /* 从叶子T[i]开始上溯*/
        while ( (p=T[c].parent)>=0)
        {
            /* 直到上溯到T[c]是树根位置*/
            cd[--start]=(T[p].lchild==c)? '0' : '1'; /* 若T[c]是T[p]的左孩子，则生成代码0，否则生成代码1*/
            c=p;      /* 继续上溯*/
        }
        strcpy(H[i].bits,&cd[start]);                /*复制编码为串于编码表H*/
        printf("%-10c----------%10s\n",H[i].ch,H[i].bits);
    }
    printf("The %s\'s encoding text is:\n",s);       /*将加密的文本打印*/
    for (i=0;i<len;i++)
        for (k=0;k<n;k++)
            if (s[i]==H[k].ch)
                printf("%s",H[k].bits);
}
/**********************译码*********************/
void CharSetHuffmanDecoding(HuffmanT T, HuffmanCode H)
{
    int j=0;
    int start=m-1;//从树根开始查找

    while (s[j]!='\0')
    {
        if (s[j] == '0' && T[start].lchild != -1)//遇见0，向左儿子走
            start = T[start].lchild;
        else if (s[j] == '1' && T[start].rchild != -1)//遇见1，向右儿子走
            start = T[start].rchild;
        else
        {
            printf("%c", letter[start].ch);//如果走到了外结点，就打印该节点
            start = m - 1;
            j--;
        }
        j++;
    }
    printf("%c\n", letter[start].ch);//将最后一个字符打印
}
/********************主函数************************/
int main()
{
    char a;
    int i;
    /**************输入文本***********************/
    printf("Please input a english text:\n");
    while (gets(s)!=NULL)
    {

        len=strlen(s);
        weight_count(s,len);
        printf("\nThe letters\' frequence are:\n");
        for (i=0;i<n;i++)                                   /*打印频率的统计结果*/
            printf("%c %d\n",letter[i].ch,letter[i].weight);
        printf("The encoding letters are:\n");
        m=2*n-1;
        T=(HuffmanT)malloc(m*sizeof(HTNODE));               //为huffman树申请空间
        H=(HuffmanCode)malloc(n*sizeof(CodeNode));          //为huffman编码申请空间
        CreartHT(T);//建huffman树
        /*************encode*********************/
        CharSetHuffmanEncoding(T,H);                        //利用huffman树进行编码

        printf("\n\nDo you want to exist?(y to quit,n to decode):");
        if (getchar()=='y')//退出选择y
        {
            free(T);
            free(H);
            return 0;
        }
decode:
        getchar();//读入回车，消除影响
        /***********decode*****************/
        printf("Please input the encoding text that you want to decode.\n");
        gets(s);//输入01字符串
        CharSetHuffmanDecoding(T,H);//利用编完的huffman编码进行译码
        printf("\n\nDo you want to exist?(y to quit,\'1\' to encode,\'2\' to decode):");
        if ((a=getchar())=='y')//选择y退出
        {
            free(T);
            free(H);
            return 0;
        }
        else if (a=='1')//选择1进行编码
        {
            free(T);
            free(H);
            getchar();//读入回车，消除影响
            printf("Please input a english text:\n");
            continue;
        }
        else if (a=='2')//选择2进行译码
        {
            goto decode;
        }
    }
    return 0;
}