数据结构--赫夫曼树及其应用

------ 赫夫曼树和赫夫曼编码的存储表示------
[cpp]  
typedef struct {  
    unsigned int weight;  
    unsigned int parent,lchild,rchild;  
}HTNode,*HuffmanTree;  
typedef char ** HuffmanCode;  
   
void HuffmanCoding(HuffmanTree& HT,HuffmanCode & HC,int *w,int n)  {  
   
    if (n < 1) return;\  
    int m = 2* n + 1;  
    HT = (HuffmanTree) malloc (m+1)* sizeof(HTNode); //0 号单元未用  
    for ( HuffmanTree p = HT; i=1; i<=n; ++i; ++p; ++w)    
        *p = {*w,0,0,0,0};  
    for(; i<=m; ++i; ++p)  
        *p = {0,0,0,0};  
   
    for(i = n+1; i<=m; i++) {  //建立HuffmanTree  
   
        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;  
    }  
   
    HC = (HuffmanCode)malloc((n+1)* sizeof(char*));  
    cd = (char*) malloc(n* sizeof(char));  
    cd [n-1] = "\0";  
    for ( i=1; i<=n; i++) {  
        int start = n-1;  
        for ( c=i, f = HT[i].parent; f!=0; c=f; f = HT[f].parent )  
            if( HT[f].lchild == c )  cd [--start] = "0";  
            else cd [--start] = "1";  
        HC[i] = (char*) malloc ( (n-start)* sizeof(char));   
        strcyp(HC[i],&cd[start]);  
    }  
    free(cd);  
   
}  
 
------ 无栈非递归遍历赫夫曼树，求赫夫曼编码------
[cpp]  
HC = (HuffmanCode) malloc ( (n+1) *　sizeof(char*));   
int p = m, cdlen = 0;  
  
for ( int i=1; i<=m; ++i)  HT[i].weight = 0;  
  
while(p) {  
  
    if ( HT[p].weight == 0 ) {  
  
        HT[p].weight = 1;   
        if ( HT[p].lchild != 0) {  
            p = HT[p].lchild;   
            cd[cdlen++] = "0";  
        }else if ( HT[p].lchild == 0) {  
  
            HC[p] = (char*) malloc ((cdlen+1) * sizeof(char));  
            cd[cdlen] = "\0";   www.zzzyk.com
            strcpy(HC[p],cd);  
        }  
    }else if ( HP[p].weight == 1) {  
  
        HT[p].weight = 2;  
        if ( HT[p].rchild != 0) {  
            p = HT[p].rchild;  
            cd [cdlen++] = "1";  
        }else {  
            HT[p].weight = 0; p = HT[p].parent; --cdlen;  
        }  
    }      
}  
 

补充：软件开发 , C++ ,

上一个：POJ3006:Dirichlet's Theorem on Arithmetic Progressions
下一个：宏名字和括号间不能有空格!