Thread: Question About Huffman Tree

  1. #1
    Registered User
    Join Date
    Sep 2016
    Posts
    2

    Question About Huffman Tree

    I wish to implement a Huffman tree. But it seems like my program can't work correctly. I've been struggling with it for days!
    (Segmentation Fault) I guess there are some mistakes with the space of pointers, but I just don't know what's the problem.
    (btw,I printed all the nodes in the tree which is not exact hufftree. Well, it doesn't matter)
    Code:
    #include<stdio.h>
    #include<malloc.h>
    typedef struct huff{
        struct huff *left;
        struct huff *right;
        int data;
    } make;
    make *initial(int x[],int number);
    void print(make *c);
    int main(){
        int p,q[p];
        scanf("%d",&p);
        int delta;
        for(delta=0;delta<p;delta++){
            scanf("%d",&q[delta]);
        }
        make *root;
        root=initial(q,p);
    print(root);
        return 0;
    }
    make *initial(int x[],int number){
        make *y[number];
        int k;
        for(k=0;k<=number-1;k++){
            y[k]=(make *)malloc(sizeof(make));
            y[k]->data=x[k];
            y[k]->left=y[k]->right=NULL;
        }
        while(number>1){
            int i,j;
            make *t;
            for(j=number-1;j>=1;j--){
                for(i=0;i<=j-1;i++){
                    if(y[i]->data>y[i+1]->data){
                        t=y[i+1];
                        y[i+1]=y[i];
                        y[i]=t;
                    }
                    else {}
                }
            }
    make *p;
            p=(make *)malloc(sizeof(make));
            p->left=y[0];
            p->right=y[1];
            p->data=x[0]+x[1];
            number--;
            if(number>=3){
                y[0]=p;
                int se;
                for(se=1;se<=number-2;se++){
                    y[se]=y[se+1];
                }
            }
            else{}
    }
        make *q;
        q=(make *)malloc(sizeof(make));
        q->left=y[0];
        q->right=y[1];
        return (q);
    }
    void print(make *c){
        if(c!=NULL){
            printf("%d,",c->data);
            print(c->left);
            print(c->right);
        }
        else{}
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    You appear to have made a mistake early on:
    Code:
    int p,q[p];
    scanf("%d",&p);
    The problem is that you declared p to be a variable length array of length p, but you only set p after the declaration. You should have written:
    Code:
    int p;
    scanf("%d",&p);
    int q[p];
    though it would be wise to check that scanf returned 1 and that p is greater than 0 before creating q.

    Note that while variable length arrays are part of the standard, they became optional in the most recent version of the standard, and from what I understand Microsoft C compilers still don't support them to this day, so if you want your code to be more portable, you should use the malloc/free family of functions for dynamic memory management instead. In fact, I note that you included the non-standard <malloc.h> header; the correct standard header would be <stdlib.h>, and you should remember to free what you malloc.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help for novice re: Huffman tree
    By atlantis43 in forum C Programming
    Replies: 5
    Last Post: 03-03-2015, 09:16 PM
  2. Help with adaptive Huffman theory question
    By tms43 in forum C++ Programming
    Replies: 3
    Last Post: 12-03-2006, 12:24 PM
  3. huffman tree
    By blazer26 in forum C Programming
    Replies: 0
    Last Post: 04-25-2006, 03:39 PM
  4. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  5. yet another huffman tree problem
    By ygfperson in forum C++ Programming
    Replies: 2
    Last Post: 04-18-2002, 01:20 AM

Tags for this Thread