converting binary tree into linear hashing code

Discussion in 'C' started by viewsonic, Apr 23, 2008.

  1. viewsonic

    viewsonic New Member

    Joined:
    Apr 23, 2008
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    I have to following code

    Code:
    #ifndef CONTAINERIMPL_H
    #define CONTAINERIMPL_H
    
    #include <iostream>
    #include "Container.h"
    
    class ContainerImpl : public Container {
    
      class Node {
      public:
        Key key;
        Node * left;
        Node * right;
        Node( const Key& key, Node * left = 0, Node * right = 0 ) : key( key ), left( left ), right( right ) {}
      };
    
      Node * root;
    
      void add_( Node*& node, const Key& key );
      bool isMember_( Node* node, const Key& key ) const;
      std::ostream& put_( Node* node, std::ostream& o ) const;
    
      virtual std::ostream& put( std::ostream& o ) const { return put_( root, o ); }
    
    public:
      ContainerImpl() : root( 0 ) { }
      virtual ~ContainerImpl( ) { }   // not implemented
    
      using Container::add;
      virtual void add( const Key keys[], size_t size );
    
      using Container::remove;
      virtual void remove( const Key keys[], size_t size ) { }  // not implemented
    
      virtual bool isMember( const Key& key ) const  { return isMember_( root, key ); }
      virtual size_t size( ) const { return 0; }  // not implemented
      virtual bool isEmpty( ) const { return false; }  // not implemented
    
      virtual void foreach( const Functor& f, Order order = dontcare ) const { } // not implemented
    
      virtual Key minKey( ) const { return Key(); } // not implemented
      virtual Key maxKey( ) const { return Key(); } // not implemented
    
      virtual int teamNr( ) const { return 0; }
      virtual int themeNr( ) const { return 0; }
    };
    
    #endif //CONTAINERIMPL_H
    with

    Code:
    #include <iostream>
    #include "ContainerImpl.h"
    
    void ContainerImpl::add_( Node*& node, const Key& key ) {
      if (!node) {
        node = new Node( key );
      } else {
        if (node->key > key) {
          add_( node->left, key );
        } else if (key > node->key) {
          add_( node->right, key );
        }
      }
    }
    
    void ContainerImpl::add( const Key keys[], size_t size ) {
      for (size_t i = 0; i < size; ++i) {
        add_( root, keys[i] );
      }
    }
    
    bool ContainerImpl::isMember_( Node* node, const Key& key ) const {
      if (!node) {
        return false;
      } else if (key == node->key) {
        return true;
      } else if (node->key > key) {
        return isMember_( node->left, key );
      } else {
        return isMember_( node->right, key );
      }
    }
    
    std::ostream& ContainerImpl::put_( Node* node, std::ostream &o ) const {
      if (node) {
        o << " (";
        o << node->key;
        put_( node->left, o );
        put_( node->right, o );
        o << ')';
      } else {
        o << " .";
      }
      return o;
    }
    

    convert into linear hashing with insert and search function.


    Also, I have to use

    Code:
        *      Defaultkonstruktor ContainerImpl() 
        *      void add( const Key[], size_t ) 
        *      void add( const Key& ) 
        *      bool isMember( const Key& ) const 
        *      int teamNr( ) const 
        *      int themeNr( ) const 
    Cause, I'm not a programmer and I need to do that in a few days, I hope also someone can help me with it? Thanks in Advance
     
    Last edited by a moderator: Jun 16, 2009

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice