#include <stdlib.h>#include <stdio.h>#include <string.h>#include <conio.h>#pragma warning(disable:4996)typedef struct HuffmanTree{    int weight;//权值    int parent;//父节点    int left;//左子树    int right;//右子树};typedef char *HuffmanCode;//Huffmancode编码//从1-x个节点选择parent节点为0，权重最小的两个节点void SelectNode(HuffmanTree *ht, int n, int *bt1, int *bt2){    int i;    HuffmanTree *ht1, *ht2, *t;    ht1 = ht2 = NULL;//初始化两个节点为空    for (i = 1; i <= n; ++i)//循环处理1-n个节点（包括叶节点和非叶节点）    {        if (!ht[i].parent)//父节点为空(节点的parent为0)        {            if (ht1 == NULL)//节点指针1为空            {                ht1 = ht + i;//指向第i个节点                continue;//继续循环            }            if (ht2 == NULL)            {                ht2 = ht + i;                if (ht1->weight > ht2->weight)//比较两个值的权重，使ht1指向权值大的                {                    t = ht2;                    ht2 = ht1;                    ht1 = t;                }                continue;//继续循环            }            if (ht1 && ht2)//若两个值都有效            {                if (ht[i].weight <= ht1->weight)//第i个节点权重小于ht1指向的节点                {                    ht2 = ht1;//ht2保存ht1,因为这时ht1指向的节点成为第2小的                    ht1 = ht + i;                }                else if (ht[i].weight < ht2->weight)//若第i个节点权重小于ht2指向的权重                {                    ht2 = ht + i;                }            }        }    }    if (ht1 > ht2)//增加比较，使二叉树左侧为叶节点    {        *bt2 = ht1 - ht;        *bt1 = ht2 - ht;    }    else    {        *bt1 = ht1 - ht;        *bt2 = ht2 - ht;    }}void CreateTree(HuffmanTree *ht, int n, int *w){    int i, m = 2 * n - 1;//总的节点总数    int bt1, bt2;//二叉树节点序与    if (n <= 1)//只有一个节点就无法创建    {        return;    }    for (i = 0; i <= n; ++i)//初始化节点    {        ht[i].weight = w[i - 1];        ht[i].parent = 0;        ht[i].left = 0;        ht[i].right = 0;    }    for (; i <= m; ++i)//初始化后序节点    {        ht[i].weight = 0;        ht[i].parent = 0;        ht[i].left = 0;        ht[i].right = 0;    }    for (i = n + 1; i <= m; ++i)//逐个计算非叶节点，创建Huffman树    {        SelectNode(ht, i - 1, &bt1, &bt2);        ht[bt1].parent = i;        ht[bt2].parent = i;        ht[i].left = bt1;        ht[i].right = bt2;        ht[i].weight = ht[bt1].weight + ht[bt2].weight;    }}//void HuffmanCoding(HuffmanTree *ht, int n, HuffmanCode *hc){    char *cd;    int start, i;    int current, parent;    cd = (char*)malloc(sizeof(char)*n);//用来临时存放一个字符编码的结果    cd[n - 1] = ‘\0‘;//设置字符串结束标志    for (i = 1; i <= n; i++)    {        start = n - 1;        current = i;        parent = ht[current].parent;//获取当前节点的父节点；        while (parent)        {            if (current == ht[parent].left)//若该节点的父节点是做左子树            {                cd[--start] = ‘0‘;//设置编码为0            }            else//若该节点是父节点的右子树            {                cd[--start] = ‘1‘;//设置编码为1            }            current = parent;//设置当前节点指向父节点            parent = ht[parent].parent;//获取当前节点的父节点序号；        }        hc[i - 1] = (char*)malloc(sizeof(char)*(n - start));        strcpy(hc[i - 1], &cd[start]);//复制生成生成的编码    }    free(cd);//释放编码占用的字符}void Encode(HuffmanCode *hc, char *alphabet, char *str, char *code){    //将一个字符串转换为Huffman编码    //hc为Huffman编码表，alphabet为对应的字母表，str为需要转换的字符串，code返回转换的结果    int len = 0, i = 0, j;    code[0] = ‘\0‘;    while (str[i])    {        j = 0;        while (alphabet[j] != str[i])        {            j++;        }        strcpy(code + len, hc[j]);//将对应字母的Huffman编码复制code指定位置        len = len + strlen(hc[j]);//累加字符串长度        i++;    }    code[len] = ‘\0‘;}void Decode(HuffmanTree *ht, int m, char *code, char *alphabet, char *decode){    //将一个huffman编码组成的字符串转换为明文字符串    //ht为huffman二叉树，m为字符数量，alphabet为对应的字母表，str需转换的字符串    int position = 0, i, j = 0;    m = 2 * m - 1;    while (code[position])//字符串未结束    {        for (i = m; ht[i].left && ht[i].right; position++)        {            if (code[position] == ‘0‘)//编码位为0            {                i = ht[i].left;            }            else            {                i = ht[i].right;//处理右子树            }        }        decode[j] = alphabet[i - 1];//得到一个字母        j++;//处理下一个字符    }    decode[j] = ‘\0‘;//字符串结尾}//主函数int main(void){    int i, n = 4, m;    char test[] = "DBDACDADCCDBDCBADBCABABA";    char code[100], code1[100];    char alphabet[] = { ‘A‘, ‘B‘, ‘C‘, ‘D‘, };//四个字符    int w[] = { ‘5‘, ‘7‘, ‘2‘, ‘13‘ };//四个字符的权重    HuffmanTree *ht;    HuffmanCode *hc;    m = 2 * n - 1;    ht = (HuffmanTree *)malloc((m + 1)*sizeof(HuffmanTree));//申请内存，保存赫夫曼树    if (!ht)    {        printf("内存分配失败！");        exit(0);    }    hc = (HuffmanCode *)malloc(n*sizeof(char*));    if (!hc)    {        printf("分配内存失败！");        exit(0);    }    //创建赫夫曼树    CreateTree(ht, n, w);    HuffmanCoding(ht, n, hc);//根据赫夫曼树生成的赫夫曼编码    for (i = 1; i <= n; i++)    {        printf("字母：%c,权重：%d,编码为：%s\n", alphabet[i - 1], ht[i].weight, hc[i - 1]);    }    Encode(hc, alphabet, test, code);//根据赫夫曼编码生成编码字符串    printf("\n字符串：\n%s\n转换后为：\n%s\n", test, code);    Decode(ht, n, code, alphabet, code1);//根据编码字符串生成解码后的字符串    printf("\n编码：\n%s\n转换后为：\n%s\n", code, code1);    _getch();    return 0;}