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

Originally Posted by Salem

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"?

Originally Posted by Salem

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]..

Originally Posted by Salem

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..

Originally Posted by Salem

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?

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());

Originally Posted by Salem

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?

Originally Posted by Salem

> 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]