首页 > 代码库 > 数据结构之哈夫曼树

数据结构之哈夫曼树

2024-07-14 05:45:25   223人阅读

 typedef struct{
       int wiget;
       int lchild,rchild,parent;
       int data;
    }HNode,*HTree;


     void select(HTree &H,int i,int &s1,int &s2){
             int tmp,min1,min2=0;
             int j;
            for(j=1;j<=i;j++)
              {
                  if(H[i].parent==0)
                    {
                       min1=i;
                       break; 
                    }
              }                    
            for(j=1;j<=i;j++)
             {
                   if(H[i].parent==0&&i!=min1)
                    {
                          min2=i;
                          break;
                    }
  
             }
           if(H[min2].wiget<H[min1].wiget)
               {
                    tmp=min1;
                    min1=min2;
                    min2=tmp;
               }
           for(j=1;j<=i;j++){
                 if(H[i].parent==0)
                    {
                      if(H[i].wiget<=H[min2].wiget&&i!=min1&&i!=min2)
                        {
                            min2=i;
                            if(H[min2].wiget<H[min1].wiget)
                              {
                                  tmp=min1;
                                  min1=min2;
                                  min2=tmp;
                              }     
                        }
                          
                    }
             }
                return 0;
       }




   int init_hufuman_tree(HTree &H,int n,int *w){
        int m=2n+1,i,s1,s2;
        if(n<=1) return 1; 
        if(!H=(HTree)malloc((m+1)sizeof(HNode))) return 1;
        for(i=1;i<=n;i++,w++) H[i]=(*w,0,0,0,0);
        for(i=n+1;i<=m;i++) H[i]=(0,0,0,0,0);
        for(i=n+1;i<=m;i++){
            select(H,i-1,&s1,&s2);
            H[s1].parent=i;H[s2].parent=i;
            H[i].wiget=H[s1].wiget+H[s2].wiget;
            H[i].lchild=s1;H[i].rchild=s2;
         }
            return 0;
      }
     
   int get_Hucode(HTree &H,int n){
       int j,i,c,f,start;
       char *cd=NULL;
       char **Hcode=(char**)malloc((n+1)sizeof(char*));
       if(!Hcode)return 1;
       Hcode[]=NULL;
       if(!cd=(char*)malloc((n+1)*sizeof(char)))return 1;
       cd[n]=‘/0‘;
       start=n-1;
       for(i=1;i<=n;i++)
        {
           for(c=i,f=H[c].parent;f!=0;c=f,f=H[f].parent){
                  if(H[f].lchild==c) {cd[start]=‘0‘;start--;}
                  else{cd[start]=‘1‘;start--}
            }
           char *code=(char*)malloc((n-start)sizeof(char));
           if(!code) return 1;
           strcpy(code,&char[start]);
           start=n-1;
           Hcode[i]=code;
        }
        free(cd);
         return 0;
}




      }
  

数据结构之哈夫曼树


联系
我们