哈夫曼编码

#include<stdio.h>
#include<tchar.h>
#include<stdlib.h>


typedef struct {
    int weight;
    int parent, lchild, rchild;
} HTNode, * HuffmanTree;         //动态分配数组存储Huffman 树
typedef char ** HuffmanCode;         //动态分配数组存储Huffman 编码表


void Select(HuffmanTree HT,int j,int &s1,int &s2){          //获取哈夫曼树前j个结点中最小的两个结点，将这两个结点的下标赋给s1和s2
    int min1=10000,min2=10000;
    for(int k=1;k<=j;k++)
        if(HT[k].weight<min1&&HT[k].parent==0){
            min1=HT[k].weight;
            s1=k;
        }
    for(int k=1;k<=j;k++)
        if(HT[k].weight<min2&&HT[k].parent==0&&k!=s1){
            min2=HT[k].weight;
            s2=k;
        }
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC,int *w, int n){     //w存放n个字符的权值，构造Huffman 树HT, 并求出n 个字符的Huffman 编码HC 。
    printf("\n以权值小的为左子树创建哈夫曼树\n\n\n");
    if (n<=1)
        return;
    int m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    
    HuffmanTree p;
    int i,s1,s2;
    
    for(p=HT+1, i=1; i<=n; ++i, ++p, ++w)
        *p={*w, 0, 0, 0};
    for ( ; i<=m; ++i, ++p)
        *p={0, 0, 0, 0};
    for (i=n+1; i<=m; ++i){     //创建Huffman树     //在HT[1…i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
        
        Select(HT, i-1, s1, s2);
        HT[s1].parent=i;
        HT[s2].parent=i;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
    
    
    //——从叶子到根逆向求每个字符的Huffman 编码——
    HC=(HuffmanCode)malloc((n+1)*sizeof(char *));    //分配n个字符编码的头指针向量
    char *cd=(char *)malloc(n*sizeof(char));    //分配求编码的工作空间      //开始不知道编码的长度，先设置为最长的情况，然后设置一个索引start，从start位置开始输出直到遇到\0结束即成功输出一个编码
    cd[n-1]='\0';    //编码结束符
    for (i=1; i<=n; ++i) {      //逐个字符求哈夫曼编码
        int start=n-1;      //编码结束符位置    //先将索引start设为最后一个位置，然后每算出一位编码就让 start--
        for (int c=i,f=HT[i].parent; f!=0; 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));      //为第i个字符编码分配空间
        strcpy(HC[i], &cd[start]);      //从cd复制编码到HC
        
    }
    
    free(cd);    //释放工作空间
}


void PrintHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n){         //打印各结点的赫夫曼编码

            HuffmanCode p=HC;
            printf("\n\n");
            for(int i=1; i<=n; i++)
            {

           printf("The weight %d HuffmanCode is: ", HT[i].weight);
           while(*p[i]!='\0'){
                    printf("%c",*p[i]);
                    p[i]++;
           }
           printf("\n");
        }
}


void PrintHuffmanTree(HuffmanTree HT,int n){
    int m=2*n-1;
    printf("HT\tweight\tparent\tlchild\trchild\n");
    for(int i=1;i<m+1;i++){
        printf("%d\t  %d\t  %d\t  %d\t  %d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
    }
}















main(){
    int n = 5;
    HuffmanTree HT;
    HuffmanCode HC;
    int a[5] = {5,6,2,9,7};//信号源的概率分布，即P={p0, p1,…, pK-1}
    HuffmanCoding(HT, HC, a, n);
    PrintHuffmanTree(HT,n);
    PrintHuffmanCode(HT, HC, n);
    system("pause");
}