createt.c

Huffman和迷宫问题Huffman和迷宫问题Huffman和迷宫问题Huffman和迷宫问题

void Select(HuffmanTree HT,int x,int *s1,int *s2)
{
    HTNode *p=HT;
    int i=0,min=0,smin=0;

    for(i=0;i<x;i++,p++)
    {
        if(p->parent==0)
            if(min==0)
            {
                min=p->cha.num;
                *s1=i;
            }
            else if(min!=0&&smin==0)
                if(min<=p->cha.num)
                {
                    smin=p->cha.num;
                    *s2=i;
                }
                else
                {
                    smin=min;
                    *s2=*s1;
                    min=p->cha.num;
                    *s1=i;
                }
            else
                if(p->cha.num<min)
                {
                    smin=min;
                    *s2=*s1;
                    min=p->cha.num;
                    *s1=i;
                }
                else if(p->cha.num<smin)
                {
                    smin=p->cha.num;
                    *s2=i;
                }
    }

}
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Sign *w,int n)
{
    int m=0,i,s1,s2,start,c,f;

    HTNode *p;
    char *cd,temp;
    if(n<=1) return;

    m=2*n-1;

    (*HT)=(HuffmanTree)malloc(m*sizeof(HTNode));            /*0st unit is not used*/

    for(p=*HT,i=1;i<=n;++i,++p,++w)
    {
        (*p).cha.cha=(*w).cha;                               /*Initialize*/
        (*p).cha.num=(*w).num;
        (*p).parent=(*p).lchild=(*p).rchild=0;
    }
    
    for(;i<=m;++i,++p)
    {
        (*p).cha.cha='\0';                               /*Initialize*/
        (*p).cha.num=0;
        (*p).parent=(*p).lchild=(*p).rchild=0;
    }

    for(i=n+1;i<=m;i++)
    {
        Select((*HT),i-1,&s1,&s2);
        (*HT)[s1].parent=(*HT)[s2].parent=i;
        (*HT)[i-1].lchild=s1+1;
        (*HT)[i-1].rchild=s2+1;
        (*HT)[i-1].cha.num=(*HT)[s1].cha.num+(*HT)[s2].cha.num;
    }
    (*HC)=(HuffmanCode)malloc((n+1)*sizeof(char *));
    cd=(char *)malloc((n+1)*sizeof(char));
    cd[n]='\0';
    for(i=1;i<=n;++i)
    {
        start=n;
        temp=(*HT)[i-1].cha.cha;
        for(c=i,f=(*HT)[i-1].parent;f!=0;c=f,f=(*HT)[f-1].parent)
        {
            if((*HT)[f-1].lchild==c)
                cd[--start]='0';
            else
                cd[--start]='1';
        }

        cd[--start]=temp;

        (*HC)[i]=(char *)malloc( (n+1-start)*sizeof(char) );

        strcpy((*HC)[i],&cd[start]);
    }
    free(cd);
}