哈夫曼编码

此代码用于生成哈夫曼树并且获取哈夫曼编码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char buffer[100010];
typedef struct node
{
    int cnt;
    char *s;
    struct node *left,*right,*next;
} HuffmanNode;
HuffmanNode* Root=NULL;
HuffmanNode Trees[200];
HuffmanNode* createNode()
{
    HuffmanNode* p = (HuffmanNode*)malloc(sizeof(HuffmanNode));
    p->cnt = 0;
    p->left=p->right=p->next=NULL;
    return p;
}
void InsertLinkedList(HuffmanNode* p)//插入有序链表中
{
    HuffmanNode* q = Root,*front=NULL;
    if (Root==NULL) {
        Root=p;
    } else {
        if (p->cnt < Root->cnt) {
            p->next = Root;
            Root = p;
        } else {
            while (q && q->cnt <= p->cnt) {//保证相等权值的结点总是后插入的在后面
                front = q;
                q = q->next;
            }
            p->next = front->next;
            front->next = p;
        }
    }
}
void getHuffmanCode(HuffmanNode* p,char *temp,int i) {//得到字符的Huffman编码
    if (p->left==NULL && p->right==NULL) {//只有在叶节点时才停止
        temp[i]=0;
        p->s = (char *)malloc(strlen(temp)+1);
        strcpy(p->s,temp);
        return;
    } else {
        temp[i]='0';
        getHuffmanCode(p->left,temp,i+1);//沿左子树，Huffman编码加一个'0'
        temp[i]='1';
        getHuffmanCode(p->right,temp,i+1);//沿右子树，Huffman编码加一个'1'
    }
}
int main()
{
    FILE* fin = fopen("input.txt","r");
    FILE* fout = fopen("output.txt","w");
    int i,len,j=0,t=0;
    char temp[1000];
    unsigned char hc=0;

    Trees[0].cnt = 1;//让'\0'权值为1
    len = fread(buffer,1,100000,fin);//统计每个字符的频率
    for (i=0;i<len;i++) {
        if (buffer[i]!='\n') {
            Trees[buffer[i]].cnt++;
        }
    }

    for (i=0;i<200;i++) {//ascii码值从小往大插入，保证了相等的权值下，ascii码值小的在前面
        if (Trees[i].cnt) InsertLinkedList(&Trees[i]);
    }

    while (Root->next) {//形成哈夫曼树
        HuffmanNode *p = Root,*q = Root->next;
        Root = Root->next->next;
        HuffmanNode *T = createNode();
        T->cnt = p->cnt+q->cnt;
        T->left = p;
        T->right = q;
        InsertLinkedList(T);
    }

    getHuffmanCode(Root,temp,0);//获取哈夫曼编码

    for (i=0;i<=len;i++) {//输出结果
        if (buffer[i]!='\n') {
            j=0;
            while (Trees[buffer[i]].s[j]) {
                hc = (hc<<1) | (Trees[buffer[i]].s[j++]-'0');//注意此处右移的用法
                t++;
                if (t==8) {//8位一输出
                    printf("%x",hc);
                    fputc(hc,fout);
                    hc=0;
                    t=0;
                }
            }
        }
    }
    while(t>0) {
        hc = hc<<1;
        t++;
        if (t==8) {
            printf("%x",hc);
            fputc(hc,fout);
            break;
        }
    }
    return 0;
}