huffman.c

/*
 * Building Huffman Tree
 * Author: ismdeep
 * */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    int id;
    double p;
    struct Node *left;
    struct Node *right;
    int level;
} Node;

int max(int a, int b) {
    return a > b ? a : b;
}

char *strjoin(char *str1,char *str2) {
    char *ans = (char *) malloc( (strlen(str1) + strlen(str2) + 4) * sizeof(char));
    strcpy(ans, str1);
    strcat(ans, str2);
    return ans;
}

void *create_array(int size, int sizeof_item) {
    void *a = malloc(size * sizeof_item);
    return a;
}

void swap(int *a, int *b) {
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void arrange(Node **p, int *index1, int *index2) {
    if (p[*index1]->p > p[*index2]->p) {
        swap(index1, index2);
    }
}

/* 找出最小的两个位置 */
void find_top(Node **p, int size, int *index1, int *index2) {
    *index1 = 0;
    *index2 = 1;
    int index3;
    arrange(p, index1, index2);
    for (int i = 2; i < size; i++) {
        index3 = i;
        arrange(p, index2, &index3);
        arrange(p, index1, index2);
    }
}

/* 构建Huffman树 */
void build_huffman_tree(Node *node, int n) {
    for (int i = 0; i < 2 * n - 1; i++) {
        node[i].left = NULL;
        node[i].right = NULL;
        node[i].level = 0;
    }

    /* 指向指针的动态指针数组 */
    Node **a = (Node **) create_array(n, sizeof(Node *));
    for (int i = 0; i < n; i++) {
        a[i] = &node[i];
    }

    for (int i = 0; i < n - 1; i++) {
        int index1, index2;
        /* 每次寻找两个最小的进行合并。 */
        find_top(a, n - i, &index1, &index2);
        node[n + i].p = a[index1]->p + a[index2]->p;
        node[n + i].left = a[index1];
        node[n + i].right = a[index2];
        node[n + i].level = max(a[index1]->level, a[index2]->level) + 1;
        /* 将新的节点放到 a[index1] 里面 */
        a[index1] = &node[n + i];
        /* 将最后一个节点放到 a[index2] 里面 */
        a[index2] = a[n - 1 - i];
    }
}

void generate_huffman_code(Node *node, char str[]) {
    if (NULL == node->left && NULL == node->right) {
        printf("Id:%d   P:%.2lf    Code:%s\n", node->id, node->p, str);
        return;
    }
    if (NULL != node->left) {
        generate_huffman_code(node->left, strjoin(str, "0"));
    }
    if (NULL != node->right) {
        generate_huffman_code(node->right, strjoin(str, "1"));
    }
}

int main() {
    freopen("in.txt", "r", stdin);
    int n, i;
    scanf("%d", &n);

    /* 动态创建节点，一棵叶子节点为n的Huffman树，一共需要2*n-1个节点进行存储。 */
    /* 这里存储方式类似树状数组的思想。 */
    Node *node = (Node *) create_array(n * 2 - 1, sizeof(Node));
    for (i = 0; i < n; i++) {
        scanf("%lf", &node[i].p);
        node[i].id = i;
    }

    /* 构建Huffman树 */
    build_huffman_tree(node, n);
    for (i = 0; i < 2 * n - 1; i++) {
        printf("%p => left:%p  right:%p   %.2lf\n", &node[i], node[i].left, node[i].right,  node[i].p);
    }
    printf("----------------------------\n");
    char *str = "";
    generate_huffman_code(&node[2 * n - 2], str);
    return 0;
}