Thread: Linked list inside an unbalanced BST or linked list inside a linked list c program

  1. #1
    Registered User
    Join Date
    Jul 2010
    Posts
    178

    Linked list inside an unbalanced BST or linked list inside a linked list c program

    Hello All,
    I am struggling with a linked list inside a BST, basically a linked list inside a linked list. I have completed the BST from a file read using an iterative approach to the BST because of the assigned function declaration. The part I am struggling with is getting the linked list inside the BST. What I am tasked with is to get the string length of the strings in the file and use that length to create the node number. eg. "Joe" = node number 3, "Dave" = node number 4. This part is completed. After that though, I need to get the strings in another linked list that is "linked" to each node. The reason is I can have two strings that are the same length. Say "Joe" & "Bob" which both need to go into node 3. Nodes cannot be duplicated, although at this moment, they are and that can be taken care of. My two structs are:
    Code:
    typedef struct data_string
    {
        char data[9];
        struct node_t *sleft;
        struct node_t *sright;
    }CHARstring;
    
    typedef struct node_t 
    {
        int node_num;
        struct data_string CHARstring;
        struct node_t *left;
        struct node_t *right;
    }node_t;
    How do I link the linked list to the node number. I am hoping someone could get me started. Here is my buildTree.c code although not all of it.
    Code:
     node_t *root = NULL, *newNode = NULL, *temp1 = NULL, *temp2 = NULL;
    
        if(regcomp(&regex, to_find, REG_EXTENDED | REG_NEWLINE) != 0)
        {
            fprintf(stderr, "Failed to compile regex '%s'\n", to_find);
            return NULL;
        }
    
        while(fgets(file, BUFF, fp) != NULL)
        {
            ++line_count;
            if((ret_val = regexec(&regex, file, 0, NULL, 0)) == 0)
            {
                printf("ERROR, non alphanumeric character on line %d\n", line_count);
                return NULL;
            }
    
            token = strtok(file, " \t\n\r");
            while (token != NULL)
            {
                digit_count = strlen(token);
                newNode = malloc(sizeof(node_t));
                newNode->left = newNode->right = NULL;
                newNode->node_num = digit_count;
                
                if(root == NULL)
                {
                    root = newNode;
                }
                else
                {
                    temp1 = root;
                    while (temp1 != NULL)
                    {
                        temp2 = temp1;
    
                        if(newNode->node_num > temp1->node_num)
                        {
                            temp1 = temp1->right;
                        }
                        else
                        {
                            temp1 = temp1->left;
                        }
                    }
                    
                    if(newNode->node_num > temp2->node_num)
                    {
                        temp2->right = newNode;
                    }
                    else
                    {
                        temp2->left = newNode;
                    }
                }
    
                token = strtok(NULL, " \t\n\r");
                printf("Token: %d\n", digit_count);
                printf("String: %s\n", newNode->CHARstring.data);
            }
    
        }
    
        return root;
    
        
    }

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    To clarify: are you asking how to add nodes to the btree such that nodes with the same key are added to the same btree node in a linked list headed by that btree node?

    If so, maybe structs like this would do:
    Code:
    typedef struct list_node list_node;
    struct list_node
    {
        char *str;
        list_node *next;
    };
    
    typedef struct btree_node btree_node;
    struct btree_node
    {
        int key;
        list_node *list;   /* build list off of here */
        btree_node *left;
        btree_node *right;
    };
    BTW: Since you don't really need a regex, it's best not to use it. It just complicates things. You can check for non-alphanumeric characters with a simple function that loops through the string and uses the isalnum() function prototyped in ctype.h.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    Registered User
    Join Date
    Jul 2010
    Posts
    178
    Quote Originally Posted by oogabooga View Post
    To clarify: are you asking how to add nodes to the btree such that nodes with the same key are added to the same btree node in a linked list headed by that btree node?

    If so, maybe structs like this would do:
    Code:
    typedef struct list_node list_node;
    struct list_node
    {
        char *str;
        list_node *next;
    };
    
    typedef struct btree_node btree_node;
    struct btree_node
    {
        int key;
        list_node *list;   /* build list off of here */
        btree_node *left;
        btree_node *right;
    };
    BTW: Since you don't really need a regex, it's best not to use it. It just complicates things. You can check for non-alphanumeric characters with a simple function that loops through the string and uses the isalnum() function prototyped in ctype.h.
    I believe that is what I am asking. To clarify my file will contains strings like
    Code:
    joe     clint james brint howard
    jimmy
    alexander
    
    me
    joe will be in node 3, clint, brint & james will be in node 5, howard & jimmy will be in node 6, etc. I get the node numbers from the string length of the strings in the file. Now when you say "build list off here, I am still at the point of how to bring along the rest of the items into a linked list. I appreciate your comments.
    Last edited by csharp100; 09-22-2013 at 06:03 PM. Reason: mispelling

  4. #4
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    What do you mean by "bring along the rest of the times"?
    In what sense "bring along"?
    What are "the rest of the times"?

    EDIT: Ohhhhh, items, the misspelling created a reasonable word and I was wondering if "times" were also involved.

    Anyway, I was thinking that as you extract tokens you would call an "add to binary tree" function that would find the appropriate btree node, and if that node existed it would already have a list attached to it of at least one member, and you'd add a new list node to the head or tail (or perhaps in sorted order) of that list. If the btree node doesn't exist, you create it and start a new list there.
    Last edited by oogabooga; 09-22-2013 at 06:14 PM.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  5. #5
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    I might suggest changing btree_node to bst_node or some such. There is a structure called a B-tree, which is quite different from a BST, and I was confused when I first read your post.

    @csharp100
    oogabooga's struct names are still more descriptive than yours, however, so I would adopt them. It will also make it more clear the relationship between your two data structures. He's also right about the regex, it's overkill.

    From your example, it appears that the node_num/key in the binary tree is the length of the strings. Given that you only allow for 9 characters in the list node, you only have room for 8 characters (remember, +1 for the NULL), which means you will only have at most 8 nodes in your binary tree. Binary trees are generally better suited for larger sets of data, otherwise the overhead of managing the tree outweighs the benefit of fast inserts, lookups and deletes. If you have such a small, fixed maximum string length, you would be better off with an array of 8 lists. And by the way, you should make that a #define, no magic numbers!

    However, if you really want to use a BST, then my first sugggestion is to stop thinking of this as some bastard hybrid data structure. There is a BST, and it has some arbitrary data stored in each node. Whether that data is an int, a float, a string or a linked list or strings is irrelevant to finding the correct place to insert or lookup a node. Same goes for your list. Work out your BST and list and test them separately, then write a function that combines bst_insert and list_insert. Also, I suggest you read up on BST tutorials. The recursive approach to insert and lookup are much simpler than the iterative one.

    Start by building a simpler BST, don't worry about the list part yet. Add a member to the tree node called count, make it an int. When you "insert" a string into the tree, if a node for that string length exists, simply increment count. Otherwise, create a new node, set count to 1 and insert that node in the tree. Something like:
    Code:
    bst_node *bst_insert(bst_node *root, const char *data, int len)
    {
        if root is NULL
            // create new node and set count to 1
        if len < root->key
            // recursively insert into left sub-tree
        else if len > root->key
            // recursively insert into right sub-tree
        else
            // increment count
    }
    Write similar bst_lookup, bst_delete and bst_print functions as needed. The print function is probably best done as an in-order traversal, which prints out the key/strlen of each node, and the count of how many strings of that length have been "inserted". This will be useful for testing. Write little bits at a time, testing as you go. When your BST code is done, you can move on to the list, knowing it works.

    Your list might need the following functions:
    Code:
    list_node *list_insert(list_node *head, const char *data)  // insert data into list, returning the new head
    list_node *list_find(list_node *head, const char *key)  // find key in list, returning pointer to the node
    list_node *list_delete(list_node *head, const char *key)  // delete node containing key from list, returning new head
    void list_print(list_node *head)  // print list
    Take the same approach as the BST. Keep it simple to start, and pretend the other half of your data structure doesn't exist. Write little bits at a time, testing as you go. Once you have that finished, you know the list half of your data structure will work. Not only that, you are keeping things loosely coupled. You may find later that you want a BST of BSTs, or of hash tables, or whatever. This way it will be much easier to swap out the list in each tree node for something else should you want to.

    All that's left is putting them together. So, in your tree, when you inserted, all you were doing was incrementing a count variable. Now, instead of that (or in conjunction with that), you just need your one-line call to your list_insert function, and you have a tree of lists.

  6. #6
    Registered User
    Join Date
    Jul 2010
    Posts
    178
    Quote Originally Posted by oogabooga View Post
    What do you mean by "bring along the rest of the times"?
    In what sense "bring along"?
    What are "the rest of the times"?

    EDIT: Ohhhhh, items, the misspelling created a reasonable word and I was wondering if "times" were also involved.

    Anyway, I was thinking that as you extract tokens you would call an "add to binary tree" function that would find the appropriate btree node, and if that node existed it would already have a list attached to it of at least one member, and you'd add a new list node to the head or tail (or perhaps in sorted order) of that list. If the btree node doesn't exist, you create it and start a new list there.
    Unfortunately I am not allowed any other functions. I can only have main.c, buildTree.c, traverseInorder.c, traversPreorder.c & traversePostorder.c.

  7. #7
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by csharp100 View Post
    Unfortunately I am not allowed any other functions. I can only have main.c, buildTree.c, traverseInorder.c, traversPreorder.c & traversePostorder.c.
    But those aren't functions. They're code files, presumably with multiple functions in each.

    @anduril: Argh! I should've remembered that b-tree was something else. I've never coded one, but I've certainly heard of it. BST it is.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  8. #8
    Registered User
    Join Date
    Jul 2010
    Posts
    178
    Quote Originally Posted by anduril462 View Post
    I might suggest changing btree_node to bst_node or some such. There is a structure called a B-tree, which is quite different from a BST, and I was confused when I first read your post.

    @csharp100
    oogabooga's struct names are still more descriptive than yours, however, so I would adopt them. It will also make it more clear the relationship between your two data structures. He's also right about the regex, it's overkill.

    From your example, it appears that the node_num/key in the binary tree is the length of the strings. Given that you only allow for 9 characters in the list node, you only have room for 8 characters (remember, +1 for the NULL), which means you will only have at most 8 nodes in your binary tree. Binary trees are generally better suited for larger sets of data, otherwise the overhead of managing the tree outweighs the benefit of fast inserts, lookups and deletes. If you have such a small, fixed maximum string length, you would be better off with an array of 8 lists. And by the way, you should make that a #define, no magic numbers!

    However, if you really want to use a BST, then my first sugggestion is to stop thinking of this as some bastard hybrid data structure. There is a BST, and it has some arbitrary data stored in each node. Whether that data is an int, a float, a string or a linked list or strings is irrelevant to finding the correct place to insert or lookup a node. Same goes for your list. Work out your BST and list and test them separately, then write a function that combines bst_insert and list_insert. Also, I suggest you read up on BST tutorials. The recursive approach to insert and lookup are much simpler than the iterative one.

    Start by building a simpler BST, don't worry about the list part yet. Add a member to the tree node called count, make it an int. When you "insert" a string into the tree, if a node for that string length exists, simply increment count. Otherwise, create a new node, set count to 1 and insert that node in the tree. Something like:
    Code:
    bst_node *bst_insert(bst_node *root, const char *data, int len)
    {
        if root is NULL
            // create new node and set count to 1
        if len < root->key
            // recursively insert into left sub-tree
        else if len > root->key
            // recursively insert into right sub-tree
        else
            // increment count
    }
    Write similar bst_lookup, bst_delete and bst_print functions as needed. The print function is probably best done as an in-order traversal, which prints out the key/strlen of each node, and the count of how many strings of that length have been "inserted". This will be useful for testing. Write little bits at a time, testing as you go. When your BST code is done, you can move on to the list, knowing it works.

    Your list might need the following functions:
    Code:
    list_node *list_insert(list_node *head, const char *data)  // insert data into list, returning the new head
    list_node *list_find(list_node *head, const char *key)  // find key in list, returning pointer to the node
    list_node *list_delete(list_node *head, const char *key)  // delete node containing key from list, returning new head
    void list_print(list_node *head)  // print list
    Take the same approach as the BST. Keep it simple to start, and pretend the other half of your data structure doesn't exist. Write little bits at a time, testing as you go. Once you have that finished, you know the list half of your data structure will work. Not only that, you are keeping things loosely coupled. You may find later that you want a BST of BSTs, or of hash tables, or whatever. This way it will be much easier to swap out the list in each tree node for something else should you want to.

    All that's left is putting them together. So, in your tree, when you inserted, all you were doing was incrementing a count variable. Now, instead of that (or in conjunction with that), you just need your one-line call to your list_insert function, and you have a tree of lists.
    I am not allowed any other functions. I have created a binary tree and completely agree the recursive approach would be much better. But how do you call an interface of:
    Code:
    node_t *buildTree(FILE *)
    recursively? I realize all of you are not privy to all the requirements of my assignment. If I could do this a simpler way, I would without hesitation. I have adopted oogabooga structs. The buildTree function must do everything. What is so ironic about this is the professor is a huge advocate of using functions. The whole way of doing this is assignment goes against all that I have been taught but I guess that is why it is assigned this way.

  9. #9
    Registered User
    Join Date
    Jul 2010
    Posts
    178
    Quote Originally Posted by oogabooga View Post
    But those aren't functions. They're code files, presumably with multiple functions in each.

    @anduril: Argh! I should've remembered that b-tree was something else. I've never coded one, but I've certainly heard of it. BST it is.
    You are correct, they are not fuctions. I did not word that correctly. The interfaces I am allowed are:
    Code:
    node_t *buildTree(FILE *)
    void traverseInorder(node_t*)
    void traversePreorder(node_t*)
    void traversePostorder(node_t*)
    That is all I can have.

  10. #10
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Hmmmmm, one thing that occurs to me is that an "interface" does not generally include all the functions in a code file. There can be others that are only use within the file. So not being able to add functions to the interface is not the same as not being able to add internal (static) functions to the code file.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  11. #11
    Registered User
    Join Date
    Jul 2010
    Posts
    178
    Quote Originally Posted by oogabooga View Post
    Hmmmmm, one thing that occurs to me is that an "interface" does not generally include all the functions in a code file. There can be others that are only use within the file. So not being able to add functions to the interface is not the same as not being able to add internal (static) functions to the code file.
    Sorry oogabooga, he explicitly states, "Building the tree (through one function) should be implemented in another source file buildTree.c"

  12. #12
    Registered User
    Join Date
    May 2009
    Posts
    4,036
    Quote Originally Posted by csharp100 View Post
    Sorry oogabooga, he explicitly states, "Building the tree (through one function) should be implemented in another source file buildTree.c"
    Based on on your reading of that; you also can NOT used any functions; I suggest asking the instructor because I think you are able to use other functions!
    You just must do the ones he requested in the files requested in order to support the interface he is testing. So, I suggest doing what was suggested.

    In other the words, use the interface required; but, use what implementation is best or at least maintainable.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  13. #13
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by csharp100 View Post
    Sorry oogabooga, he explicitly states, "Building the tree (through one function) should be implemented in another source file buildTree.c"
    Now that I stop and think about it, it's not really a recursive problem to insert a node into a bst. You just have to dig down into the tree to find the correct position, you don't need to keep track of where you've been for backtracking, which is what the recursion simplifies.

    So you have an outermost loop with fgets, reading a line at a time. Then you have the strtok loop inside that. Then you'll have a loop to find the location in the bst. At that point you either add a new bst node connected to a linked list with one node, or you insert a new list node into a preexisting list in a preexisting bst node.

    Give that a try and post some code to make this more concrete.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  14. #14
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Posting the exact requirements would help us help you. A lot. And I have to say, I'm with Tim here, I think the professor is saying you must code to the interface, but you can implement it however you want. I.e. make a bunch of static "helper" functions that are local to, say, buildTree.c. That actually ties in quite well with your professor's love of functions, and (presumably) his sense of good design. In fact, "programming to an interface, not an implementation" is a pretty core concept of good software design/architecture, and something you come across all the time. In fact, you already do this every time you use a library function, like fgets, malloc, etc. You don't care how they wrote it, whether they used a for or while loop, or how many temp variables. You just want to know that it follows all the rules that fgets is supposed to follow. But to be sure, double check with your professor.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 05-19-2012, 09:12 PM
  2. Declaring linked list inside linked list
    By blueboyz in forum C Programming
    Replies: 33
    Last Post: 04-20-2012, 10:13 AM
  3. linked list inside a structure
    By jerepops in forum C Programming
    Replies: 5
    Last Post: 12-14-2009, 08:22 PM
  4. Linked List inside Linked List
    By de4th in forum C++ Programming
    Replies: 1
    Last Post: 05-15-2006, 11:17 AM
  5. linked list inside array of structs- Syntax question
    By rasmith1955 in forum C Programming
    Replies: 14
    Last Post: 02-28-2005, 05:16 PM