Hi,
You are right, googling it, I got a few codes, even in that code I am facing problem in understanding sorting part, especially after base nodes are defined...
Code:
// huffman.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>
#include <math.h>
#include <string.h>
#define NUMBYTES 256
#define NUMBITS 16
#define INPUTFILENAME "input.huf"
#define OUTPUTFILENAME "output.huf"
#define TEMPFILENAME "huffman.tmp"
typedef struct _HUFFNODE {
char byte;
long freq;
struct _HUFFNODE *parent;
struct _HUFFNODE *left;
struct _HUFFNODE *right;
} HUFFNODE;
typedef struct _HUFFTAB {
char byte;
char numbits;
long freq;
long bits[NUMBITS];
} HUFFTAB;
FILE *f;
long fsize, numnodes, numbasenodes;
long freq_tab[NUMBYTES]; // Frequency table
HUFFNODE *nodelist[NUMBYTES];
HUFFNODE *basenode[NUMBYTES];
HUFFNODE *templist[NUMBYTES];
HUFFTAB code_tab[NUMBYTES];
/////////////////////////////////
// Return file size in bytes //
/////////////////////////////////
long filesize(FILE *f)
{
long pos, fsize;
pos = ftell(f);
fseek(f, 0L, SEEK_END);
fsize = ftell(f);
fseek(f, pos, SEEK_SET);
return fsize;
}
/////////////////////////////////////////////////////////
// Read input file to memory to speed up compression //
/////////////////////////////////////////////////////////
char *huffman_readinputstream(char *inputstream)
{
char *stream;
f = fopen(inputstream, "r+b");
assert(f != NULL);
fsize = filesize(f);
stream = (char *)calloc(fsize, sizeof(char));
assert(stream != NULL);
fread(stream, fsize, 1, f);
fclose(f);
return stream;
}
////////////////////////////
// Make frequency table //
////////////////////////////
void huffman_buildfreq(char *stream)
{
long k;
for (k = 0; k < NUMBYTES; k++)
freq_tab[k] = 0;
for (k = 0; k < fsize; k++)
freq_tab[stream[k]]++;
}
/////////////////////////////////////////////////////////
// Sort node list table using straight insertion sort //
/////////////////////////////////////////////////////////
void huffman_sortnodelist(HUFFNODE *nodes[])
{
HUFFNODE *node;
long i, j, k;
for (i = 0; i < numnodes-1; i++) {
k = i;
node = nodes[i];
for (j = i+1; j < numnodes; j++)
if (nodes[j]->freq < node->freq) { //Surprisingly breaks at this point in 2nd sort...
k = j;
node = nodes[j];
}
if (k != i) {
node = nodes[i];
nodes[i] = nodes[k];
nodes[k] = node;
}
}
}
//////////////////////////
// Build huffman tree //
//////////////////////////
void huffman_buildtree(char *stream)
{
HUFFNODE *node;
HUFFNODE *node1, *node2; // Two nodes with smallest frequency
long k, n;
// Build frequency table
huffman_buildfreq(stream);
// Build base nodes
numbasenodes = 0;
for (k = 0; k < NUMBYTES; k++) {
if (freq_tab[k] > 0) {
node = (HUFFNODE *)calloc(1, sizeof(HUFFNODE));
assert(node != NULL);
node->byte = k;
node->freq = freq_tab[k];
node->parent = NULL;
node->left = NULL;
node->right = NULL;
nodelist[numbasenodes] = node;
basenode[numbasenodes] = node;
templist[numbasenodes] = node;
numbasenodes++;
}
}
// Build huffman tree
numnodes = numbasenodes;
n = numnodes;
while (--n > 0) {
// Sort node list go get two nodes with minor frequency
huffman_sortnodelist(nodelist);
node1 = nodelist[0];
node2 = nodelist[1];
// Make new node and link nodes
node = (HUFFNODE *)calloc(1, sizeof(HUFFNODE));
node->byte = 'x';
node->freq = node1->freq + node2->freq;
node->left = node1;
node->right = node2;
node->parent = NULL;
node1->parent = node;
node2->parent = node;
// Add new node and remove old two
nodelist[0] = node;
for (k = 1; k < n; k++)
nodelist[k] = nodelist[k+1];
nodelist[n] = NULL;
templist[numnodes++] = node;
}
for (k = 0; k < numnodes; k++)
nodelist[k] = templist[k];
}
////////////////////
// Main program //
////////////////////
int main()
{
char *stream;
long k;
// Read input stream
stream = huffman_readinputstream(INPUTFILENAME);
// Build huffman tree
huffman_buildtree(stream);
return 0;
}
have just mentioned sort and tree build part
Code:
for (j = i+1; j < numnodes; j++)
if (nodes[j]->freq < node->freq)
after 1st sort, it always breaks at this point...I can't understand why..