[es] - Linear Hashing sa Merge sort implementirati insert, search, delete i sortiranje

SuperC

Član broj: 120719
Poruke: 124
*.9.14.vie.surfer.at.

Profil

Linear Hashing sa Merge sort implementirati insert, search, delete i sortiranje

^{31.03.2008. u 18:06 - pre 195 meseci}

Radim jedan projekat u C++. Moja tema je Linearni Hashing sa Mergesort.

Znaci Hashing sa Mergesortom trebam implementirati unutar koda (vidi ispod), i to tako da da imam bazu u koju cu implementirati insert i search i onda da dodam i delete i sortiranje

Code:
#ifndef CONTAINER_H
#define CONTAINER_H

#include <iostream>
#include <string>

class Streamable {
    virtual std::ostream& put( std::ostream& o ) const = 0;
    friend std::ostream& operator<<( std::ostream& o, const Streamable& s );
public:
    virtual ~Streamable( ) {};
};

inline std::ostream& operator<<( std::ostream& o, const Streamable& s ) { return s.put( o ); }

typedef unsigned long int ValueType;

class Key {
    ValueType value;
    Key( ValueType v ) : value( v ) {}
public:
    Key() {}
    ~Key( ) {}
    std::ostream& put( std::ostream& o ) const { return o << value; }
    std::istream& get( std::istream& i ) { return i >> value; }
    bool operator==( const Key& k ) const { return value == k.value; }
    bool operator>( const Key& k ) const { return value > k.value; }
    unsigned long ulongValue() const { return (unsigned long) value; }
    unsigned long hashValue() const { return (unsigned long) value; }

    friend class KeyFactory;
};

inline std::ostream& operator<<( std::ostream& o, const Key& s ) { return s.put( o ); }
inline std::istream& operator>>( std::istream& i, Key& s ) { return s.get( i ); }

class KeyFactory {
public:
    static Key newKey( unsigned long v ) { return Key( v ); }
    static Key newKey( ) { return Key( std::rand( ) ); }
    static void srand( int i ) { std::srand( i ); }
};

class Container : public Streamable {
protected:
    Container( ) { }
public:
    enum Order { dontcare, ascending, descending };
    class Functor;
    class Exception;

    virtual ~Container( ) { }

    virtual void add( const Key& key ) { add( &key, 1 ); }
    virtual void add( const Key keys[], size_t size ) = 0;

    virtual void remove( const Key& key ) { remove( &key, 1 ); }
    virtual void remove( const Key keys[], size_t size ) = 0;

    virtual bool isMember( const Key& key ) const = 0;
    virtual size_t size( ) const = 0;
    virtual bool isEmpty( ) const { return size( ) == 0; }

    virtual void foreach( const Functor& f, Order order = dontcare ) const = 0;

    virtual Key minKey( ) const = 0;
    virtual Key maxKey( ) const = 0;

    virtual int teamNr( ) const = 0;
    virtual int themeNr( ) const = 0;
};

class Container::Exception : public Streamable {
    std::string msg;
    virtual std::ostream& put( std::ostream& o ) const { return o << "Container::Exception (" << msg << ")"; }
public:
    Exception( const std::string& msg ) : msg( msg ) {}
    const std::string& getMsg() const { return msg; }
    virtual ~Exception( ) {}
};

class Container::Functor {
public:
    virtual bool operator( )( const Key& key ) const = 0;
    virtual ~Functor( ) {}
};

#endif //CONTAINER_H

Odgovor na temu

kiklop74
Darko Miletić
Buenos Aires

Član broj: 78422
Poruke: 569
*.fibertel.com.ar.

Sajt: ar.linkedin.com/pub/darko..

+13 Profil

Re: Linear Hashing sa Merge sort implementirati insert, search, delete i sortiranje

^{01.04.2008. u 01:02 - pre 195 meseci}

A tvoje pitanje je?

Tko leti vrijedi

Odgovor na temu

SuperC

Član broj: 120719
Poruke: 124
*.9.14.vie.surfer.at.

Profil

Re: Linear Hashing sa Merge sort implementirati insert, search, delete i sortiranje

^{02.04.2008. u 18:50 - pre 195 meseci}

Druga recenica je pitanje, tj kako da to izvedem?

Odgovor na temu

SuperC

Član broj: 120719
Poruke: 124
*.9.14.vie.surfer.at.

Profil

Re: Linear Hashing sa Merge sort implementirati insert, search, delete i sortiranje

^{14.04.2008. u 20:33 - pre 195 meseci}

Svi navodni eksperti, odlicni programeri, i oni kojima je C++ u krvi mogu se naravno slobodno ponuditi da mi pomognu u rjesavanju ovog zadatka/projekta.. Ne morate se stidjeti.

Odgovor na temu

itf
Zagreb

Član broj: 59794
Poruke: 993
161.53.237.*

+9 Profil

Re: Linear Hashing sa Merge sort implementirati insert, search, delete i sortiranje

^{15.04.2008. u 10:53 - pre 195 meseci}

Citat:

SuperC: Svi navodni eksperti, odlicni programeri, i oni kojima je C++ u krvi mogu se naravno slobodno ponuditi da mi pomognu u rjesavanju ovog zadatka/projekta.. Ne morate se stidjeti.

Cinizam i arogancija te neće daleko dovesti. Nitko nije dužan ovdje tebi nešto dokazivati, a pogotovo svoje znanje, bio on "navodni" ekspert, odličan programer itd..

A za početak pomogni samom sebi. Prvo, pogledaj malo općenito o hashingu tj. što je to hashing table i kad shvatiš povezanost između ključa i vrijednosti stvar implementacije je najmanji problem. Merge sort je dobro rješenje jer radi na vrlo jednostavan način (podijeli pa vladaj) tj. raspodjelom strukutura na dijelove, te kroz dinamičko alociranje rezultata na kraju spaja sve u sortirani niz. Zbog samog principa rada to se može iskoristiti za hashing i rad s ključevima.

Odgovor na temu

SuperC

Član broj: 120719
Poruke: 124
*.pns.univie.ac.at.

Profil

Re: Linear Hashing sa Merge sort implementirati insert, search, delete i sortiranje

^{15.04.2008. u 13:43 - pre 195 meseci}

itf, hvala puno na odgovoru.

Naravno, neki znaju da programiraju neki nesto drugo. Procitah puno i zato pitah, da mi je jasno sta uraditi trebam ne bih pitao. Hvala jos jednom

Odgovor na temu

SuperC

Član broj: 120719
Poruke: 124
*.9.14.vie.surfer.at.

Profil

Re: Linear Hashing sa Merge sort implementirati insert, search, delete i sortiranje

^{18.04.2008. u 22:27 - pre 195 meseci}

dat je primjer binarnog stabla, rijesen, odnosno trazi se da

Code:

    *
      Defaultkonstruktor ContainerImpl()
    *
      void add( const Key[], size_t )
    *
      void add( const Key& )
    *
      bool isMember( const Key& ) const
    *
      int teamNr( ) const
    *
      int themeNr( ) const

moraju funkcionirati.
------------------------------------

Evo rijesenog primjera binarnog stabla:

ContainerImpl.h

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

ContainerImpl.C

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;
}

da bi se olaksalo testiranje, preporucena je i metoda:

Code:
std::ostream& put( std::ostream& ) const

Odgovor na temu

SuperC

Član broj: 120719
Poruke: 124
*.9.14.vie.surfer.at.

Profil

Re: Linear Hashing sa Merge sort implementirati insert, search, delete i sortiranje

^{20.04.2008. u 11:04 - pre 195 meseci}

Pojednostavljeno treba implementirati jednu strukturu podataka odnosno implementirati insert i search u istu. Koristeci dati kod naravno potrebno je to uraditi uz pomoc linear hashing.

Ako sam dobro iscitao u prvom dijelu se koristi linear hashing, tek poslije (drugi dio) je potrebno, uz pomoc mergesort uraditi i delete i sort.

Da li je neko nesto slicno vec radio? Kod bi naravno dobrodosao, obzirom da nisam u struci. :)

Odgovor na temu