Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   converting binary tree into linear hashing code (http://www.go4expert.com/forums/converting-binary-tree-linear-hashing-t10211/)

viewsonic 24Apr2008 03:10

converting binary tree into linear hashing code
 
I have to following code

Code: C++

#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: C++

#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


All times are GMT +5.5. The time now is 09:38.