数据结构——哈夫曼树及哈夫曼编码代码实现

Dear 丶 2024-04-18 16:49 84阅读 0赞

#define MAXLEAFNUM 50 //最优二叉树中的最多叶子数目
    
    typedef struct node{
        char ch;//结点表示的字符
        int weight;//权值
        int parent;//结点的父结点的下标，为0表示无父结点
        int lChild,rChild;//结点的左右孩子结点的下标，为0表示无孩子结点
    }HuffmanTree[2*MAXLEAFNUM];
    
    typedef char* HuffmanCode[MAXLEAFNUM + 1];
    
    void select(HuffmanTree HT,int n,int &s1,int &s2)
    {
        s1 = 1;
        s2 = 2;
        int nMinW = HT[1].weight;
    
        for(int  i = 1; i <= n;i++){
            if(HT[i].parent != 0){
                continue;
            }
            if(nMinW > HT[i].weight){
                nMinW = HT[i].weight;
                s1 = i;
            }
        }
        if(s1 != 1){
            nMinW = HT[1].weight;
        }else{
            nMinW = HT[2].weight;
        }
        for(int  i = 1; i <= n -1;i++){
            if(HT[i].parent != 0 || i == s1){
                continue;
            }
    
            if(nMinW > HT[i].weight){
                nMinW = HT[i].weight;
                s2 = i;
            }
        }
    }
    
    //创建哈夫曼树
    void createHTree(HuffmanTree HT,char *c,int *w,int n)
    {
        int i,s1,s2;
        if(n <= 1){
            return;
        }
    
        for(i = 1; i <= n;i++){//构造n棵只有根结点的树
            HT[i].ch = c[i - 1];
            HT[i].weight = w[i - 1];
            HT[i].parent = HT[i].lChild = HT[i].rChild = 0;
        }
        for(;i < 2 * n;i++){
            HT[i].parent = HT[i].lChild = HT[i].rChild = 0;
        }
    
        for(i = n + 1; i < 2 *n; i++){
            select(HT,i - 1,s1,s2);
            HT[s1].parent = i;
            HT[s2].parent = i;
            HT[i].lChild = s1;
            HT[i].rChild = s2;
            HT[i].weight = HT[s1].weight + HT[s2].weight;
        }
    }
    
    //根据给定的哈夫曼树，从每个叶子结点出发追溯到根，逆向找出最优二叉树中叶子结点的编码
    //n个叶子结点在哈夫曼HT中的下标为1~n，第i(1<= i <= n)个叶子的编码存放在HC[i]中
    void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n)
    {
        char *cd;
        int i,start,c,f;
    
        if(n <= 1){
            return;
        }
        cd = (char*)malloc( n * sizeof(char));//申请足够的空间存储编码
        cd[n -1] = '\0';//结尾符
        for(i = 1; i <= n;i++){
            start = n - 1;
            for(c = i,f = HT[i].parent;f != 0;c = f,f = HT[f].parent){//执行完一次后继续向上回溯结点
                if(HT[f].lChild == c){//如果当前结点与父结点的左节点相等，则对应字符编码为0，否则为1
                    cd[start] = '0';
                }else{
                    cd[start] = '1';
                }
                start--;
            }
            HC[i] = (char*)malloc((n - start) * sizeof(char));
            strcpy(HC[i],&cd[start]);
            free(cd);
        }
    }
    
    //利用最优二叉树译码
    void Decoding(HuffmanTree HT,int n,char *buff)
    {
        int p = 2 * n - 1;
        while (*buff) {
            if((*buff) == '0'){
                p = HT[p].lChild;
            }else{
                p = HT[p].rChild;
            }
    
            if(HT[p].lChild == 0 && HT[p].rChild == 0){
                cout << HT[p].ch << endl;
                p = 2 * n - 1;
            }
            buff++;
        }
    }