程序填空题：哈夫曼编码

本题要求根据输入创建哈夫曼编码。

输入4 个字符以及该字符对应的权值(如:a,10)

输出每个节点的哈夫曼编码。 

输入样例为：
```
a,10
b,9
c,12
d,8
```
输出样例为：
```
a:10
b:00
c:11
d:01
```

```c++
#include
#include
#include

#define N 4         //带权值的叶子节点数或者是需要编码的字符数
#define M 2*N-1     //n个叶子节点构造的哈夫曼树有2n-1个结点
#define MAX 10000

typedef char TelemType;
typedef struct{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
} HTNode;
typedef HTNode HuffmanTree[M+1];
typedef char * HuffmanCode[N+1];

void createHuffmanTree(HuffmanTree HT, int *w, int n);
void select(HuffmanTree HT, int k, int *s1, int *s2);
void encodingHuffmanCode(HuffmanTree HT, HuffmanCode HC);
void printHuffmanCoding(HuffmanCode HC, char ch[]);

int main(){
    HuffmanTree HT;
    TelemType ch[N+1];
    int w[N+1];
    for(int i = 1; i <= N; i++){
        scanf("%c,%d", &ch[i], &w[i]);
        getchar();}
    createHuffmanTree(HT, w, N);    HuffmanCode HC;
    encodingHuffmanCode(HT, HC);    printHuffmanCoding(HC, ch);
    return 0;}

void createHuffmanTree(HuffmanTree HT, int *w, int n){
    if(n<=1)
        return;
    for(int i=1; i<=n; i++){
        HT[i].weight=;
        HT[i].lchild=;
        HT[i].parent=;
        HT[i].rchild=; }
    for(int i=; i<=M; i++){
        HT[i].weight=0;
        HT[i].lchild=0;
        HT[i].parent=0;
        HT[i].rchild=0; }
    for (int i=n+1; i<=M; i++){
        int s1,s2;
        select(HT,i-1,&s1,&s2);
        HT[s1].parent=i;
        HT[s2].parent=i;
        HT[i].lchild=;
        HT[i].rchild=;
        HT[i].weight=; }}

void select(HuffmanTree HT, int k, int *s1, int *s2){
    unsigned int tmp=MAX,tmpi=0;
    for (int i=1; i<=k; i++){
        if(!HT[i].parent){
            if(tmp>HT[i].weight){
                tmp=HT[i].weight;
                tmpi=i;}}}
    *s1=tmpi;
    tmp=MAX;
    tmpi=0;
    for(int i=1; i<=k; i++){
        if((!HT[i].parent)&&i!=*s1){
            if(tmp>HT[i].weight){
                tmp=HT[i].weight;
                tmpi=i;}}}
    if(tmpi<*s1){
        *s2=*s1;
        *s1=tmpi;}
    else
        *s2=tmpi;}

void encodingHuffmanCode(HuffmanTree HT, HuffmanCode HC){
    char tmp[N];
    tmp[N-1]=;
    int start,c,f;
    for (int i=1; i<=N; i++){
        start=N-1;
        for(c=i,f=; f!=0; c=f,f=){
            if(HT[f].lchild==c)
                tmp[--start]=;
            else
                tmp[--start]=; }
        HC[i]=(char*)malloc((N-start)*sizeof(char));
        strcpy (HC[i],&tmp[start]);}}

void printHuffmanCoding(HuffmanCode HC, char ch[]){
    for(int i=1; i<=N; i++){
        printf("%c:%s\n",ch[i],HC[i]);}}
```






答案：
第1空：w[i]    

第2空：0    

第3空：0    

第4空：0    

第5空：n+1    

第6空：s1    

第7空：s2    

第8空：HT[s1].weight+HT[s2].weight    

第9空：'\0'    

第10空：HT[i].parent    

第11空：HT[f].parent    

第12空：'0'    

第13空：'1'