Huffman树

Z_zack

瑞斯拜

云端之梦

#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[i].parent!=0&&i<end)//s1保存较小的
        {       
                i++;
        }
        min1=HT[i].weight;
        *s1=i;
        i++;
        while(HT[i].parent!=0&&i<end)
                i++;
        if(HT[i].weight<min1)
        {
                min2=min1;
                *s2=*s1;
                min1=HT[i].weight;
                *s1=i;
        }
        else
        {
                min2=HT[i].weight;
                *s2=i;
        }
        for(int j=i+1;j<end;j++)
        {
                if(HT[j].parent!=0)
                {
                        continue;
                }
                if(HT[j].weight<min1)
                {
                        min2=min1;
                        *s2=*s1;
                        min1=HT[j].weight;
                        *s1=j;
                }
                if(HT[j].weight>min1&&HT[j].weight<min2)
                {
                        min2=HT[j].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)[s1].parent=i;
                (*HT)[s2].parent=i;
                (*HT)[i].lchild=s1;
                (*HT)[i].rchild=s2;
                (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
        }
       
        return 0;
}


int main()
{
        return 0;
}

hasakiii

ZzlYanG

学习学习！

1624002105

看看

3Lling

ok

Tiｚ