Strooustrup Exercise - doubly-linked list

[arnuld]

Problem Statement is in the comments. I am getting compile time error:



/* Stroustrup, Chapter 7, exercise 7
*
* Consider:
* struct Tnode {
* string word;
* int count;
* Tnode* left;
* Tnode* right;
* };
*
*
* (1) Write a function for entering new words into a tree of Tnodes.
* (2) Write a function to write out a tree of Tnodes.
* (3) Write a function to write out a tree of Tnodes in alphabetical order.
* (4) Modify Tnode so that it stores (only) a pointer to an arbitrary long
* word stored as an array of characters on free store using new.
* (5) Modify the functions to use the new definition of Tnode.
*
* Right now, I am at (1), will do it and only then will go on (2).
*
*
* VERSION 1.0
*
*/


#include <iostream>
#include <string>



struct Tnode
{
std::string word;
int count;
Tnode* left;
Tnode* right;
};


void add_some_words(Tnode* );

int main()
{
Tnode* my_tree;

my_tree->word = NULL;
my_tree->count = 0;
my_tree->left = NULL;
my_tree->right = NULL;

add_some_words( my_tree );



return 0;
}


void add_some_words( Tnode* add_to_tree )
{
std::cout << "Please enter some words that you want to add to the Tree\n";
/* I want to use istream_iterator but can't find a way for 3rd argument to
std::copy */
/* std::copy( std::istream_iterator<std::string>(std::cin),
std::istream_iterator<std::string(),
??????? );
*/
std::string a_word;
while( std::cin >> a_word )
{
if( NULL == add_to_tree->word )
{
add_to_tree->word = a_word;
add_to_tree->count++;
}
else if( NULL == add_to_tree->left )
{
add_to_tree = add_to_tree->left;
add_to_tree->word = a_word;
add_to_tree->count++;
add_to_tree->left = NULL;
add_to_tree->right = NULL;
}
else if( NULL == add_to_tree->right )
{
add_to_tree->word = a_word;
add_to_tree->count++;
add_to_tree->left = NULL;
add_to_tree->right = NULL;
}
}

}
======================= OUTPUT ==============================
[arnuld@dune cpp]$ g++4 -ansi -pedantic -Wall -Wextra 07_7.cpp
07_7.cpp: In function ‘int main()’:
07_7.cpp:47: error: ambiguous overload for ‘operator=’ in ‘my_tree->Tnode::word = 0’
/usr/include/c++/3.4.3/bits/basic_string.h:434: note: candidates are:
std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT,
_Traits, _Alloc>:perator=(const std::basic_string<_CharT, _Traits,
_Alloc>&) [with _CharT = char, _Traits = std::char_traits<char>, _Alloc =
std::allocator<char>]
/usr/include/c++/3.4.3/bits/basic_string.h:445: note:
std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT,
_Traits, _Alloc>:perator=(const _CharT*) [with _CharT = char, _Traits =
std::char_traits<char>, _Alloc = std::allocator<char>]
/usr/include/c++/3.4.3/bits/basic_string.h:459: note:
std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT,
_Traits, _Alloc>:perator=(_CharT) [with _CharT = char, _Traits =
std::char_traits<char>, _Alloc = std::allocator<char>] 07_7.cpp: In
function ‘void add_some_words(Tnode*)’: 07_7.cpp:72: error: no match
for ‘operator==’ in ‘0 == add_to_tree->Tnode::word’
[arnuld@dunecpp]$



Line 47: my_tree->word = NULL;


I don't see why it complains on that line. my_tree->word is a std::string
and we use operator= for std::string all the time.

 

[red floyd]

Problem Statement is in the comments. I am getting compile time error:



/* Stroustrup, Chapter 7, exercise 7
*
* Consider:
* struct Tnode {
* string word;
* int count;
* Tnode* left;
* Tnode* right;
* };
*
*
* (1) Write a function for entering new words into a tree of Tnodes.
* (2) Write a function to write out a tree of Tnodes.
* (3) Write a function to write out a tree of Tnodes in alphabetical order.
* (4) Modify Tnode so that it stores (only) a pointer to an arbitrary long
* word stored as an array of characters on free store using new.
* (5) Modify the functions to use the new definition of Tnode.
*
* Right now, I am at (1), will do it and only then will go on (2).
*
*
* VERSION 1.0
*
*/


#include <iostream>
#include <string>



struct Tnode
{
std::string word;
int count;
Tnode* left;
Tnode* right;
};


void add_some_words(Tnode* );

int main()
{
Tnode* my_tree;

my_tree->word = NULL;
my_tree->count = 0;
my_tree->left = NULL;
my_tree->right = NULL;

add_some_words( my_tree );



return 0;
}


void add_some_words( Tnode* add_to_tree )
{
std::cout << "Please enter some words that you want to add to the Tree\n";
/* I want to use istream_iterator but can't find a way for 3rd argument to
std::copy */
/* std::copy( std::istream_iterator<std::string>(std::cin),
std::istream_iterator<std::string(),
??????? );
*/
std::string a_word;
while( std::cin >> a_word )
{
if( NULL == add_to_tree->word )
{
add_to_tree->word = a_word;
add_to_tree->count++;
}
else if( NULL == add_to_tree->left )
{
add_to_tree = add_to_tree->left;
add_to_tree->word = a_word;
add_to_tree->count++;
add_to_tree->left = NULL;
add_to_tree->right = NULL;
}
else if( NULL == add_to_tree->right )
{
add_to_tree->word = a_word;
add_to_tree->count++;
add_to_tree->left = NULL;
add_to_tree->right = NULL;
}
}

}
======================= OUTPUT ==============================
[arnuld@dune cpp]$ g++4 -ansi -pedantic -Wall -Wextra 07_7.cpp
07_7.cpp: In function ‘int main()’:
07_7.cpp:47: error: ambiguous overload for ‘operator=’ in ‘my_tree->Tnode::word = 0’
/usr/include/c++/3.4.3/bits/basic_string.h:434: note: candidates are:
std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT,
_Traits, _Alloc>:perator=(const std::basic_string<_CharT, _Traits,
_Alloc>&) [with _CharT = char, _Traits = std::char_traits<char>, _Alloc =
std::allocator<char>]
/usr/include/c++/3.4.3/bits/basic_string.h:445: note:
std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT,
_Traits, _Alloc>:perator=(const _CharT*) [with _CharT = char, _Traits =
std::char_traits<char>, _Alloc = std::allocator<char>]
/usr/include/c++/3.4.3/bits/basic_string.h:459: note:
std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT,
_Traits, _Alloc>:perator=(_CharT) [with _CharT = char, _Traits =
std::char_traits<char>, _Alloc = std::allocator<char>] 07_7.cpp: In
function ‘void add_some_words(Tnode*)’: 07_7.cpp:72: error: no match
for ‘operator==’ in ‘0 == add_to_tree->Tnode::word’
[arnuld@dunecpp]$



Line 47: my_tree->word = NULL;


I don't see why it complains on that line. my_tree->word is a std::string
and we use operator= for std::string all the time.

Yeah, but NULL is an integer constant, defined as 0. There's no
assignment operator std::basic_string<>:perator=(int), hence the error.

By default a std::string is empty. Plus, in main, my_tree points at
garbage (uninitialized pointer). I'd declare it just as a TNode, rather
than TNode*, and pass its address to add_some_words()

 

[Salt_Peter]

Problem Statement is in the comments. I am getting compile time error:

/* Stroustrup, Chapter 7, exercise 7
*
* Consider:
* struct Tnode {
* string word;
* int count;
* Tnode* left;
* Tnode* right;
* };
*
*
* (1) Write a function for entering new words into a tree of Tnodes.
* (2) Write a function to write out a tree of Tnodes.
* (3) Write a function to write out a tree of Tnodes in alphabetical order.
* (4) Modify Tnode so that it stores (only) a pointer to an arbitrary long
* word stored as an array of characters on free store using new.
* (5) Modify the functions to use the new definition of Tnode.
*
* Right now, I am at (1), will do it and only then will go on (2).
*
*
* VERSION 1.0
*
*/

#include <iostream>
#include <string>

struct Tnode
{
std::string word;
int count;
Tnode* left;
Tnode* right;

};

void add_some_words(Tnode* );

int main()
{
Tnode* my_tree;

At this point you have a pointer my_tree, it *could* potentially point
to something.
In fact, it does point somewhere, some garbage/residual value.
A pointer does not invoke construction.
So far - there *is* no Tnode at that pointer.
Can you see why naming a pointer as such is helpful?

You could allocate it and later destroy the object using new / delete.
At least then you would have an object *at* that pointer to work with.

Tnode* p_node = new Tnode;
// do stuff
delete p_node;

or you might simply do it all without manual allocation / deallocation
and just pass the address of the object using the address_of operator
&.

Tnode node;
Tnode* p_node = &node;
// do stuff

my_tree->word = NULL;

member word is a std::string, not a pointer

my_tree->word = "";

my_tree->count = 0;
my_tree->left = NULL;
my_tree->right = NULL;

add_some_words( my_tree );

return 0;

}

void add_some_words( Tnode* add_to_tree )
{
std::cout << "Please enter some words that you want to add to the Tree\n";
/* I want to use istream_iterator but can't find a way for 3rd argument to
std::copy */
/* std::copy( std::istream_iterator<std::string>(std::cin),
std::istream_iterator<std::string(),
??????? );
*/
std::string a_word;
while( std::cin >> a_word )
{
if( NULL == add_to_tree->word )
{
add_to_tree->word = a_word;
add_to_tree->count++;
}
else if( NULL == add_to_tree->left )
{
add_to_tree = add_to_tree->left;
add_to_tree->word = a_word;
add_to_tree->count++;
add_to_tree->left = NULL;
add_to_tree->right = NULL;
}
else if( NULL == add_to_tree->right )
{
add_to_tree->word = a_word;
add_to_tree->count++;
add_to_tree->left = NULL;
add_to_tree->right = NULL;
}
}

}

======================= OUTPUT ==============================
[arnuld@dune cpp]$ g++4 -ansi -pedantic -Wall -Wextra 07_7.cpp
07_7.cpp: In function ‘int main()’:
07_7.cpp:47: error: ambiguous overload for ‘operator=’ in ‘my_tree->Tnode::word = 0’
/usr/include/c++/3.4.3/bits/basic_string.h:434: note: candidates are:
std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT,
_Traits, _Alloc>:perator=(const std::basic_string<_CharT, _Traits,
_Alloc>&) [with _CharT = char, _Traits = std::char_traits<char>, _Alloc =
std::allocator<char>]
/usr/include/c++/3.4.3/bits/basic_string.h:445: note:
std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT,
_Traits, _Alloc>:perator=(const _CharT*) [with _CharT = char, _Traits =
std::char_traits<char>, _Alloc = std::allocator<char>]
/usr/include/c++/3.4.3/bits/basic_string.h:459: note:
std::basic_string<_CharT, _Traits, _Alloc>& std::basic_string<_CharT,
_Traits, _Alloc>:perator=(_CharT) [with _CharT = char, _Traits =
std::char_traits<char>, _Alloc = std::allocator<char>] 07_7.cpp: In
function ‘void add_some_words(Tnode*)’: 07_7.cpp:72: error: no match
for ‘operator==’ in ‘0 == add_to_tree->Tnode::word’
[arnuld@dunecpp]$

Line 47: my_tree->word = NULL;

I don't see why it complains on that line. my_tree->word is a std::string
and we use operator= for std::string all the time.

If you read the error, its complaining that its not able to use
that operator with an rvalue that is a pointer* .

so this would do:
std::string* p_s = 0; // points to nothing yet
and this would also:
std::string s = "";

Don't get discouraged, you need to detect the crucial difference
between
an instance of a type and a pointer.
A pointer points to nothing until properly initialized.

 

[arnuld]

Yeah, but NULL is an integer constant, defined as 0. There's no
assignment operator std::basic_string<>:perator=(int), hence the error.

Oh.. I thought of std::string like a char pointer.

By default a std::string is empty. Plus, in main, my_tree points at
garbage (uninitialized pointer). I'd declare it just as a TNode, rather
than TNode*, and pass its address to add_some_words()

Whats the benefit of it over the pointer definition ?


2nd it works fine but I get Segfault because of the some wrong code in
while() loop:


/* Stroustrup, Chapter 7, exercise 7
*
* Consider:
* struct Tnode {
* string word;
* int count;
* Tnode* left;
* Tnode* right;
* };
*
*
* (1) Write a function for entering new words into a tree of Tnodes.
* (2) Write a function to write out a tree of Tnodes.
* (3) Write a function to write out a tree of Tnodes in alphabetical order.
* (4) Modify Tnode so that it stores (only) a pointer to an arbitrary long
* word stored as an array of characters on free store using new.
* (5) Modify the functions to use the new definition of Tnode.
*
* Right now, I am at (1), will do it and only then will go on (2).
*
*
* VERSION 1.1
*
*/


#include <iostream>
#include <string>



struct Tnode
{
std::string word;
int count;
Tnode* left;
Tnode* right;
};


void add_some_words(Tnode* );

int main()
{
Tnode my_tree;

my_tree.word = "";
my_tree.count = 0;
my_tree.left = NULL;
my_tree.right = NULL;

add_some_words( &my_tree );


return 0;
}


void add_some_words( Tnode* add_to_tree )
{
std::cout << "Please enter some words that you want to add to the Tree\n";
/* I want to use istream_iterator but can't find a way for 3rd argument to
std::copy */
/* std::copy( std::istream_iterator<std::string>(std::cin),
std::istream_iterator<std::string(),
??????? );
*/
std::string a_word;
while( std::cin >> a_word )
{
if( add_to_tree->word.length() == 0 )
{
add_to_tree->word = a_word;
add_to_tree->count++;
}
else if( NULL == add_to_tree->left )
{
add_to_tree = add_to_tree->left;
add_to_tree->word = a_word;
add_to_tree->count++;
add_to_tree->left = add_to_tree->right = NULL;
}
else if( NULL == add_to_tree->right )
{
add_to_tree->word = a_word;
add_to_tree->count++;
add_to_tree->left = add_to_tree->right = NULL;
}
}
}

=================== OUTPUT ====================
[arnuld@dune cpp]$ g++4 -ansi -pedantic -Wall -Wextra 07_7.cpp
[arnuld@dune cpp]$ ./a.out
Please enter some words that you want to add to the Tree
Love
Linux
Segmentation fault
[arnuld@dune cpp]$

 

[arnuld]

Um, what's wrong with 'my_tree->word.clear()'?

because I did not know this member function.

 

[arnuld]

On Thu, 06 Nov 2008 21:57:08 -0800, red floyd wrote:


STATEMENT: see the comments
PROBLEM: It's not adding words to the Tree, though it compiles fine.


/* Stroustrup, Chapter 7, exercise 7
*
* Consider:
* struct Tnode {
* string word;
* int count;
* Tnode* left;
* Tnode* right;
* };
*
*
* (1) Write a function for entering new words into a tree of Tnodes.
* (2) Write a function to write out a tree of Tnodes.
* (3) Write a function to write out a tree of Tnodes in alphabetical order.
* (4) Modify Tnode so that it stores (only) a pointer to an arbitrary long
* word stored as an array of characters on free store using new.
* (5) Modify the functions to use the new definition of Tnode.
*
* Right now, I am at (1), will do it and only then will go on (2).
*
* Problem doe snot explain why the "count" exists as a member of Tnode. I think
* the author does not want us to have duplicates getting stored in Tnode. So if
* we get a some duplicate word, then we can increase the count of that specific
* node.
*
* VERSION 1.2
*
*/


#include <iostream>
#include <string>



struct Tnode
{
std::string word;
int count;
Tnode* left;
Tnode* right;
};


void make_tree_null( Tnode* );
void add_some_words(Tnode* );
Tnode* add_single_word( Tnode*, std::string );
void print_tree( Tnode* );

int main()
{
Tnode my_tree;

make_tree_null( &my_tree );
add_some_words( &my_tree );
print_tree( &my_tree );


return 0;
}

void make_tree_null( Tnode* non_null_tree )
{
non_null_tree->word = "";
non_null_tree->count = 0;
non_null_tree->left = NULL;
non_null_tree->right = NULL;
}

void add_some_words( Tnode* a_tree )
{
std::cout << "Please enter some words that you want to add to the Tree\n";
std::string a_word;
while( std::cin >> a_word )
{
a_tree = add_single_word(a_tree, a_word);
}
/* Instead of while() loop I want to use istream_iterator but can't find a
way for 3rd argument to std::copy:
std::copy( std::istream_iterator<std::string>(std::cin),
std::istream_iterator<std::string(),
???????????????????????????????? )
*/
}


/* Uses recursion, inspired from K&R2,Self-Referential structures, section 6.5
function is printing the word and the string comparison without any trouble.

argument "ts" means "tree structure", but easy to type.
*/
Tnode* add_single_word( Tnode* ts, std::string single_word )
{
int comparison;


if( NULL == ts )
{
ts = new Tnode;
std::cout << "-------------\n";
if( ts )
{
ts->word.clear();
ts->count++;
}
else
{
std::cerr << "Can't allocate memory\n";
return ts;
}
}
else if( !(comparison = single_word.compare(ts->word)) )
{
ts->count++;
}
else if( comparison < 0 )
{
add_single_word( ts->left, single_word );
}
else if( comparison > 0 )
{
add_single_word(ts->right, single_word);
}

return ts;
}



void print_tree( Tnode* a_tree)
{
if( a_tree )
{
print_tree(a_tree->left);

std::cout << a_tree->word
<< " occured "
<< a_tree->count
<< " times"
<< std::endl;

print_tree(a_tree->right);
}
else
{
std::cout << "NULL tree" << std::endl;
}
}


==================== OUTPUT =======================
[arnuld@dune C++]$ ./a.out
Please enter some words that you want to add to the Tree
Bjarne Stroustrup and Hurb Sutter

 

[DJ Dharme]

STATEMENT:  see the comments
PROBLEM:    It's not adding words to the Tree, though it compiles fine.

/* Stroustrup, Chapter 7, exercise 7
 *
 * Consider:
 *           struct Tnode {
 *                          string word;
 *                          int count;
 *                          Tnode* left;
 *                          Tnode* right;
 *                     };
 *
 *
 *  (1) Write a function for entering new words into a tree of Tnodes..
 *  (2) Write a function to write out a tree of Tnodes.
 *  (3) Write a function to write out a tree of Tnodes in alphabetical order.
 *  (4) Modify Tnode so that it stores (only) a pointer to an arbitrary long
 *      word stored as an array of characters on free store using new.
 *  (5) Modify the functions to use the new definition of Tnode.
 *
 * Right now, I am at (1), will do it and only then will go on (2).
 *
 * Problem doe snot explain why the "count" exists as a member of Tnode.. I think
 * the author does not want us to have duplicates getting stored in Tnode. So if
 * we get a some duplicate word, then we can increase the count of that specific
 * node.
 *
 * VERSION 1.2
 *
 */

#include <iostream>
#include <string>

struct Tnode
{
  std::string word;
  int count;
  Tnode* left;
  Tnode* right;

};

void make_tree_null( Tnode* );
void add_some_words(Tnode* );
Tnode* add_single_word( Tnode*, std::string );
void print_tree( Tnode* );

int main()
{
  Tnode my_tree;

  make_tree_null( &my_tree );
  add_some_words( &my_tree );
  print_tree( &my_tree );

  return 0;

}

void make_tree_null( Tnode* non_null_tree )
{
  non_null_tree->word  = "";
  non_null_tree->count = 0;
  non_null_tree->left  = NULL;
  non_null_tree->right = NULL;

}

void add_some_words( Tnode* a_tree )
{
  std::cout << "Please enter some words that you want to add to the Tree\n";
  std::string a_word;
  while( std::cin >> a_word )
    {
      a_tree = add_single_word(a_tree, a_word);
    }
  /* Instead of while() loop I want to use istream_iterator but can't find a
     way for 3rd argument to std::copy:
     std::copy( std::istream_iterator<std::string>(std::cin),
     std::istream_iterator<std::string(),
     ???????????????????????????????? )
  */

}

/* Uses recursion, inspired from K&R2,Self-Referential structures, section 6.5
   function is printing the word and  the string comparison without any trouble.

   argument "ts" means "tree structure", but easy to type.
*/
Tnode* add_single_word( Tnode* ts, std::string single_word )
{
  int comparison;

  if( NULL == ts )
    {
      ts = new Tnode;
      std::cout << "-------------\n";
      if( ts )
        {
          ts->word.clear();
          ts->count++;
        }
      else
        {
          std::cerr << "Can't allocate memory\n";
          return ts;
        }
    }
  else if( !(comparison = single_word.compare(ts->word)) )
    {
      ts->count++;
    }
  else if( comparison < 0 )
    {
      add_single_word( ts->left, single_word );
    }
  else if( comparison > 0 )
    {    
      add_single_word(ts->right, single_word);
    }

  return ts;

}

void print_tree( Tnode* a_tree)
{
  if( a_tree )
    {
      print_tree(a_tree->left);

      std::cout << a_tree->word
                << " occured "
                << a_tree->count
                << " times"
                << std::endl;

      print_tree(a_tree->right);
    }
  else
    {
      std::cout << "NULL tree" << std::endl;
    }

}

==================== OUTPUT =======================
[arnuld@dune C++]$ ./a.out
Please enter some words that you want to add to the Tree
Bjarne Stroustrup and Hurb Sutter
-------------
-------------
-------------
-------------
-------------
NULL tree
 occured 0 times
NULL tree
[arnuld@dune C++]$

--www.lispmachine.wordpress.com
my email is @ the above blog.

Try this one out

#include <iostream>
#include <string>

struct Tnode
{
std::string word;
int count;
Tnode* left;
Tnode* right;

};

void reset_node(Tnode* pnode);
void add_some_words(Tnode* proot);
void add_to_tree(Tnode* pnode, std::string& word);
void print_tree(Tnode* proot);

int main()
{
Tnode root;

reset_node(&root);
add_some_words(&root);

std::cout << "Printing Items in the alphabetical order (Case
Sensitive)" << std::endl;

print_tree(&root);

return 0;

}

void reset_node(Tnode* pnode)
{
pnode->word = "";
pnode->count = 0;
pnode->left = NULL;
pnode->right = NULL;
}

void add_some_words(Tnode* proot)
{
std::cout << "Please enter some words that you want to add to the
Tree" << std::endl;

std::string aword;
getline(std::cin, aword);

while(aword != "")
{
add_to_tree(proot, aword);
getline(std::cin, aword);
}
}

void add_to_tree(Tnode* pnode, std::string& word)
{
if(pnode->count == 0)
{
pnode->word = word;
}
else
{
if(word.compare(pnode->word) < 0)
{
if(pnode->left == NULL)
{
pnode->left = new Tnode;
reset_node(pnode->left);
}

add_to_tree(pnode->left, word);
}
else
{
if(pnode->right == NULL)
{
pnode->right = new Tnode;
reset_node(pnode->right);
}

add_to_tree(pnode->right, word);
}
}

++(pnode->count);
}

void print_tree(Tnode* pnode)
{
if(pnode->left)
{
print_tree(pnode->left);
}
std::cout << pnode->word << std::endl;

if(pnode->right)
{
print_tree(pnode->right);
}
}

 

[Default User]

Oh.. I thought of std::string like a char pointer.

I'd strongly recommend that you read the Stroustrup sections on
std::string before you try to use it any further.




Brian