Alphabetic binary tree sorting

access violation (segmentation fault)

Page 1 of 1

4 Replies - 6201 Views - Last Post: 13 February 2010 - 07:50 AM Rate Topic: -----

#1 not1975  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 51
  • Joined: 26-December 06

Alphabetic binary tree sorting

Posted 10 February 2010 - 07:49 PM

This is my program for sorting words alphabetically into a binary tree. So far it only sorts based on the first character. I'm getting an access violation error and a crash with the insert() recursively called within insert.

#include <stdio.h>
#define STRING_LEN 100



struct node
{
    char word[STRING_LEN+1];
    struct node* left;
    struct node* right;
};

void insert(struct node* new, struct node* current)
{
    if(new->word[0] <= current->word[0])
    {
        if(current->left==NULL)
        {
            current->left = new;
        }
        else
            insert(current, new);
    }
        
    else
    {
        if(current->right == NULL)
            current->right = new; 
        else
            insert(current, new);
    }
}

void read_tree(struct node* node)
{
    printf("%s", node->word);
    if(node->left != NULL)
    {
        read_tree(node->left);
    }
    else if(node->right != NULL)
    {
        read_tree(node->right);
    }
}

int main()
{
    struct node* root_node = (struct node *) malloc(sizeof(struct node));;
    
    char word[STRING_LEN+1];
    int eof_flag = 0;
    
    FILE* word_file = fopen("C:\\wordlist.txt", "r");
    while(!eof_flag)
    {
        struct node* new_node= (struct node *) malloc(sizeof(struct node));
        
        if(fgets(new_node->word, STRING_LEN, word_file)==NULL)
        {
            eof_flag=1;
            break;
        }
        
        insert(new_node, root_node);
    }
    
    read_tree(root_node);
    
    system("PAUSE");
    
    if(fclose(word_file) != 0)
        return -1;
    else return 0;
}



This post has been edited by not1975: 10 February 2010 - 07:55 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Alphabetic binary tree sorting

#2 Keerigan  Icon User is offline

  • D.I.C Head

Reputation: 10
  • View blog
  • Posts: 55
  • Joined: 04-February 10

Re: Alphabetic binary tree sorting

Posted 10 February 2010 - 08:40 PM

Im not at my pc right now, so i don't really want to get into depth wiht this, but have you check out maps?
they are basically a struct with 2 items. The first one is the key that has to be unique for each struct, then the second can be whatever kind of data you want( including more structs or maps ).

The nice thing about this is that is that maps are always kept sorted by the key.

Don't know if that helps at all, but I thought that I would throw that out there before I put my phone away.
Was This Post Helpful? 0
  • +
  • -

#3 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Alphabetic binary tree sorting

Posted 11 February 2010 - 06:37 AM

One problem I see is that your root node is uninitialized. I am sorry I ran out of time to look this over but hopefully someone else will pick up the task.

I prefer myself to wrap things like a tree by a second struct that has a pointer to the root node, then have a function insertToTree(tree, node) -- on of the things this give you is you can check if tree.root_node == null then make the new node the root node, else scale the tree and insert.

there is something fishy about your insert routine but I just ran out of time before I could really look into it. I could be wrong but I could "almost" sware you should be doing something like this:
void insert(struct node* newone, struct node* current) {
    if (newone->word[0] <= current->word[0]) {
        if (current->left==NULL) {
            current->left = newone;
        } else {
            insert(newone, current->left);
        }
    } else {
        if (current->right == NULL) {
            current->right = newone;
        } else {
            insert(newone, current->right);
        }
    }
}
-- Note that code is UNTESTED and written off the cuff in like 30seconds -- please look it over before you use it!

also note, while 'new' is not a reserved word in C it is generally a good idea to treat it as one. Not a big deal but should you ever want to migrate you code to C++ it might cause trouble.
Was This Post Helpful? 0
  • +
  • -

#4 not1975  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 51
  • Joined: 26-December 06

Re: Alphabetic binary tree sorting

Posted 13 February 2010 - 07:11 AM

#include <stdio.h>
#define STRING_LEN 100

struct node
{
    char word[STRING_LEN+1];
    struct node* left;
    struct node* right;
};

void insert(struct node* new, struct node* current)
{
        
    //For now the program only sorts based on the first character
    if(new->word[0] <= current->word[0])
    {
        if(current->left==NULL)
        {
            current->left = new;
        }
        else
        {
            insert(current->left, new);
        }
    }
        
    else
    {
        if(current->right == NULL)
        {
            current->right = new; 
        }
        else
        {
            insert(current->right, new);
        }
    }
}

void read_tree(struct node* node)
{
    printf("%s", node->word);
    if(node->left != NULL)
    {
        read_tree(node->left);
    }
    if(node->right != NULL)
    {
        read_tree(node->right);
    }
}

int main()
{
    struct node* root_node = (struct node *) malloc(sizeof(struct node));
    root_node->word[0]=' ';
    root_node->word[1]='\n';
    root_node->word[2]='\0';
    root_node->left=NULL;
    root_node->right=NULL;
    
    char word[STRING_LEN+1];
    
    FILE* word_file = fopen("C:\\wordlist.txt", "r");
    while(1)
    {
        struct node* new_node= (struct node *) malloc(sizeof(struct node));
        
        if(fgets(new_node->word, STRING_LEN, word_file)==NULL)
            break;
        
        insert(new_node, root_node);
    }
    
    read_tree(root_node);
    
    system("PAUSE");
    
    if(fclose(word_file) != 0)
        return -1;
    else return 0;
}



I initialized the variables for root_node. I'm still getting the same access violation error in the insert routine. But now it shows it coming from the first if statement in insert:
 if(new->word[0] <= current->word[0]) 


I don't even know what that means. Is there something I'm doing with the arrays that's incorrect?
Was This Post Helpful? 0
  • +
  • -

#5 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6064
  • View blog
  • Posts: 23,518
  • Joined: 23-August 08

Re: Alphabetic binary tree sorting

Posted 13 February 2010 - 07:50 AM

Compiling with warnings on yields an issue:
tree.c:55: warning: implicit declaration of function ‘malloc’
tree.c:55: warning: incompatible implicit declaration of built-in function ‘malloc’

you need to include stdlib.h.

EDIT: If you're compiling as a C program, you should NEVER need to cast the return value of malloc. Requiring such in order to compile means exactly what you see above: you failed to include stdlib.h.

This post has been edited by JackOfAllTrades: 13 February 2010 - 07:52 AM
Reason for edit:: More info

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1