HELP with Huffman Tree 
Author Message
 HELP with Huffman Tree

first of all, i apologize for posting a binary attachment earlier on.
below is my newest version, it constructs a tree, but somehow when i
try to run it, it always gives me a segmentation fault (which i think
is caused by the *head node). my professor was having a hard time
figuring out what's wrong with it... so i don't really expect anyone
to actually point it out quickly. if someone can just give me a
pointer to what function or what area i need to fix up, i would really
appreciate it.

===========================================================

/*
 * Name: Joshua Kuo             Assignment#5
 *
 * this program combines my assignment#3 and add on some more
 * to achieve huffman's compression. it uses a binary tree
 * structure to compress files into binary bits.
 *
 *      %prog input_file_name > output_file_name
 *
 * will read from input and write to output file
 */

#include <stdio.h>
#include <stdlib.h>

int to;                 /* total amount of characters */
int difBytes;           /* amount of different bytes */
int total(int o[]);             /* get the sum of values in o */
void sort(int n[], int m[]);    /* sorts n and m */
void print(int n[], int m[]);   /* prints the arrays */

/*
 * defines a node
 */
struct node
{
        int byte;               /* ASCII value */
        int count;              /* occurance */
        char code[20];  /* path */
        struct node *left;      /* pointer to left child */
        struct node *right;     /* pointer to right child */

Quote:
};

void printNodes(struct node *head);
/* print nodes */
int makeNodes(struct node *t[], int n[], int m[]);
/* makes nodes from n and m */
int makeTree(struct node *t[], struct node *p, int size);
/* adds in the new node deletes used nodes */
struct node *tinit(int n, int m);
/* makes a node */
struct node *makeHuffNode(struct node *a, struct node *b);
/* combines 2 nodes */
struct node *makeHuffTree(struct node *t[]);
/* builds the tree */

/*
 * constructs a leaf node
 */
struct node *tinit(int n, int m)
{
        struct node *p;
        p = (struct node*)malloc(sizeof(struct node));
        p -> byte = m;
        p -> count = n;
        return p;

Quote:
}

/*
 * checks if p is a leaf
 * return 1 if p is a leaf
 * return 0 if p is not a leaf
 */
int isLeaf(struct node *p){    
        /* if p is a leaf */
        if ((p -> left == NULL) && (p -> right == NULL)) return 1;

        /*if it isn't*/
        else return 0;

Quote:
}

/*
 * makes nodes from n and m and puts them in t.
 * n and m are arranged from greatest to least
 * this fucntion puts it in t from least to greatest...
*/
int makeNodes(struct node *t[], int counter[], int ascii[])
{
        int i,s;
        i = 0;
        s = difBytes - 1;

        while(s >= 0)
        {
        /* allocate space for node.. so it doesn't dissapear */
                t[s] = (struct node *) malloc (sizeof(struct node));
                t[s] -> byte = ascii[i];
                t[s] -> count = counter[i];
                s--;
                i++;
        }
        return 0;

Quote:
}

/*
 * constructs a parent node
 */
struct node *makeHuffNode(struct node *a, struct node *b)
{
        struct node *p;
        p = (struct node *) malloc(sizeof(struct node));
        p -> left = a;
        p -> right = b;
        p -> count = a -> count + b -> count;
        return p;

Quote:
}

/*
 * get array t, and a node p, size is the size of t[]
 * finds where p belongs in t and puts it there
 */
int makeTree(struct node *t[], struct node *p, int size)
{
        int i = size - 3;
        p = makeHuffNode(t[size-2], t[size-1]); /* make a new node */
        t[size-1] = NULL;
        t[size-2] = NULL;

        while (i >= 0)
        {
                /* append to the end */
                if (t[i] -> count >= p -> count)
                {
                        t[i+1] = p;
                        break;
                }

                /* insert at beginning */
                else if (i == 0 && t[i] -> count < p -> count)
                {
                        t[i+1] = t[i];
                        t[i] = NULL;
                        t[i] = p;
                }

                /* else shift it */
                else
                {
                        t[i+1] = t[i];
                        t[i] = NULL;
                }
                i--;
        } /* ends while loop */
        return 0;

Quote:
}

/*
 * makes a Huffman Tree
 */
struct node *makeHuffTree(struct node *t[])
{
        struct node *p;
        int size = difBytes;
        while(size >= 2)
        {
                /* while there is more than 2 nodes */
                if (size >= 2) makeTree(t, p, size);

                /* if there are 2 nodes left */
                else p = makeHuffNode(t[1], t[0]);
                size--;
        }
        return p;

Quote:
}

/*
 *  - RECURSION -
 * BASE CASE: when node is null, return
 * ELSE: go to right child and process, go to left child and process
 * traverses the tree pre order and puts in the code for each node
 */
void makeCode(struct node *head)
{
        if (head == NULL) return;

        /* append 0 to left child if head has a left child */
        else if (head -> left != NULL)
        {
                strcat(strcpy(head -> left -> code, head -> code),
"0");
                makeCode(head -> left);
        }

        /* append 1 to right child if head has a right child */
        else if (head -> right != NULL)
        {
                strcat(strcpy(head -> right -> code, head -> code),
"1");
                makeCode(head -> right);
        }

Quote:
}

/*
 * - RECURSION -
 * BASE CASE: when head is null, return
 * ELSE: print left node, print middle (if it's a leaf), print right
 * node prints out only leaf nodes
 */
void printNodes(struct node *head)
{
        if (head == NULL) printf("Tree is empty\n");

        printNodes(head -> left);
        if (isLeaf(head) == 1)
        {
                printf("ASCII: %d\t", head -> byte);
                printf("Char: ");
                putchar(head -> byte);
        }
        printNodes(head -> right);

Quote:
}

/*
 * - RECURSION -
 * BASE CASE: when head is null, return 0
 * BASE CASE: when head is leaf, return 1;
 * ELSE: return byteCount(left) + byteCount(right)
 *
 */
int byteCount(struct node *head)
{
        /* if the tree root is null */
        if (head == NULL) return 0;
        if (isLeaf(head) == 1) return 1;
        else return byteCount(head -> left) + byteCount(head ->
right);

Quote:
}

/*
 * - RECURSION -
 * BASE CASE: when head is null, return 0;
 * ELSE: return bit length + bitCount(left) + bitCOunt(right)
 * gets the amount of bits needed to encode the file
 */
int bitCount(struct node *head)
{
        if (head == NULL) return 0;
        else return (head -> count * strlen(head -> code))
                                                                +
bitCount(head -> left) + bitCount(head -> right);

Quote:
}

/*
 * --- from ass3 ---
 * prints out array results
 */
int printResult(int a[], int b[])
{
        int i;
        printf("RESULT:\n");
        for (i = 0; i < 256; i++)
        {
                /* only print the chars found */
                if (a[i] != 0)
                {
                        printf("ASCII=%3d\t", b[i]);
                        printf("Char=");
                        putchar(b[i]);
                        printf("\t");
                        printf("Count=%3d\n", a[i]);
                }
        }
        return 0;

Quote:
}

/*
 * --- from ass3 ---
 * sorts array -- insertion sort
 * the largest element gets moved up to the start
 * of the array
 */
int sortArray(int a[], int b[])
{
        int x, y, A, B;
        for (x = 1; x < 256; x++) {
                y = x;
                A = a[x];
                B = b[x]; /* swap b array elements */

                /* comparison and swapgin */
                while (( y > 0) && (a[y-1] < A)) {
                        a[y] = a[y-1];
                        b[y] = b[y-1]; /* swap b array elements */
                        y--;
                }

                a[y] = A;
                b[y] = B; /* swap swap b array elements*/
        }
        return 0;

Quote:
}

/**************     MAIN     *******************/

/*
 * for now it only tests assignment 3 stuff
 */
int main(int argc, char *argv[])
{
        int c;                  /* stores the ASCII character */
        int i;                  /* iteration counter */
        int counter[256];               /* stores the count */
        int ascii[256];                 /* stores the ASCII info */
        FILE *infp;             /* input file pointer */
        struct node *t[256];            /*construct an array ofnodes*/
        struct node *head;              /* constrcut the header node*/

        /* error handler: wrong number of parameters */
        if (argc != 2)
        {
                printf("Wrong number of parameters\n");
                exit(0);
        }

        /* open the input file */
        infp = fopen(argv[1], "rb");

        /* initialize both arrays */
        for (i = 0; i < 256; i++)
        {
                counter[i] = 0;
                ascii[i] = i;
        }

        /* iterate thru the file and record result in array a[] */
        while ((c = getc(infp)) != EOF)
                counter[c]++;

        /* sorts input and print output to screen */
        sortArray(counter, ascii);
        printResult(counter, ascii);

        /*!!!!!!!!!!!!!!!!!these are the root of the problem!!!!!!!*/

        makeNodes(t, counter, ascii);
        head = makeHuffTree(t);
        printNodes(head);

        /*
        printf("%d\n", head -> count);
        printf("%d\n", head -> left -> count);
        printf("%d\n", head -> right -> count);
        */

        /* close input file */
        fclose(infp);
        return 0;

Quote:
}

/******* UNIX OUTPUT ***********/

/*

%./a.out input.txt

ASCII= 32       Char=   Count= 53
ASCII= 49       Char=1  Count= 14
ASCII= 51       Char=3  Count=  8
ASCII= 50       Char=2  Count=  6
ASCII= 53       Char=5  Count=  5
ASCII= 10       Char=
        Count=  2
ASCII= 48       Char=0  Count=  2
ASCII= 55       Char=7  Count=  2
ASCII= 57       Char=9  Count=  2
ASCII= 52       Char=4  Count=  1
Tree is empty
Segmentation fault (core dumped)

*/



Tue, 20 Aug 2002 03:00:00 GMT  
 HELP with Huffman Tree
You've already got an important clue, say 'Tree is empty'.
Try to find out what you have omitted.

There must be a ng such as comp.lang.debugging

Good luck!



Quote:
> first of all, i apologize for posting a binary attachment earlier on.
> below is my newest version, it constructs a tree, but somehow when i
> try to run it, it always gives me a segmentation fault (which i think
> is caused by the *head node). my professor was having a hard time
> figuring out what's wrong with it... so i don't really expect anyone
> to actually point it out quickly. if someone can just give me a
> pointer to what function or what area i need to fix up, i would really
> appreciate it.

> ===========================================================

> /*
>  * Name: Joshua Kuo Assignment#5
>  *
>  * this program combines my assignment#3 and add on some more
>  * to achieve huffman's compression. it uses a binary tree
>  * structure to compress files into binary bits.
>  *
>  * %prog input_file_name > output_file_name
>  *
>  * will read from input and write to output file
>  */

> #include <stdio.h>
> #include <stdlib.h>

> int to; /* total amount of characters */
> int difBytes; /* amount of different bytes */
> int total(int o[]); /* get the sum of values in o */
> void sort(int n[], int m[]); /* sorts n and m */
> void print(int n[], int m[]); /* prints the arrays */

> /*
>  * defines a node
>  */
> struct node
> {
> int byte; /* ASCII value */
> int count; /* occurance */
> char code[20]; /* path */
> struct node *left; /* pointer to left child */
> struct node *right; /* pointer to right child */
> };

> void printNodes(struct node *head);
> /* print nodes */
> int makeNodes(struct node *t[], int n[], int m[]);
> /* makes nodes from n and m */
> int makeTree(struct node *t[], struct node *p, int size);
> /* adds in the new node deletes used nodes */
> struct node *tinit(int n, int m);
> /* makes a node */
> struct node *makeHuffNode(struct node *a, struct node *b);
> /* combines 2 nodes */
> struct node *makeHuffTree(struct node *t[]);
> /* builds the tree */

> /*
>  * constructs a leaf node
>  */
> struct node *tinit(int n, int m)
> {
> struct node *p;
> p = (struct node*)malloc(sizeof(struct node));
> p -> byte = m;
> p -> count = n;
> return p;
> }

> /*
>  * checks if p is a leaf
>  * return 1 if p is a leaf
>  * return 0 if p is not a leaf
>  */
> int isLeaf(struct node
{
> /* if p is a leaf */
> if ((p -> left == NULL) && (p -> right == NULL)) return 1;

> /*if it isn't*/
> else return 0;
> }

> /*
>  * makes nodes from n and m and puts them in t.
>  * n and m are arranged from greatest to least
>  * this fucntion puts it in t from least to greatest...
> */
> int makeNodes(struct node *t[], int counter[], int ascii[])
> {
> int i,s;
> i = 0;
> s = difBytes - 1;

> while(s >= 0)
> {
> /* allocate space for node.. so it doesn't dissapear */
> t[s] = (struct node *) malloc (sizeof(struct node));
> t[s] -> byte = ascii[i];
> t[s] -> count = counter[i];
> s--;
> i++;
> }
> return 0;
> }

> /*
>  * constructs a parent node
>  */
> struct node *makeHuffNode(struct node *a, struct node *b)
> {
> struct node *p;
> p = (struct node *) malloc(sizeof(struct node));
> p -> left = a;
> p -> right = b;
> p -> count = a -> count + b -> count;
> return p;
> }

> /*
>  * get array t, and a node p, size is the size of t[]
>  * finds where p belongs in t and puts it there
>  */
> int makeTree(struct node *t[], struct node *p, int size)
> {
> int i = size - 3;
> p = makeHuffNode(t[size-2], t[size-1]); /* make a new node */
> t[size-1] = NULL;
> t[size-2] = NULL;

> while (i >= 0)
> {
> /* append to the end */
> if (t[i] -> count >= p -> count)
> {
> t[i+1] = p;
> break;
> }

> /* insert at beginning */
> else if (i == 0 && t[i] -> count < p -> count)
> {
> t[i+1] = t[i];
> t[i] = NULL;
> t[i] = p;
> }

> /* else shift it */
> else
> {
> t[i+1] = t[i];
> t[i] = NULL;
> }
> i--;
> } /* ends while loop */
> return 0;
> }

> /*
>  * makes a Huffman Tree
>  */
> struct node *makeHuffTree(struct node *t[])
> {
> struct node *p;
> int size = difBytes;
> while(size >= 2)
> {
> /* while there is more than 2 nodes */
> if (size >= 2) makeTree(t, p, size);

> /* if there are 2 nodes left */
> else p = makeHuffNode(t[1], t[0]);
> size--;
> }
> return p;
> }

> /*
>  *  - RECURSION -
>  * BASE CASE: when node is null, return
>  * ELSE: go to right child and process, go to left child and process
>  * traverses the tree pre order and puts in the code for each node
>  */
> void makeCode(struct node *head)
> {
> if (head == NULL) return;

> /* append 0 to left child if head has a left child */
> else if (head -> left != NULL)
> {
> strcat(strcpy(head -> left -> code, head -> code),
> "0");
> makeCode(head -> left);
> }

> /* append 1 to right child if head has a right child */
> else if (head -> right != NULL)
> {
> strcat(strcpy(head -> right -> code, head -> code),
> "1");
> makeCode(head -> right);
> }
> }

> /*
>  * - RECURSION -
>  * BASE CASE: when head is null, return
>  * ELSE: print left node, print middle (if it's a leaf), print right
>  * node prints out only leaf nodes
>  */
> void printNodes(struct node *head)
> {
> if (head == NULL) printf("Tree is empty\n");

> printNodes(head -> left);
> if (isLeaf(head) == 1)
> {
> printf("ASCII: %d\t", head -> byte);
> printf("Char: ");
> putchar(head -> byte);
> }
> printNodes(head -> right);
> }

> /*
>  * - RECURSION -
>  * BASE CASE: when head is null, return 0
>  * BASE CASE: when head is leaf, return 1;
>  * ELSE: return byteCount(left) + byteCount(right)
>  *
>  */
> int byteCount(struct node *head)
> {
> /* if the tree root is null */
> if (head == NULL) return 0;
> if (isLeaf(head) == 1) return 1;
> else return byteCount(head -> left) + byteCount(head ->
> right);
> }

> /*
>  * - RECURSION -
>  * BASE CASE: when head is null, return 0;
>  * ELSE: return bit length + bitCount(left) + bitCOunt(right)
>  * gets the amount of bits needed to encode the file
>  */
> int bitCount(struct node *head)
> {
> if (head == NULL) return 0;
> else return (head -> count * strlen(head -> code))
> +
> bitCount(head -> left) + bitCount(head -> right);
> }

> /*
>  * --- from ass3 ---
>  * prints out array results
>  */
> int printResult(int a[], int b[])
> {
> int i;
> printf("RESULT:\n");
> for (i = 0; i < 256; i++)
> {
> /* only print the chars found */
> if (a[i] != 0)
> {
> printf("ASCII=%3d\t", b[i]);
> printf("Char=");
> putchar(b[i]);
> printf("\t");
> printf("Count=%3d\n", a[i]);
> }
> }
> return 0;
> }

> /*
>  * --- from ass3 ---
>  * sorts array -- insertion sort
>  * the largest element gets moved up to the start
>  * of the array
>  */
> int sortArray(int a[], int b[])
> {
> int x, y, A, B;
> for (x = 1; x < 256; x++) {
> y = x;
> A = a[x];
> B = b[x]; /* swap b array elements */

> /* comparison and swapgin */
> while (( y > 0) && (a[y-1] < A)) {
> a[y] = a[y-1];
> b[y] = b[y-1]; /* swap b array elements */
> y--;
> }

> a[y] = A;
> b[y] = B; /* swap swap b array elements*/
> }
> return 0;
> }

> /**************     MAIN     *******************/

> /*
>  * for now it only tests assignment 3 stuff
>  */
> int main(int argc, char *argv[])
> {
> int c; /* stores the ASCII character */
> int i; /* iteration counter */
> int counter[256]; /* stores the count */
> int ascii[256]; /* stores the ASCII info */
> FILE *infp; /* input file pointer */
> struct node *t[256]; /*construct an array ofnodes*/
> struct node *head; /* constrcut the header node*/

> /* error handler: wrong number of parameters */
> if (argc != 2)
> {
> printf("Wrong number of parameters\n");
> exit(0);
> }

> /* open the input file */
> infp = fopen(argv[1], "rb");

> /* initialize both arrays */
> for (i = 0; i < 256; i++)
> {
> counter[i] = 0;
> ascii[i] = i;
> }

> /* iterate thru the file and record result in array a[] */
> while ((c = getc(infp)) != EOF)
> counter[c]++;

> /* sorts input and print output to screen */
> sortArray(counter, ascii);
> printResult(counter, ascii);

> /*!!!!!!!!!!!!!!!!!these are the root of the problem!!!!!!!*/

> makeNodes(t, counter, ascii);
> head = makeHuffTree(t);
> printNodes(head);

> /*
> printf("%d\n", head -> count);
> printf("%d\n", head -> left -> count);
> printf("%d\n", head -> right -> count);
> */

> /* close input file */
> fclose(infp);
> return 0;
> }

> /******* UNIX OUTPUT ***********/

> /*

> %./a.out input.txt

> ASCII= 32       Char=   Count= 53
> ASCII= 49       Char=1  Count= 14
> ASCII= 51       Char=3  Count=  8
> ASCII= 50       Char=2  Count=  6
> ASCII= 53       Char=5  Count=  5
> ASCII= 10       Char=
>         Count=  2
> ASCII= 48       Char=0  Count=  2
> ASCII= 55       Char=7  Count=  2
> ASCII= 57       Char=9  Count=  2
> ASCII= 52       Char=4  Count=  1
> Tree is empty
> Segmentation fault (core dumped)

> */



Sat, 24 Aug 2002 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. HELP with Huffman Tree Traversal - huff2.c (1/1)

2. HELP with Huffman Tree Traversal - huff2.c (1/1)

3. HELP with Huffman Tree Traversal - huff2.c (0/1)

4. Help on Huffman trees 2

5. Help on Huffman trees

6. Huffman coding/huffman tree

7. HELP Huffman Tree Traversal

8. Smallest Huffman Binary Decoding Tree Header

9. huffman tree source code

10. huffman tree/coding

11. Need Help! Huffman Code

12. Help with AVL tree (balanced tree)

 

 
Powered by phpBB® Forum Software