赫夫曼树和赫夫曼编码

前言：

接近一个礼拜没更新了，因为上周周末我有两场计算机的算法比赛，我要复习，没时间更新博客。可事情总是不如人意，两场考试我都考的不好，都没做出来几道题，深深的打击了我，现在处于极度痛苦中。

这次说的这道题也没啥难的，唯一要注意的就是如何用选择排序选出一组序列中最小的两个数，而根据题目要求可以看出左右之分是根据这两个数的下标决定，而我排出来的是根据数字大小排的，所有在最后需要按照要求改一下。

第1关：赫夫曼树和赫夫曼编码

任务描述

本关任务：赫夫曼编码。请编写一个程序，先输入字符个数，再输入各个字符的权值（权值大小对应字符的出现频率），请以这些字符为叶子建立赫夫曼树，再求出其赫夫曼编码，并打印。

相关知识

为了完成本关任务，你需要掌握：1.如何建立赫夫曼树，2.如何应用赫夫曼树进行编码。

数据结构

根据课本，给出赫夫曼树存储的数据结构

typedef struct{    unsigned int weight;    unsigned int parent, lchild, rchild;}HTNode, *HuffmanTree;        //动态分配数组存储赫夫曼树typedef char ** HuffmanCode;    //动态分配数组存储赫夫曼编码表

建立赫夫曼树

建立过程如下：

for(i= 第n+1个结点开始； i<=没有到达第2n+1个结点； 结点下标++){    Select(HT，i-1， s1, s2);    以s1和s2为下标的结点的双亲是i；    s1和s2中下标靠前的是i结点的左孩子，另一个为右孩子}

函数名如下： void Create_HuffmanTree(HuffmanTree HT,int n)；

HT的初始化函数已经给出，不需要学生完成。

求赫夫曼编码

从叶子开始逆序遍历建好的赫夫曼树 举例如下： 从叶子结点a开始，a的双亲是b，a是b的左孩子，则在a的编码序列中添加一个‘0’，b的双亲是c，b是c的右孩子，则在a的编码序列的最左侧添加一个‘1’，此时a的编码序列是‘10’。c的双亲是0，则逆序编列结束.将a的编码字符串存入HC中。

函数名如下： void GetHuffmanCode(HuffmanCode HC, HuffmanTree HT, int n)； 同样，HC的初始化函数已经给出，不需要学生完成。

Select()函数

提示： 可以参考选择排序的方法，使用两个整型变量，或指针，指定两个数为最小值，在遍历过程中，遇到比两个数其中任意一个数小时，与更改下标或更改指针指向。这种方法可以在仅作一次循环的前提下，找到两个最小值。

编程要求

根据提示，在右侧编辑器补充代码，将建立赫夫曼树、查找权重最小的结点下标和获取赫夫曼编码的函数补充完整。

测试说明

平台会对你编写的代码进行测试：

测试输入：

8    //8个权值5 29 7 8 14 23 3 11        //录入权值

预期输出：

01101011101111110000111010

开始你的任务吧，祝你成功！

源码：

/*
    哈夫曼编码(代码补充) 
*/
#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct{
    int weight;
    int parent, lchild, rchild;
}HTNode, *HuffmanTree;    //动态数组，元素为HTNode 
typedef char** HuffmanCode;    //编码表，每一个元素都是一个编码，即char*方式存储的字符串 

void Init_weight(int **w, int n){
    while(!(*w=(int*)malloc((n+1)*sizeof(int))));
}

void Create_Weight(int n, int *w){
    int i, data;
    for(i = 1; i<=n; i++){
        scanf("%d", &data);
        w[i] = data;
    }
}    
    
    //初始化哈夫曼树 
void Init_HuffmanTree(HuffmanTree *HT,int *w, int n){
    int i;
    int m = 2*n-1;
    HTNode *p;
    while(!((*HT)=(HTNode*)malloc(sizeof(HTNode)*(m+1))));
    for(p = (*HT)+1, i=1; i<=n; i++, p++){
        p->weight = w[i];
        p->parent = 0;
        p->rchild = 0;
        p->lchild = 0;
    }
    for(; i<=m; i++, p++){
        p->lchild = 0;
        p->parent = 0;
        p->rchild = 0;
        p->weight = 0;
    }
}

//利用选择排序（循环一次得到最小的两个值） 
//在HT中选择parent为0，且权重最小的两个节点，返回他们的数组下标分别为s1和s2 
void Select(HuffmanTree HT, int i, int *s1, int *s2){
    //**************begin********************
    int flag1=0,flag2=0;
    for(int j=1;j<=i;j++){
        if(HT[j].parent==0){
            if(flag1==0){
                *s1=j;
                flag1++;
                continue;
            }
            if(flag2==0){
                *s2=j;
                flag2++;
                continue;
            }
            if(flag1==1&&flag2==1&&HT[*s1].weight>HT[*s2].weight){
                int x=*s1;*s1=*s2;*s2=x;
            }
            if(HT[j].weight<HT[*s1].weight){
                *s2=*s1;
                *s1=j;
                continue;
            }
            if(HT[j].weight<HT[*s2].weight){
                *s2=j;
                continue;
            }
        }
    }
    //这里就是根据下标大小来重新排一下
    if(*s1>*s2){
        int x=*s1;*s1=*s2;*s2=x;
    }
    
      //****************end******************
}

    //创建哈夫曼树
void Create_HuffmanTree(HuffmanTree HT,int n){
    //**************begin********************
    for(int i=n+1;i<=2*n-1;i++){
        int s1=0,s2=0;
        Select(HT,i-1,&s1,&s2);
        HT[i].lchild=s1;HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
        HT[s1].parent=i;HT[s2].parent=i;
    }
      //****************end******************
}
    
    //初始化哈夫曼编码表 
void Init_HuffmanCode(HuffmanCode *HC,int n){
    while(!((*HC) = (HuffmanCode)malloc((n+1)*sizeof(char*))));
}
    
    //求哈夫曼编码
void GetHuffmanCode(HuffmanCode HC, HuffmanTree HT, int n){
    //**************begin********************
    char temp[n];
    temp[n-1]='\0';
    for(int i=1;i<=n;i++){
        int start=n-1,f=HT[i].parent,t=i;
        while(f!=0){
            start--;
            if(HT[f].lchild==t){
                temp[start]='0';
            }else{
                temp[start]='1';
            }
            t=f;f=HT[t].parent;
        }
        HC[i]=new char[n-start];
        strcpy(HC[i],&temp[start]);
    }
    
      //****************end******************
}
    
    //打印哈夫曼编码表
void PrintCode(HuffmanCode HC, int n){
    for(int i=1; i<=n; i++){
        printf("%s\n", HC[i]);
    } 
} 

void Destory(HuffmanTree *HT, HuffmanCode *HC){
    free(*HC);
    free(*HT);
}
int main(){
    HuffmanTree HT;
    HuffmanCode HC;
    int *w, n; 
    
    scanf("%d", &n);
    
    //初始化权重数组 
    Init_weight(&w, n);
    
    
    //创建权值数组
    //n表示权值个数 
    Create_Weight(n, w);    
    
    
    //初始化哈夫曼树 
    Init_HuffmanTree(&HT, w, n);
 
    //创建哈夫曼树
    Create_HuffmanTree(HT, n);
    
    //初始化哈夫曼编码表 
    Init_HuffmanCode(&HC, n);
    
    //求哈夫曼编码
    GetHuffmanCode(HC, HT, n); 
    
    //打印哈夫曼编码表
    PrintCode(HC, n); 
    
    //释放空间
    Destory(&HT, &HC);
     
    
    return 0;
}