huffman算法源代码.txt

数据结构里比较常见到的压缩算法。希望对大家有用。

} 
/* initialize freq tree */ 
void StartHuff() 
{ 
        int i, j; 
        for (i = 0; i < N_CHAR; i++) { 
                freq[i] = 1; 
                son[i] = i + T; 
                prnt[i + T] = i; 
        } 
        i = 0; j = N_CHAR; 
        while (j <= R) { 
                freq[j] = freq[i] + freq[i + 1]; 
                son[j] = i; 
                prnt[i] = prnt[i + 1] = j; 
                i += 2; j++; 
        } 
        freq[T] = 0xffff; 
        prnt[R] = 0; 
} 
/* reconstruct freq tree */ 
void reconst() 
{ 
        int i, j, k; 
        unsigned f, l; 
        /* halven cumulative freq for leaf nodes */ 
        j = 0; 
        for (i = 0; i < T; i++) { 
                if (son[i] >= T) { 
                        freq[j] = (freq[i] + 1) / 2; 
                        son[j] = son[i]; 
                        j++; 
                } 
        } 
        /* make a tree : first, connect children nodes */ 
        for (i = 0, j = N_CHAR; j < T; i += 2, j++) { 
                k = i + 1; 
               f = freq[j] = freq[i] + freq[k]; 
                for (k = j - 1; f < freq[k]; k--); 
                k++; 
                l = (j - k) * 2; 
                /* movmem() is Turbo-C dependent 
                   rewritten to memmove() by Kenji */ 
                /* movmem(&freq[k], &freq[k + 1], l); */ 
                (void)memmove(&freq[k + 1], &freq[k], l); 
                freq[k] = f; 
                /* movmem(&son[k], &son[k + 1], l); */ 
                (void)memmove(&son[k + 1], &son[k], l); 
                son[k] = i; 
        } 
        /* connect parent nodes */ 
        for (i = 0; i < T; i++) { 
                if ((k = son[i]) >= T) { 
                        prnt[k] = i; 
                } else { 
                        prnt[k] = prnt[k + 1] = i; 
                } 
        } 
} 
/* update freq tree */ 
void update(int c) 
{ 
        int i, j, k, l; 
        if (freq[R] == MAX_FREQ) { 
                reconst(); 
        } 
        c = prnt[c + T]; 
        do { 
                k = ++freq[c]; 
                /* swap nodes to keep the tree freq-ordered */ 
                if (k > freq[l = c + 1]) { 
                        while (k > freq[++l]); 
                        l--; 
                        freq[c] = freq[l]; 
                       freq[l] = k; 
                        i = son[c]; 
                        prnt[i] = l; 
                        if (i < T) prnt[i + 1] = l; 
                        j = son[l]; 
                        son[l] = i; 
                        prnt[j] = c; 
                        if (j < T) prnt[j + 1] = c; 
                        son[c] = j; 
                        c = l; 
                } 
        } while ((c = prnt[c]) != 0);   /* do it until reaching the root */ 
} 
unsigned code, len; 
void EncodeChar(unsigned c) 
{ 
        unsigned i; 
        int j, k; 
        i = 0; 
        j = 0; 
        k = prnt[c + T]; 
        /* search connections from leaf node to the root */ 
        do { 
                i >>= 1; 
                /* 
                if node's address is odd, output 1 
                else output 0 
                */ 
                if (k & 1) i += 0x8000; 
                j++; 
        } while ((k = prnt[k]) != R); 
        Putcode(j, i); 
        code = i; 
        len = j; 
        update(c); 
} 
void EncodePosition(unsigned c) 
{ 
        unsigned i; 
        /* output upper 6 bits with encoding */ 
        i = c >> 6; 
        Putcode(p_len[i], (unsigned)p_code[i] << 8); 
        /* output lower 6 bits directly */ 
        Putcode(6, (c & 0x3f) << 10); 
} 
void EncodeEnd() 
{ 
        if (putlen) { 
                putc(putbuf >> 8, outfile); 
                codesize++; 
        } 
} 
int DecodeChar() 
{ 
        unsigned c; 
        c = son[R]; 
        /* 
         * start searching tree from the root to leaves. 
         * choose node #(son[]) if input bit == 0 
         * else choose #(son[]+1) (input bit == 1) 
         */ 
        while (c < T) { 
                c += GetBit(); 
               c = son[c]; 
        } 
        c -= T; 
        update(c); 
        return c; 
} 
int DecodePosition() 
{ 
        unsigned i, j, c; 
        /* decode upper 6 bits from given table */ 
        i = GetByte(); 
        c = (unsigned)d_code[i] << 6; 
        j = d_len[i]; 
        /* input lower 6 bits directly */ 
        j -= 2; 
        while (j--) { 
                i = (i << 1) + GetBit(); 
        } 
        return c | i & 0x3f; 
} 
/* Compression */ 
void Encode(void)  /* Encoding/Compressing */ 
{ 
        int  i, c, len, r, s, last_match_length; 
        fseek(infile, 0L, 2); 
        textsize = ftell(infile); 
        if (fwrite(&textsize, sizeof textsize, 1, outfile) < 1) 
                Error("Unable to write");       /* write size of original te 
xt / 
        if (textsize == 0) 
                return; 
        rewind(infile); 
        textsize = 0;                   /* rewind and rescan */ 
        StartHuff(); 
        InitTree(); 
        s = 0; 
        r = N - F; 
        for (i = s; i < r; i++) 
                text_buf[i] = ' '; 
        for (len = 0; len < F && (c = getc(infile)) != EOF; len++) 
                text_buf[r + len] = c; 
        textsize = len; 
        for (i = 1; i <= F; i++) 
                InsertNode(r - i); 
        InsertNode(r); 
        do { 
                if (match_length > len) 
                        match_length = len; 
                if (match_length <= THRESHOLD) { 
                        match_length = 1; 
                        EncodeChar(text_buf[r]); 
                } else { 
                        EncodeChar(255 - THRESHOLD + match_length); 
                        EncodePosition(match_position); 
                } 
                last_match_length = match_length; 
                for (i = 0; i < last_match_length && 
                                (c = getc(infile)) != EOF; i++) { 
                        DeleteNode(s); 
                        text_buf[s] = c; 
                        if (s < F - 1) 
                                text_buf[s + N] = c; 
                        s = (s + 1) & (N - 1); 
                        r = (r + 1) & (N - 1); 
                        InsertNode(r); 
                } 
                if ((textsize += i) > printcount) { 
                        printf("%12ld\r", textsize); 
                        printcount += 1024; 
                } 
                while (i++ < last_match_length) { 
                        DeleteNode(s); 
                        s = (s + 1) & (N - 1); 
                        r = (r + 1) & (N - 1); 
                        if (--len) InsertNode(r); 
                } 
        } while (len > 0); 
        EncodeEnd(); 
        printf("input: %ld bytes\n", textsize); 
        printf("output: %ld bytes\n", codesize); 
} 
void Decode(int pnum,int all)  /* Decoding/Uncompressing */ 
{ 
        int  i, j, k, r, c; 
        unsigned long int  count; 
        if (fread(&textsize, sizeof textsize, 1, infile) < 1) 
                Error("Unable to read");  /* read size of original text */ 
        if (textsize == 0) 
                return; 
        StartHuff(); 
        for (i = 0; i < N - F; i++) 
                text_buf[i] = ' '; 
        r = N - F; 
        for (count = 0; count < textsize; ) { 
                c = DecodeChar(); 
                if (c < 256) { 
                        putc(c, outfile); 
                        text_buf[r++] = c; 
                        r &= (N - 1); 
                        count++; 
                } else { 
                        i = (r - DecodePosition() - 1) & (N - 1); 
                        j = c - 255 + THRESHOLD; 
                        for (k = 0; k < j; k++) { 
                                c = text_buf[(i + k) & (N - 1)]; 
                                putc(c, outfile); 
                                text_buf[r++] = c; 
                                r &= (N - 1); 
                                count++; 
                        } 
                } 
                if (count > printcount) { 
                        process(0,count*100L/textsize); 
                        process(1,pnum+count*(long)all/textsize); 
                        printcount += 1024; 
                } 
        } 
        process(0,99); 
        process(1,pnum+all); 
} 
//解码调用程序 
int exact(char *s1,char *s2,int pnum,int all) 
{ 
   char s[100]; 
   infile=fopen(s1,"rb"); 
   if(infile==NULL) 
    { 
     sprintf(s,"File %s not found",s1); 
     OutWindow(s); 
     return 1; 
    } 
   sprintf(s,"%s\\%s",destpath,s2); 
   outfile=fopen(s,"wb"); 
   Decode(pnum,all); 
   fclose(infile); 
   fclose(outfile); 
   textsize=0; 
   codesize=0; 
   printcount = 0; 
   getbuf = 0; 
   getlen = 0; 
   putbuf = 0; 
   putlen = 0; 
   return 0; 
}