huff.cpp

非常好用的五子棋游戏源码

// Created:10-20-98
// By Jeff Connelly

// My version of Huffman encoding

#include "stdafx.h"
#define EXPORTING
#include "comprlib.h"
#include <stdio.h>
#include <stdlib.h>

typedef struct tagTREE
{
    tagTREE* left;
    tagTREE* right;
    int weight;
} TREE;

static int freq[0x100];
static TREE* top;

// Builds the 'freq' frequency array based on input 
static void build_freq_table()
{
    while (!end_of_data())
        ++freq[read_byte()];
}

// Compares tree pointed to by 'a' and tree pointed to by 'b'
static int compare_tree_weight(TREE* a, TREE* b)
{
    return (a->weight < b->weight ? -1 : +1);
}

#define INVALID       0xFFFFFFFFL       // Invalid weight, ignore

// Builds a Huffman tree based on 'freq' array
static void build_tree()
{
    register int i, j = 0;
    int topsize;

    top = (tagTREE*)malloc(0x100);

    if (!top)
        EXCEPTION (ERR_MEMORY, "Failed to allocate memory for top of tree"
                               "build_tree()", "");

    // Copy the weights
    for (i = 0; i < 0xFF; ++i)
    {
        if (freq[i])
            top[i].weight = freq[i];
        else
            top[i].weight = INVALID;             // Skip this
        top[i].left = top[i].right = 0;          // No branches yet
    }



void huffman_encode()
{
    register char c;
    register int i, j;
    int size;
    TREE* node1;
    TREE* node2;

    // Build the frequency table and reset position
    build_freq_table();
    beginning_of_data();

    // Figure the size of the frequency table excluding zeros so we can
    // allocate memory
    for (i = 0; i < 0xFF; ++i)
    {
        if (freq[i])
            ++size;
    }

    // Allocate the memory
    top = malloc(size * sizeof(TREE));
    if (!top)
        EXCEPTION(ERR_MEMORY, "Failed to allocate memory for top of tree",
                              "huffman_encode()");

    // Now copy the weights
    j = 0;
    for (i = 0; i < 0xFF; ++i)
    {
        if (freq[i])            // If non-zero, add it
        {
            top[j].weight = freq[i];
            top[j].value = i;
            top[j].left = top[j].right = NULL;    // No branches yet
            printf ("%x (%d)\n", top[j].weight, top[j].value);
            ++j;
        }
    }

    while(true)
    {
        // Sort them using 'qsort' so we know the lowest
        qsort(&top, 1, size, compare_tree_weight);

        // 'node1' and 'node2' are the two lowest weights
        node1 = &top[0];
        node2 = &top[1];

        printf ("Lowest: %d, %d\n", node1->weight, node2->weight);

        if (!node1 || !node2)
            break;



        break;
    }
}