哈夫曼编码及译码

#include<stdio.h>

#include<conio.h>

#define MAXVALUE 1000          //最大权值

#define MAXLEAF 30             //最大叶结点个数

#define MAXNODE MAXLEAF*2-1    //最大结点个数

#define MAXBIT 50              //编码的最大长度

typedef struct node{

    char letter;      //字符

    int weight;       //权值

    int parent;       //父母结点

    int lchild;       //左孩子结点

    int rchild;       //右孩子结点

}HNodeType;

typedef struct{

    char letter;         // 字符

    int bit[MAXBIT];     //数组，存放字符的哈夫曼编码

    int start;           //该编码在数组bit的开始位置

}HCodeType;

typedef struct{

    char s;

    int num;

}Message;

void HuffmanTree(HNodeType HuffNode[],int n,Message a[])

{

    int i,j,m1,m2,x1,x2,temp1;

    char temp2;

    for(i=0;i<2*n-1;i++)      //哈夫曼树初始化

    {

        HuffNode[i].letter=NULL;

        HuffNode[i].weight=0;

        HuffNode[i].parent=-1;

        HuffNode[i].lchild=-1;

        HuffNode[i].rchild=-1;

     }

    for(i=0;i<n-1;i++)   //n等于不同字符的个数

    for(j=i+1;j<n-1;j++)    //按照重复个数大小对字符排序

    if(a[j].num>a[i].num)   

    {

        temp1=a[i].num;

        a[i].num=a[j].num;

        a[j].num=temp1;

        temp2=a[i].s;

        a[i].s=a[j].s;

        a[j].s=temp2;

     }

     for(i=0;i<n;i++)

     {

         HuffNode[i].weight=a[i].num;    //将字符个数赋给权值

         HuffNode[i].letter=a[i].s;      

     }

     for(i=0;i<n-1;i++)  //构造哈夫曼树

     {

         m1=m2=MAXVALUE;  //给最小和次小的树赋最大值

         x1=x2=0;

     for(j=0;j<n+i;j++)   //找出的两颗权值最小的子树

     {

         if(HuffNode[j].parent==-1 && HuffNode[j].weight<m1)  

         {                            //每次找出剩下的最小权值，并将最小权值赋给次小

             m2=m1;                                   

            x2=x1;

             m1=HuffNode[j].weight;

            x1=j;

         }else if(HuffNode[j].parent==-1 && HuffNode[j].weight<m2)

         {

             m2=HuffNode[j].weight;

             x2=j;

         }

     }

     //将找出的两颗子树合并成一棵子树

     HuffNode[x1].parent = n+i;

     HuffNode[x2].parent = n+i;

     HuffNode[n+i].weight = HuffNode[x1].weight+HuffNode[x2].weight;   //父节点赋权值

     HuffNode[n+i].lchild = x1;

     HuffNode[n+i].rchild = x2;

     //生成哈夫曼编码

    }

}

void  HuffmanCode(int  n, Message a[]){

    HNodeType  HuffNode[MAXNODE];

    HCodeType  HuffCode[MAXLEAF], cd;

    int  i, j ,c ,p;

    char  code[30],*m;

    HuffmanTree(HuffNode,n,a);     //调用哈夫曼树的构造

    for(i=0;i<n;i++){

    cd.start=n-1;                  //编码的开始位置

    c=i;

    p=HuffNode[c].parent;           

    while(p!=-1)                  //路径

    {

        if(HuffNode[p].lchild==c)     

            cd.bit[cd.start]=0;

        else  

            cd.bit[cd.start]=1;

        cd.start--;             //倒着计算编码值的所以减减

        c=p;                    //沿着父母结点往上走到顶点

        p=HuffNode[c].parent;   

    }

     //保存求出的每个叶节点的哈夫曼编码和编码的起始位

    for(j=cd.start+1;j<n;j++)              //cd.start往后退到要保存的位置，往前一位是编码值   

         HuffCode[i].bit[j]=cd.bit[j];    //将保存的编码值挨个赋值给编码结构体数组

         HuffCode[i].start=cd.start;     

    }

    printf("输出每个叶子节点的密文（哈夫曼编码）：\n");

    // 输出哈夫曼编码

    for(i=0; i<n; ++i){

        HuffCode[i].letter = HuffNode[i].letter;   //位置已经对应，但是编码数组没有字符，现付制字符

        printf("字符%c的密文:",HuffCode[i].letter);

        for(j=HuffCode[i].start + 1; j<n; ++j)   //start走过了，加一恢复到开始位，编码个数不会大于n

            printf("%d", HuffCode[i].bit[j]);    //按顺序输出编码

        printf("\n");

    }

        printf("\n");

    printf("输出连续的叶子节点的密文（哈夫曼编码）：\n");

        for(i=0; i<n; ++i){            

        for(j=HuffCode[i].start + 1; j<n; ++j){

                printf("%d", HuffCode[i].bit[j]);

        }

    }

    printf("\n\n");

    //手动输入二进制编码转化为字符

    printf("请输入密文(1/0)：\n");

    for(i=0; i<MAXLEAF; ++i) code[i] = NULL;    // 初始化code数组（code用来存储密文，类型char[]）

    scanf("%s",&code);

    m = code;

    c = 2*n -2;    //    哈夫曼树的根节点下标

    printf("输出明文（字符）: \n");

    while( *m != NULL) {

        if( *m == '0'){

            c = i =HuffNode[c].lchild;

            if(HuffNode[c].lchild == -1 && HuffNode[c].rchild == -1){ // 叶子节点

                printf("%c",HuffNode[i].letter);

                c = 2*n - 2;    // 重新从根遍历

            }

        }

        if( *m == '1'){

            c = i = HuffNode[c].rchild;

            if(HuffNode[c].lchild == -1 && HuffNode[c].rchild == -1) {    // 叶子节点

                printf("%c",HuffNode[i].letter);

                c = 2*n-2;    // 重新从根遍历

            }

        }

        m++;

    }

    printf("\n");

}

int main(void)

{

    Message data[MAXLEAF];

    char s[1000] , *p;     //char数组，存放字符 （最大是1000，符合需求）

    int i, count=0;       //count 计算不同字符个数

    printf("\n请输入一段明文(字符):");

    scanf("%s",&s);

    for(i=0;i<MAXLEAF;i++){      //初始化结构体数组data

        data[i].s=NULL;

        data[i].num=NULL;

    }

    p=s;

    while(*p){                 

        for(i=0;i<=count+1;i++){

            if(data[i].s==NULL){     //data[i].s存储 不同 的字符,用data[i].num存储相同的字符的数量

                data[i].s=*p;

                data[i].num++;

                count++;    // 统计不同字符的个数

                break;        // 跳出for循环，统计下一个字符 (需要注意的是，不会进行 i++了)

            }

            else if(data[i].s==*p){  // 字符重复，则累加 num

                data[i].num++;

                break;        // 跳出for循环，统计下一个字符

            }

        }

        p++;

    }

    printf("\n");

    printf("不同的明文(字符)个数:%d\n",count);

    for(i=0;i<count;i++){          //输出不同字符及其所对应的权值

        printf("%c",data[i].s);        

        printf("权值:%d",data[i].num);

        printf("\n");

    }

    printf("\n");

    HuffmanCode(count,data);    

    getch();    // 不回显函数

    return 0;

}