Thread: Enter and write out words into a tree of nodes

  1. #16
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    Quote Originally Posted by Salem View Post
    Yes, this looks like it's sorted to me, at least according to the dictionary that I have.

    > What would be the difference between char word[64 + 1] (in struct Tnode) and node->word = new char[64+1];
    You don't need to call delete[] node->word; later on.
    Ok,thanks. Are there any semantical or logical differences?I' ve tried to implement char word[64+1],but it did' t get compiled.
    Is an additional difference that in node->word = new char[64+1]; memory gets requested dynamically and in char word[64+1] it is "static"?

  2. #17
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,668
    These are the only code changes.
    Code:
    $ diff foo.cpp main.cpp
    9c9
    <      char* word; 
    ---
    >      char word[64+1]; 
    20c20
    <            node->word = new char[64+1]; 
    ---
    >            //node->word = new char[64+1]; 
    99c99
    <        delete root->word; 
    ---
    >        //delete root->word; 
    102d101
    <
    No it's nothing to do with things being static.

    The memory for char word[64] is allocated at the same time as the rest of Tnode when you call malloc.

    Try
    cout << "Node size=" << sizeof(Tnode) << endl;
    before and after the change from pointer to array.
    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. #18
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    Quote Originally Posted by Salem View Post
    These are the only code changes.
    Code:
    $ diff foo.cpp main.cpp
    9c9
    <      char* word; 
    ---
    >      char word[64+1]; 
    20c20
    <            node->word = new char[64+1]; 
    ---
    >            //node->word = new char[64+1]; 
    99c99
    <        delete root->word; 
    ---
    >        //delete root->word; 
    102d101
    <
    No it's nothing to do with things being static.

    The memory for char word[64] is allocated at the same time as the rest of Tnode when you call malloc.

    Try
    cout << "Node size=" << sizeof(Tnode) << endl;
    before and after the change from pointer to array.
    Ok understood. So everything will be same,right? I mean logical.
    char* word works the same way as char word[64+1]..

  4. #19
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,668
    Well they have a functional equivalence (both are useful for storing up to 64 character strings), but they're not the same thing in a literal sense (sizeof is different for both for example).
    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.

  5. #20
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    Quote Originally Posted by Salem View Post
    Well they have a functional equivalence (both are useful for storing up to 64 character strings), but they're not the same thing in a literal sense (sizeof is different for both for example).
    Hmm.If someone asks you "You used char* word instead of char word[64+1] in struct Tnode (with the same code afterwards) what would be your answer?
    Maybe I will understand it then..

  6. #21
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,668
    Well my initial question would be why you didn't use std::string in place of either char* or char array.

    That aside, the question is like asking a carpenter whether a chisel or a saw is better.
    It really depends on what you're trying to achieve.

    The char array simplifies allocation at the expense of being able to change your mind later, when you discover a really long string.
    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.

  7. #22
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    Quote Originally Posted by Salem View Post
    Well my initial question would be why you didn't use std::string in place of either char* or char array.

    That aside, the question is like asking a carpenter whether a chisel or a saw is better.
    It really depends on what you're trying to achieve.

    The char array simplifies allocation at the expense of being able to change your mind later, when you discover a really long string.
    This is my final code:

    Code:
    #include <iostream>
    #include <string>
    #include <string.h>
    using namespace std;
    struct Tnode
    {
            char word[64+1];
            int count;
            Tnode* left;
            Tnode* right;
    };
    class Tree
    {
            public:
            Tnode* addNode(Tnode* root, string word);
            void printTree(Tnode* root, int indent);
            void alphabeticPrintTree(Tnode* root);
            void printTree(Tnode* root);
            void freeTree(Tnode* root);
    };
    
    Tnode* Tree::addNode(Tnode* root, string word)
    {
            Tnode* node;
            if (!root)
            {
                    node = new Tnode;
                    strcpy(node->word, word.c_str());
                    node->left = 0;
                    node->right = 0;
                    node->count = 1;
                    return (node);
            }
    
            int cmp = strcmp(word.c_str(), root->word);
            if (cmp < 0)
            {
                    node = addNode(root->left, word);
                    if(!root->left)
                    {
                            root->left = node;
                    }
            }
            else if (cmp > 0)
            {
                    node = addNode(root->right, word);
                    if(!root->right)
                    {
                            root->right = node;
                    }
            }
            else
            {
                    root->count++;
            }
            return (node);
    }
    
    void Tree::printTree(Tnode* root, int indent)
    {
            if(!root)
            {
                    return;
            }
            cout << string(indent, ' ') << root->word << "[" << root->count << "]" << endl;
            printTree(root->left, indent+4);
            printTree(root->right, indent+6);
    }
    
    void Tree::alphabeticPrintTree(Tnode* root)
    {
            if(!root)
            {
                    return;
            }
            alphabeticPrintTree(root->left);
            cout << root->word << "[" << root->count << "]" << endl;
            alphabeticPrintTree(root->right);
    }
    
    void Tree::printTree(Tnode* root)
    {
            printTree(root, 0);
    }
    
    void Tree::freeTree(Tnode* root)
    {
            if(!root)
            {
                    return;
            }
            freeTree(root->left);
            freeTree(root->right);
            delete root;
     }
    
    int main(int argc, char* argv[])
    {
            Tree tree;
            Tnode* root = 0;
            string word;
            for(int i = 1; i < argc; i++)
            {
                    word = string(argv[i]);
                    Tnode* node = tree.addNode(root, word);
                    if (!root)
                    {
                            root = node;
                    }
            }
            cout << "Tree:" << endl;
            tree.printTree(root);
            cout << "Alphabetical:" << endl;
            tree.alphabeticPrintTree(root);
            tree.freeTree(root);
    }
    Now I want to change 2 things:

    1.) I want that if a word is longer than 64 characters it should be cut after it (Word with 80 chars => node with 64 chars). How I can realize that?
    2.) If there is no more memory for "new" the program should print out a message. How can be this done?

  8. #23
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    How can I change this part that it will copy just the first 64 characters?I searched for something in c_str() but didn' t find anything.

    Code:
    strcpy(node->word, word.c_str());

  9. #24
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,668
    Maybe strncpy.

    But note this won't append a \0 if it results in the string being truncated.
    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.

  10. #25
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    Quote Originally Posted by Salem View Post
    Maybe strncpy.

    But note this won't append a \0 if it results in the string being truncated.
    I' ve tried this

    snprintf(word.c_str(), word.size()-1, "%s", node->word);

    But it didn`t run.What is wrong here?

  11. #26
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,668
    > But it didn`t run.What is wrong here?
    You didn't pay attention to what I wrote.
    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.

  12. #27
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    Quote Originally Posted by Salem View Post
    > But it didn`t run.What is wrong here?
    You didn't pay attention to what I wrote.
    I' ve changes this:
    Code:
    struct Tnode
    {
            char word[10];
            int count;
            Tnode* left;
            Tnode* right;
    };
    
    ...
    Tnode* node;
            if (!root)
            {
                    node = new Tnode;
                    strncpy(node->word, word.c_str(), word.size()-1);
      node->word[word.size()-1] = '\0';
                    node->left = 0;
                    node->right = 0;
                    node->count = 1;
                    return (node);
            }
    ...
    Input: /home/t540972/test ==> tnode hello c++ foo faz

    Output:

    Tree:
    hell[1]
    c+[1]
    fo[1]
    fa[1]
    Alphabetical:
    c+[1]
    fa[1]
    fo[1]
    hell[1]

    Something is wrong here... Where is my mistake?
    Last edited by Joe1903; 11-17-2016 at 03:53 AM.

  13. #28
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,668
    > strncpy(node->word, word.c_str(), word.size()-1);
    You need to limit by the MINIMUM of
    - the size of what you're copying from
    - the size of what you're copying to

    If you strncpy from a small string into a large string and use the destination size, you risk illegal memory access when reading the source.
    If you strncpy from a large string into a small string and use the source size, you risk illegal memory access when writing to the destination.

    strncpy based on the source length is no different from strcpy.

    Code:
    size_t copyLen = std::min( sizeof(node->word)-1, word.size() );
    strncpy(node->word, word.c_str(), copyLen);
    node->word[copyLen] = '\0';
    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.

  14. #29
    Registered User
    Join Date
    Nov 2016
    Posts
    84
    Quote Originally Posted by Salem View Post
    > strncpy(node->word, word.c_str(), word.size()-1);
    You need to limit by the MINIMUM of
    - the size of what you're copying from
    - the size of what you're copying to

    If you strncpy from a small string into a large string and use the destination size, you risk illegal memory access when reading the source.
    If you strncpy from a large string into a small string and use the source size, you risk illegal memory access when writing to the destination.

    strncpy based on the source length is no different from strcpy.

    Code:
    size_t copyLen = std::min( sizeof(node->word)-1, word.size() );
    strncpy(node->word, word.c_str(), copyLen);
    node->word[copyLen] = '\0';
    I' ve done the changes,but output is still like this:

    /home/t540972/test ==> tnode hello c++ foo faz
    Tree:
    hell[1]
    c+[1]
    fo[1]
    fa[1]
    Alphabetical:
    c+[1]
    fa[1]
    fo[1]
    hell[1]

  15. #30
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,668
    Post your latest code for addNode
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. actions on tree with 4 nodes
    By Dave11 in forum C Programming
    Replies: 2
    Last Post: 05-09-2014, 12:07 PM
  2. Write/Read tree nodes into a binary file
    By frank1 in forum C Programming
    Replies: 2
    Last Post: 10-21-2013, 12:37 AM
  3. Issue with tree nodes
    By coffee_cups in forum C++ Programming
    Replies: 19
    Last Post: 06-14-2013, 08:16 PM
  4. total nodes in a tree
    By BEN10 in forum C Programming
    Replies: 5
    Last Post: 01-10-2010, 11:37 AM
  5. Binary Tree - sum of nodes
    By Tiffanie in forum C++ Programming
    Replies: 1
    Last Post: 09-15-2008, 08:49 AM

Tags for this Thread