论坛 › 数据结构与算法 › Huffman树

Z_zack 发表于 2020-11-9 12:57:27

瑞斯拜

云端之梦 发表于 2020-11-24 22:27:03

#include <stdio.h>
#include <stdlib.h>
typedef char * * Huffmancode;
typedef struct
{
        int parent,lchild,rchild;
        int weight;
}Htnode,*Huffmantree;

int Select(Huffmantree HT,int end,int *s1,int *s2)//end保存数组最后一个
{
        int i=1;
        int min1,min2;
       
        while(HT.parent!=0&&i<end)//s1保存较小的
        {       
                i++;
        }
        min1=HT.weight;
        *s1=i;
        i++;
        while(HT.parent!=0&&i<end)
                i++;
        if(HT.weight<min1)
        {
                min2=min1;
                *s2=*s1;
                min1=HT.weight;
                *s1=i;
        }
        else
        {
                min2=HT.weight;
                *s2=i;
        }
        for(int j=i+1;j<end;j++)
        {
                if(HT.parent!=0)
                {
                        continue;
                }
                if(HT.weight<min1)
                {
                        min2=min1;
                        *s2=*s1;
                        min1=HT.weight;
                        *s1=j;
                }
                if(HT.weight>min1&&HT.weight<min2)
                {
                        min2=HT.weight;
                        *s2=j;
                }
        }
        return 0;
}
int CreatHTfumantree(Huffmantree *HT,Huffmancode &HC,int *w,int n)//n为叶子节点数
{

        if(n<=1)
                return 1;
        int m=2*n-1;//m为总节点数
        *HT=(Huffmantree)malloc((m+1)*sizeof(Htnode));//0号位置不用
        Huffmantree p=*HT;
        for(int i=1;i<=n;i++)
        {
                (p+i)->weight=*(w+i-1);
                (p+i)->parent=0;
                (p+i)->rchild=0;
                (p+i)->lchild=0;
        }
        for( i=n+1;i<=m;i++)
        {
                (p+i)->weight=0;
                (p+i)->lchild=0;
                (p+i)->rchild=0;
                (p+i)->parent=0;
        }
        for( i=n+1;i<=m;i++)
        {
                int s1,s2;
                Select(*HT,i-1,&s1,&s2);
                (*HT).parent=i;
                (*HT).parent=i;
                (*HT).lchild=s1;
                (*HT).rchild=s2;
                (*HT).weight=(*HT).weight+(*HT).weight;
        }
       
        return 0;
}


int main()
{
        return 0;
}

hasakiii 发表于 2020-12-6 20:54:14

{:5_95:}

ZzlYanG 发表于 2020-12-7 13:03:38

学习学习！

1624002105 发表于 2020-12-8 21:10:19

看看

3Lling 发表于 2020-12-13 20:01:49

ok

Tiｚ 发表于 2021-11-30 11:23:36

{:10_243:}

查看完整版本: Huffman树