Thread: memmory addresses not working out or me screwing somthing up

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    662

    memmory addresses not working out or me screwing somthing up

    i have broken my code down a little so it is more manageable
    header:
    Code:
    #ifndef BST_H_INCLUDED
    #define BST_H_INCLUDED
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <stdbool.h>
    #include <string.h>
    
    typedef struct Bin_Node
    {
        int data;
        struct Bin_Node *left;
        struct Bin_Node *right;
    }Bin_Node;
    
    typedef struct Bin_Tree
    {
        struct Bin_Node *root; //same as head node in a linked list
        int node_count;
    }Bin_Tree;
    
    typedef struct Trunk
    {
        struct Trunk *previous;
        char mystr[20];
    }Trunk;
    
    Bin_Tree *create_tree(void);
    Bin_Tree *initalize_tree(Bin_Tree *tree);
    Bin_Node *create_node(void);
    Bin_Node *initalize_node(Bin_Node *node, int data);
    bool insert_node(Bin_Node **root, Bin_Node *node);
    void print_tree(const Bin_Node *root);
    void destroy_tree(Bin_Node *root);
    void insert(Bin_Tree *tree, int node_data);
    void print(const Bin_Tree *tree);
    void destroy(Bin_Tree *tree);
    
    // functions created to use c++ code
    Trunk *create_trunk(void);
    Trunk *initalize_trunk(Trunk *p, char strpassed[]);
    
    // copied from c++ code
    void show_trunks(Trunk *p);
    void print_tree_and_trunk(Bin_Node *root, Trunk *p, bool isleft);
    
    #endif // BST_H_INCLUDED
    i have added some printf statements in the print tree function to get the address of the node and its children's address's lines 69 and 70 of the following code
    Code:
    #include "bst.h"
    
    Bin_Tree *create_tree(void)
    {
        Bin_Tree *tmp_tree = malloc(sizeof(Bin_Tree));
    
        assert(tmp_tree != NULL);
        tmp_tree = initalize_tree(tmp_tree);
        return tmp_tree;
    }
    
    Bin_Tree *initalize_tree(Bin_Tree *tree)
    {
        tree->node_count = 0;
        tree->root = NULL;
    
        return tree;
    }
    
    Bin_Node *create_node(void)
    {
        return malloc(sizeof(Bin_Node));
    }
    
    Bin_Node *initalize_node(Bin_Node *node, int data)
    {
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    
        return node;
    }
    
    bool insert_node(Bin_Node **root, Bin_Node *node)
    {
        if (!*root) //parent node has no children??
        {
            *root = node;
            return true;
        }
        else
        {
            //printf("the value of nodes root = %d the address of node root = %p\n",(*root)->data, &(*root));
            if ((*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
            {
                return insert_node(&(*root)->right, node);
            }
            else if ((*root)->data != node->data)
            {
                return insert_node(&(*root)->left, node);
            }
        }
        return false; // the node already existed
    }
    
    void print_tree(const Bin_Node *root)
    {
        if (!root)
        {
            return;
        }
    
        if (root->left) //parent node has a child to the left
        {
            print_tree(root->left);
            printf("searching left child of %d\n", root->data);
        }
    
        printf("\nnode data = %d node address = %p\n", root->data, &root);
        printf("node left = %p node right = %p\n", root->left, root->right);
    
        if (root->right) //parent node has a child to the right
        {
            print_tree(root->right);
            printf("searching right child of %d\n", root->data);
        }
    }
    
    void destroy_tree(Bin_Node *root)
    {
        if (root) //parent has children
        {
            destroy_tree(root->left);
            destroy_tree(root->right);
            free(root);
            printf("node deleated\n");
        }
    }
    
    void insert(Bin_Tree *tree, int node_data)
    {
        Bin_Node *root = tree->root, *node;
    
        node = create_node();
        assert(node != NULL);
        node = initalize_node(node, node_data);
    
    
        if (!insert_node(&root, node)) //node already exists
        {
            free(node);
            fprintf(stderr, "value already exists\n");
        }
        else
        {
            if (!tree->root)
            {
                tree->root = node;
                //printf("tree->root = %p\n", tree->root);
            }
            tree->node_count++;
        }
    
    }
    
    void print(const Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        print_tree(root);
        print_tree_and_trunk(root, NULL, false);
        printf("\nthere are %d nodes in the tree\n\n", tree->node_count);
    }
    
    void destroy(Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        destroy_tree(root);
    }
    
    // functions created to use c++ code
    Trunk *create_trunk(void)
    {
        return malloc(sizeof(Trunk));
    }
    
    Trunk *initalize_trunk(Trunk *p, char strpassed[])
    {
        Trunk *tmp_trunk = create_trunk();
    
        assert(tmp_trunk != NULL);
        tmp_trunk->previous = p;
        strcpy(tmp_trunk->mystr, strpassed);
        return tmp_trunk;
    }
    
    // functions copied from c++ code
    void show_trunks(Trunk *p)
    {
        if (!p)
        {
            return;
        }
    
        show_trunks(p->previous);
        printf("%s", p->mystr);
    }
    
    void print_tree_and_trunk(Bin_Node *root, Trunk *p, bool isleft)
    {
        if (!root)
        {
            //printf("free memory here?\n");
            //free(p);
            return;
        }
    
        char prev_str[] = "    ";
        Trunk *tmp_trunk = initalize_trunk(p, prev_str); //this line added instead of new Trunk(prev, prev_str);
    
        print_tree_and_trunk(root->left, tmp_trunk, true);
    
        if (!p)
        {
            strcpy(tmp_trunk->mystr, "---");
        }
        else if (isleft)
        {
            strcpy(tmp_trunk->mystr, ".---");
            strcpy(prev_str, "   |");
        }
        else
        {
            strcpy(tmp_trunk->mystr, "`---");
            strcpy(p->mystr, prev_str);
        }
    
        show_trunks(tmp_trunk);
        printf("%d\n", root->data);
    
        if (p)
        {
            strcpy(p->mystr, prev_str);
        }
    
        strcpy(tmp_trunk->mystr, "   |");
        print_tree_and_trunk(root->right, tmp_trunk, false);
    
        if (tmp_trunk)
        {
            free(tmp_trunk);
        }
    }
    and lastly main
    Code:
    #include "bst.h"
    
    void insert_trunk(Bin_Tree *tree);
    
    int main()
    {                   //10,6, 3, 9, 2, 3, 13, 54, 20, 43
        int i, nums[] = {1, 2, 3};
        Bin_Tree *tree;//, *tree_trunk;
    
        tree = create_tree();
        for (i = 0; i < 3; i++)
        {
            insert(tree, nums[i]);
        }
        print(tree);
        destroy(tree);
        //tree_trunk = create_tree();
        //insert_trunk(tree_trunk);
        //print(tree_trunk);
        //destroy(tree_trunk);
        free(tree);
        //free(tree_trunk);
    
        return 0;
    }
    
    void insert_trunk(Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        root = create_node();
        assert(root != NULL);
        root = initalize_node(root, 1);
        tree->root = root;
    /*
        root->left = create_node();
        assert(root->left != NULL);
        root->left = initalize_node(root->left, 2);
    //*/
        root->right = create_node();
        assert(root->right != NULL);
        root->right = initalize_node(root->right, 3);
    /*
        root->left->left = create_node();
        assert(root->left->left != NULL);
        root->left->left = initalize_node(root->left->left, 4);
        root->left->right = create_node();
        assert(root->left->right != NULL);
        root->left->right = initalize_node(root->left->right, 5);
        root->right->left = create_node();
        assert(root->right->left != NULL);
        root->right->left = initalize_node(root->right->left, 6);
    //*/
        root->right->right = create_node();
        assert(root->right->right != NULL);
        root->right->right = initalize_node(root->right->right, 7);
    //*/
    }
    if i run this i get the following out put
    Code:
    node data = 1 node address = 0x7ffc6249a268
    node left = (nil) node right = 0x5630434472a0
    
    node data = 2 node address = 0x7ffc6249a248
    node left = (nil) node right = 0x5630434472c0
    
    node data = 3 node address = 0x7ffc6249a228
    node left = (nil) node right = (nil)
    searching right child of 2
    searching right child of 1
    ---1
        `---2
            `---3
    
    there are 3 nodes in the tree
    
    node deleated
    node deleated
    node deleated
    
    Process returned 0 (0x0)   execution time : 0.001 s
    Press ENTER to continue.
    the output doesn't make any sense to me as the tree is obviously connected together yet the address's (if i have got them correctly ) are different to the left/right pointers of the node above. ie suppose the node with the data of 2 right pointer points to x then the address of the node with the data of 3 should be x
    coop

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,497
    > printf("\nnode data = %d node address = %p\n", root->data, &root);
    Remove the & from the last parameter.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    thank you. i read in the book the other day that anyone who understand pointers loves c anyone who doesn't understand pointers hates c and is wasting their time. i just cant seem to get my head around when to use which version. I had this issue in my maths a level. there were a couple of things i just couldn't grasp we spent ages on them and no matter what i tried i always came up with the wrong answer. in the end we had to leave it and just hope it didn't come up in the exam

  4. #4
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    im confusing myself now i have changed bstlib
    Code:
    #include "bst.h"
    
    Bin_Tree *create_tree(void)
    {
        Bin_Tree *tmp_tree = malloc(sizeof(Bin_Tree));
    
        assert(tmp_tree != NULL);
        tmp_tree = initalize_tree(tmp_tree);
        return tmp_tree;
    }
    
    Bin_Tree *initalize_tree(Bin_Tree *tree)
    {
        tree->node_count = 0;
        tree->root = NULL;
    
        return tree;
    }
    
    Bin_Node *create_node(void)
    {
        return malloc(sizeof(Bin_Node));
    }
    
    Bin_Node *initalize_node(Bin_Node *node, int data)
    {
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    
        return node;
    }
    
    bool insert_node(Bin_Node **root, Bin_Node *node)
    {
        if (!*root) //parent node has no children??
        {
            *root = node;
            return true;
        }
        else
        {
            printf("the value of the node = %d the value of nodes root = %d the address of node root = %p\n", node->data, (*root)->data, *root);
            if ((*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
            {
                return insert_node(&(*root)->right, node);
            }
            else if ((*root)->data != node->data)
            {
                return insert_node(&(*root)->left, node);
            }
        }
        return false; // the node already existed
    }
    
    void print_tree(const Bin_Node *root)
    {
        if (!root)
        {
            return;
        }
    
        if (root->left) //parent node has a child to the left
        {
            print_tree(root->left);
            printf("searching left child of %d\n", root->data);
        }
    
        printf("\nnode data = %d node address = %p\n", root->data, root);
        printf("node left = %p node right = %p\n", root->left, root->right);
    
        if (root->right) //parent node has a child to the right
        {
            print_tree(root->right);
            printf("searching right child of %d\n", root->data);
        }
    }
    
    void destroy_tree(Bin_Node *root)
    {
        if (root) //parent has children
        {
            destroy_tree(root->left);
            destroy_tree(root->right);
            free(root);
            printf("node deleated\n");
        }
    }
    
    void insert(Bin_Tree *tree, int node_data)
    {
        Bin_Node *root = tree->root, *node;
    
        node = create_node();
        assert(node != NULL);
        node = initalize_node(node, node_data);
    
    
        if (!insert_node(&root, node)) //node already exists
        {
            free(node);
            fprintf(stderr, "value already exists\n");
        }
        else
        {
            if (!tree->root)
            {
                tree->root = node;
                printf("tree->root = %p\n", tree->root);
            }
            tree->node_count++;
        }
    
    }
    
    void print(const Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        printf("address of the root is %p\n", root);
        print_tree(root);
        print_tree_and_trunk(root, NULL, false);
        printf("\nthere are %d nodes in the tree\n\n", tree->node_count);
    }
    
    void destroy(Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        destroy_tree(root);
    }
    
    // functions created to use c++ code
    Trunk *create_trunk(void)
    {
        return malloc(sizeof(Trunk));
    }
    
    Trunk *initalize_trunk(Trunk *p, char strpassed[])
    {
        Trunk *tmp_trunk = create_trunk();
    
        assert(tmp_trunk != NULL);
        tmp_trunk->previous = p;
        strcpy(tmp_trunk->mystr, strpassed);
        return tmp_trunk;
    }
    
    // functions copied from c++ code
    void show_trunks(Trunk *p)
    {
        if (!p)
        {
            return;
        }
    
        show_trunks(p->previous);
        printf("%s", p->mystr);
    }
    
    void print_tree_and_trunk(Bin_Node *root, Trunk *p, bool isleft)
    {
        if (!root)
        {
            //printf("free memory here?\n");
            //free(p);
            return;
        }
    
        char prev_str[] = "    ";
        Trunk *tmp_trunk = initalize_trunk(p, prev_str); //this line added instead of new Trunk(prev, prev_str);
    
        print_tree_and_trunk(root->left, tmp_trunk, true);
    
        if (!p)
        {
            strcpy(tmp_trunk->mystr, "---");
        }
        else if (isleft)
        {
            strcpy(tmp_trunk->mystr, ".---");
            strcpy(prev_str, "   |");
        }
        else
        {
            strcpy(tmp_trunk->mystr, "`---");
            strcpy(p->mystr, prev_str);
        }
    
        show_trunks(tmp_trunk);
        printf("%d\n", root->data);
    
        if (p)
        {
            strcpy(p->mystr, prev_str);
        }
    
        strcpy(tmp_trunk->mystr, "   |");
        print_tree_and_trunk(root->right, tmp_trunk, false);
    
        if (tmp_trunk)
        {
            free(tmp_trunk);
        }
    }
    i have un-commented line 43 and added in the value of the node to be added into the tree and un-commented line 109.

    i get the following output
    Code:
    tree->root = 0x564a9c6d2280
    the value of the node = 2 the value of nodes root = 1 the address of node root = 0x564a9c6d2280
    the value of the node = 3 the value of nodes root = 1 the address of node root = 0x564a9c6d2280
    the value of the node = 3 the value of nodes root = 2 the address of node root = 0x564a9c6d26b0
    address of the root is 0x564a9c6d2280
    
    node data = 1 node address = 0x564a9c6d2280
    node left = (nil) node right = 0x564a9c6d26b0
    
    node data = 2 node address = 0x564a9c6d26b0
    node left = (nil) node right = 0x564a9c6d26d0
    
    node data = 3 node address = 0x564a9c6d26d0
    node left = (nil) node right = (nil)
    searching right child of 2
    searching right child of 1
    ---1
        `---2
            `---3
    
    there are 3 nodes in the tree
    
    node deleated
    node deleated
    node deleated
    
    Process returned 0 (0x0)   execution time : 0.001 s
    Press ENTER to continue.
    what i am trying to achieve with all these printf's is where i can put a line of code to update another member in the node struct so it knows what its parent is so when i come to do rotations i don't loose where i am.
    coop

  5. #5
    Registered User
    Join Date
    May 2019
    Posts
    209
    @cooper1200,

    Working backwards (most recent post)....

    I'm not 100% sure what the question is here, at least specifically....as in what is confusing?

    Since we're on different compilers we may have slightly different results to expect, but there's a details about %p in printf formatting you should attend. They should be cast to a void *, because of the way the compiler pushes the arguments on the stack. For example, you may be pushing a Bin_Node *, but printf doesn't have a clue what a Bin_Node is.

    Now, I get the same results with or without these casts, but technically the behavior is "undefined" if the type being pushed isn't a void *.

    I'm guessing, but maybe you're confused by the fact the printout declares root "moved"?

    That's normal, because during recursion, each recursion thinks of the "root" as a descendent, not "The" root of the entire tree.

    Actually, where you mention concern for where the parent is, usually the algorithms of a tree structure track the parent by the recursion itself. Is it clear in your mind that each recursive call has it's own memory of the state of things? Is it clear that's due to the stack?

    I'm not sure what you're specifically confused about though, so let's discuss.

    As to pointers being tough to "get", that's rather common.

    I think the situation you fixed recently was the confusion as to when to provide the address of the pointer, or the pointer.

    This is understandable, but with practice and experience it becomes more familiar.

    Since that can wind through all tributaries, I'll ask that you pose specific inquiries on the subject.

    C, being an assembler (historically), does work with pointers frequently, so familiarity is essential for your own comfort. A dedicated exercise may be in order, perhaps at another time unless you find it gets in the way here.

    Factually, the subject is nearly identical to that of assembly programming, in that you have the same basic confusing notions, but it is worse only in that the assembly language(s) have little to give you any hint, where C has a little.
    Last edited by Niccolo; 06-13-2019 at 01:23 PM.

  6. #6
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    im confused because i don't seem to get the right results tree root points to the first node.... so node 1's parent should be the tree root node two's parent should be node 1 and node three's parent should be node 2 but i dont think i am getting that

  7. #7
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    im also wondering that if the addresses are correct if i can replace the printf's with node->parent (when it exists) = *root

  8. #8
    Registered User
    Join Date
    May 2019
    Posts
    209
    @cooper1200,

    The printout is confusing because of where the printf's are reporting. You're getting "in process" information that may confuse.

    I tried this, see if you like the (crowded) result:

    In print_tree_and_trunk, where the printf prints the data of the node, I added:

    Code:
        printf("%d A:%p L:%p R:%p\n", root->data, (void *)root, (void *)root->left, (void *)root->right);
    Which shows in the tree diagram what the node addresses are.

    To be clear, AVL should not require the node holds the parent.

    Are you choosing to do that just for display?

    It would pose an uneccesary burden on the algorithm, and could confuse your efforts to maintain "parent" correctly during rotations.
    Last edited by Niccolo; 06-13-2019 at 01:50 PM.

  9. #9
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    i need to find away of assigning the parent node to the child's nodes parent pointer. the tree at the moment is unbalanced i need to do a left rotate and to do that i need to know which node is parent of which node so i dont loos track of them (i think)

  10. #10
    Registered User
    Join Date
    May 2019
    Posts
    209
    No, you don't.

    Seriously, unless you just want to have the parent for your own purpose, I promise you (and I've had my coffee, reviewed the material, I'm clear on this) the parent member of the node will only serve to confuse and confound.

    Don't do it because you think it is the way the AVL algorithm should be implemented. It isn't.

    The rotations happen from the parent's perspective, which is defined by the point of the recursion where it is performed.

    Did you "get" my questions on what the stack is? Are you clear on what the stack is and how it works with recursion?

  11. #11
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    ok it looks like i am getting the parent node address or at least the results from your line match the results from mine.. trouble is with this is every time i run it i get slightly differing addresses so its hard to visualize and confirm my findings

  12. #12
    Registered User
    Join Date
    May 2019
    Posts
    209
    @cooper1200,

    Quote Originally Posted by cooper1200 View Post
    ok it looks like i am getting the parent node address or at least the results from your line match the results from mine.. trouble is with this is every time i run it i get slightly differing addresses so its hard to visualize and confirm my findings
    HAHA....well, yes, you will (get different addresses from one run to another).

    Everything will be relative - it's tough to make that stick from run to run.

    Ok, so is the stack firm and clear in your mind?
    Last edited by Niccolo; 06-13-2019 at 02:05 PM.

  13. #13
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    i think the stack is last in first out and you can only work at the top level, this imaginary block is like a magazine in a rifle you can only load it from the top 1 round at a time and you can only empty it 1 round at a time. when you remove a round the ones below it are pushed up one slot (sorry for the mixed metaphore)

    my understanding of recurstion is at the point of calling its self the value computed is put on the stack and so on untill it reaches its conclustion then it pops each value off the stack as it unwinds. for example

    Code:
    int myrecurse(int x)
    {
        if (x == 3)
        {
            return x;
        }
        return x + myrecurse(x + 1)
    }
    if i send x = 1 into the function
    x=1 gets put on the stack x now = 2
    x=2 gets put on the stack x now = 3
    x = 3 so return 3
    get the 2 off the stack and add three to it x=5
    get the 1 off the stack and add the 1 to x so x = 6
    return 6

  14. #14
    Registered User
    Join Date
    May 2019
    Posts
    209
    @cooper1200,

    That's fairly good. I tend to think of it as a stack of cards. You deal out, say, 5 cards, one atop the other face up. The top card is current. It is popped by tossing it away, revealing the card underneath.

    Last in First out...LIFO. Like a stack of cards.


    ...but I want to expand on the subject a little.

    The stack is implemented in modern CPUs (we'll assume Intel for now) with a devoted register. It points to the memory allocated at launch for the stack.

    Every function call involves the stack. This is the part I want to be clear about. It is not just the data involved.

    When a function call is made the most important thing that happens is that the address of the program machine code is pushed onto the stack. This is how the computer knows where to return when the call is completed.

    In theory, the parameters going into the function are pushed on the stack. Technically, the optimizer may fiddle with this, but in theory they go on the stack as part of calling the function.

    When the function is entered, all locally allocated data is placed on the stack. This is key because it is how recursion works in your example. You could say each recursion (or each function call) naturally creates a structure of data involving everything from the return address to the parameters to the local data allocated inside the function.

    This is how AVL "knows" the parent. It happens to be the parameter pushed onto the stack to make the function call. You got that part correctly.

    In AVL, the parent rotates the children. When I saw you thought you needed the node to "know" the parent, it seemed to me that you were thinking the children rotate themselves.

    It is the stack that remembers the structure of the tree during insertion/deletion/search/traversal.

    Is is also how AVL rotates.

    I'll be interested as you get to the point of introducing balance, and your plan to do it. There's quite a bit I can see that needs attention in the existing code to facilitate it.

    Does your debugger have a call stack view? It can be helpful for the development phase you're entering.
    Last edited by Niccolo; 06-13-2019 at 02:23 PM.

  15. #15
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    i was just working on the rotating functions for the moment. but i was thinking of having three more members in the node left height , right height and balance factor of the node (left height - right height) that can then be checked for the range -1 to 1. calculating the height of the parent of those node(s) can be calculated (i think) by adding the left height of each node together + 1 same for the right. i think the height of each node can be done recursively a little like my example above.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 08-19-2011, 06:53 PM
  2. Working with memory addresses
    By Fujy in forum C++ Programming
    Replies: 7
    Last Post: 01-18-2010, 09:31 AM
  3. Memmory Issues and Threads
    By ddod in forum Windows Programming
    Replies: 2
    Last Post: 08-13-2004, 10:30 AM
  4. Freeing memmory - Automatic?
    By Vber in forum C Programming
    Replies: 4
    Last Post: 04-23-2003, 04:43 AM
  5. Memmory Allocation
    By MethodMan in forum C Programming
    Replies: 4
    Last Post: 04-16-2002, 01:56 PM

Tags for this Thread