数据结构————哈夫曼树的实现

 效果图：

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
        int first;//表示pair对中的第一关键字
        int second;
}two;
typedef struct PQueue
{
    two *data;
    int size;
    int max_size;
}PQueue;
typedef struct HuffmanNode
{
    int w;
    int  LChild, RChild, Parent;
}HuffmanNode;
typedef struct HuffmanTree
{
    int max_size;
    HuffmanNode *data;
}HuffmanTree;

PQueue *Create_PQueue(int max_size)
{
    PQueue *P = (PQueue*)malloc(sizeof(PQueue));
    P->max_size = max_size;
    P->size = 0;
    P->data = (two*)calloc(max_size+1, sizeof(two));//从1开始使用
    return P;
}
two Getop_PQueue(PQueue * P)
{
    return P->data[1];
}
void Pop_PQueue(PQueue * Q)
{
    Q->data[1] = Q->data[Q->size];
    Q->size -= 1;
    int p = 1;
    int q = p*2;
    while(q <= Q->size)
    {
        if(Q->data[q].first > Q->data[p].first)
            break;
        else
        {
            if(Q->data[q].first > Q->data[q+1].first)
            {
                two t = Q->data[p];
                Q->data[p] = Q->data[q+1];
                Q->data[q+1] = t;


            }else
            {
                two t = Q->data[p];
                Q->data[p] = Q->data[q];
                Q->data[q] = t;
            }

            p = q;
            q = q*2;
        }
    }
}
void Push_PQueue(PQueue *Q, two e)
{
    Q->size += 1;
    Q->data[Q->size] = e;
    int p = Q->size;
    int q = p >> 1;
    while(q)
    {
        if(Q->data[q].first < Q->data[p].first)
            break;
        else
        {
            two t = Q->data[p];
            Q->data[p] = Q->data[q];
            Q->data[q] = t;
            p =  q;
            q = q >> 1;
        }
    }
}
HuffmanTree *Create_HuffmanTree(int max_size)
{
    HuffmanTree *H = (HuffmanTree*)malloc(sizeof(HuffmanTree));
    H->max_size = max_size;
    H->data = (HuffmanNode*)calloc(max_size+1, sizeof(HuffmanNode));//注意，从1开始
    for(int i = 0; i <= max_size; i++)
    {
        H->data[i].LChild = 0;
        H->data[i].RChild = 0;
        H->data[i].Parent = 0;
        H->data[i].w = 0;
    }
    return H;
}
void Fill_HuffmanTree(HuffmanTree* H,int *arr, int size)
{
    PQueue *PQ = Create_PQueue(size);
    for(int i = 1; i <= size; i++)
    {
        two tmp;
        H->data[i].w = arr[i];
        tmp.first = arr[i];
        tmp.second = i;
        Push_PQueue(PQ,tmp);
    }
    for(int i = size+1; i <= 2*size - 1; i++)
    {
        int p1 = Getop_PQueue(PQ).second;
        Pop_PQueue(PQ);
        int p2 = Getop_PQueue(PQ).second;
        Pop_PQueue(PQ);
        H->data[i].w = H->data[p1].w + H->data[p2].w;
        H->data[i].LChild = p1;
        H->data[i].RChild = p2;
        H->data[p1].Parent = i;
        H->data[p2].Parent = i;
        two t;
        t.first = H->data[i].w;
        t.second = i;
        Push_PQueue(PQ, t);
    }
}
void EnCode(HuffmanTree *H, char *code[], int num, int buf_max)
{
    buf_max += 1;
    char *buf = (char*)calloc(buf_max, sizeof(char));
    buf[buf_max - 1] = '\0';
    for(int i = 1; i <= num; i++)
    {
        int cnt = buf_max-2;
        int p = i;
        while(H->data[p].Parent)
        {
            if(H->data[H->data[p].Parent].LChild == p)//左孩子
            {
                buf[cnt--] = '0';
            }
            else//右孩子
            {
                buf[cnt--] = '1';
            }
            p = H->data[p].Parent;
        }
        code[i] = (char *)calloc(buf_max-cnt, sizeof(char));
        strcpy(code[i], buf+cnt+1);
    }
}
void DeCode(HuffmanTree *H,int p_root, char*code, int* readnum,int* result)
{
    int cnt = 0;
    int p = p_root;
    int len = strlen(code);
    for(int i = 0; i < len ; i++)
    {
        if(code[i]=='0')
            p = H->data[p].LChild;
        else
            p = H->data[p].RChild;
        cnt++;
        if(!(H->data[p].LChild || H->data[p].RChild))
            break;
    }
    if(H->data[p].LChild || H->data[p].RChild)
    {
        printf("\n\n\a解码错误！\n");
        exit(3721);
    }
    *readnum = cnt;
    *result = p;
}
int main()
{
    int num = 0;
    printf("输入编码的个数和对应字符：\n");
    scanf("%d",&num);
    char c[num+1];
    char *code[num+1];
    char mycode[10000];
    int frequence[num+1];
    for(int i = 1; i <= num; i++)
    {
        char xx[4];
        scanf("%s",xx);
        c[i] = xx[0];
    }
    printf("输入编码的出现频率（整数）：\n");
    for(int i = 1; i <= num; i++)
    {
        scanf("%d",&frequence[i]);
    }
    HuffmanTree* H = Create_HuffmanTree(2*num-1);
    Fill_HuffmanTree(H,frequence,num);
    EnCode(H,code,num,num+5);
    for(int i = 1; i <= num; i++)
    {
        printf("%c :\t%s\n",c[i],code[i]);
    }
    printf("请输入编码：\n");
    scanf("%s",mycode);
    {
        int i = 0;
        while(i < strlen(mycode))
        {
            int readnum;
            int res;
            DeCode(H,2*num-1,mycode+i,&readnum,&res);
            printf("%c ",c[res]);
            i += readnum;
        }

    }
    return 0;
}
/*备用代码储备_______小根堆调试代码
PQueue *Q;
    Q = Create_PQueue(4);
    two t;
    t.first = 1;
    t.second = 0;
    Push_PQueue(Q,t);
    t.first = 1;
    Push_PQueue(Q,t);
    t.first = -1;
    Push_PQueue(Q,t);
    t.first = 0;
    Push_PQueue(Q,t);
    for(int i = 0; i < 3; i++)
    {
        two xx = Getop_PQueue(Q);
        Pop_PQueue(Q);
        printf("%d,%d\n",xx.first, xx.second);
    }

    t.first = 3;
    Push_PQueue(Q,t);
    t.first = 7;
    Push_PQueue(Q,t);
    t.first = -120;
    Push_PQueue(Q,t);
    for(int i = 0; i < 4; i++)
    {
        two xx = Getop_PQueue(Q);
        Pop_PQueue(Q);
        printf("%d,%d\n",xx.first, xx.second);
    }
*/
/*备用代码储备_______编码测试代码
 HuffmanTree *H = Create_HuffmanTree(20);
    int arr[10];
    char *code[10];
    for(int i = 1; i <= 4; i++)
    {
        scanf("%d",&arr[i]);
    }
    Fill_HuffmanTree(H,arr, 4);
    EnCode(H,&code,4,100);
    for(int i = 1; i <= 4; i++)
    {
        printf("%s\n",code[i]);
    }

*/