You are here:

C++/data structures

Advertisement


Question
QUESTION:  Hi,

How are you? Thank you very much for taking questions.
I am experimenting with linked lists and trees in C++. I think I know how to declare nodes for trees and also how to connect them with pointers. However, I only know how to do it one node at a time. My program needs to automatically make unknown number new nodes during runtime. How do you make automatic nodes without having to give each node an individual name. Is an array of nodes the way to go? Or is there another automatic naming pattern that Iím unaware of.

 Below is my code:

class MyTree
{
   int *id, *count;
   MyTree *left, *right;

 public:   
     
    MyTree(int a, int b)
      {
      id = new int; count = new int;   *id = a; *count = b;
      left = NULL;
      right = NULL;
      }
      
   ~MyTree(){delete id; delete count;}
   };

int main()
{

MyTree first_node(1,1);
MyTree second_node(2,1);
.
.
MyTree onehundredth_node(100,1);
}


How could I create code that doesnít need to know the names and numbers of the nodes beforehand.

My second question concerns FP-trees. Do you know of any implementation tutorials for FP-trees?

Sincerely,
         Andres


ANSWER: if we need a variable number of objects that can only be determined during run-time, we have to create these objects with a dynamic storage duration by using the keyword new. And once we are done with them, we can get rid of them by using delete.
see: http://www.cplusplus.com/doc/tutorial/dynamic/

And here is an example of using new to create objects:

#include <iostream>

struct tree
{
  int value ;

  tree* left ;
  tree* right ;

  tree( int v ) { value = v ; left = 0 ; right = 0 ; }
};

void add_item( tree* t, int val )
{
 if( t == 0 ) return ; // no tree, nothing to be done


 if( val < t->value ) // smaller value, add to left sub-tree
 {
   if( t->left == 0 ) t->left = new tree(val) ;
   else add_item( t->left, val ) ;
 }
 else // add to right sub-tree
 {
   if( t->right == 0 ) t->right = new tree(val) ;
   else add_item( t->right, val ) ;
 }
}

void print( const tree* t )
{
 if( t == 0 ) return ;
 print( t->left ) ;
 std::cout << t->value << '\n' ;
 print( t->right ) ;
}

int main()
{
  tree* t = new tree(60) ;

  int val ;
  while( std::cout << "value? " && std::cin >> val )
  {
    if( val == -1 ) break ;
    add_item( t, val ) ;
  }

  print(t) ;
}

Re: FP-Trees, here is a link: http://books.google.co.in/books?id=AfL0t-YzOrEC&pg=PA244#PPA244,M1



---------- FOLLOW-UP ----------

QUESTION: Thank you so much for your help.
You gave me a code that first declares an array of objects and then initalizes the objects during runtime. I have this question: Do you always need to have this "array backbone" for objects when you want to create them during runtime. Is there a way to do it without an array, using only pointers (somehow). I ask this because I may not know the max number of objects before the program executes. What's the best way around it? Thanks so much.
Andres.

Answer
You could use a linked list instead of an array (as in your earlier code).

If the only issue is that "I may not know the max number of objects before the program executes", the simplest (and also the best) way is to use a dynamically resizeable array. Such an implementation is already available as part of the standard C++ library - use a std::vector<> in place of a c-style array.

see: http://www.cprogramming.com/tutorial/stl/vector.html

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


vijayan

Expertise

my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.

Experience

about 15 years or so

Education/Credentials
post graduate engineer

©2016 About.com. All rights reserved.