哈夫曼編碼及譯碼

#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;

}