Projekt Double Hashing
-
Hi Leute!
Hab den Auftrag ein Programm zu schreiben, dass eine Tabelle erstellt und mittls DOubleHashing 200000 Werte einfügt.
Mein Aufratgeber hat mir einen Container vorgegeben von dem mein Header erbt.
#ifndef DOUBLEHASHING_H #define DOUBLEHASHING_H #include <iostream> #include "Container.h" enum Status { empty, filled, emptyagain }; class Ex;//Klasse für nichtimplementierte Methoden template <typename E> class DoubleHashing : public Container<E> { size_t n; size_t nmax; size_t pos; E* values; Status* status; void sort ( ) const; public: DoubleHashing(size_t laenge=30); virtual ~DoubleHashing( ); using Container<E>::add; virtual void add( const E e[], size_t len ); using Container<E>::remove; virtual void remove( const E [], size_t ) { throw Ex(); } virtual bool member( const E& e ) const; virtual size_t size( ) const { throw Ex(); } virtual size_t apply ( const Functor<E>&,Order= dontcare) const { throw Ex(); } virtual E min() const { throw Ex(); } virtual E max() const { throw Ex(); } virtual std::ostream& print( std::ostream& o ) const; }; class DHEmptyException : public ContainerException { public: virtual const char * what() const throw() { return "empty"; } }; class Ex : public ContainerException { public: virtual const char * what() const throw() { return "not implemented"; } }; template <typename E> DoubleHashing<E>::DoubleHashing ( size_t laenge) : n(0), nmax (laenge) { values = new E[nmax]; status = new Status[nmax]; for (size_t i = 0; i < nmax; ++i) status [i] = empty; } template <typename E> DoubleHashing<E>::~DoubleHashing ( ) { delete[] values; delete[] status; } template <typename E> void DoubleHashing<E>::add ( const E e[], size_t len ) { if ((n+len) >(nmax*0.7)) { size_t newnmax=nmax; while ((n + len) > newnmax) { newnmax = ( newnmax * 1.2 ) + 2; } E* newvalues = new E[newnmax]; Status * newstatus = new Status[newnmax]; for (size_t i = 0; i < newnmax; ++i) newstatus [i] = empty; //NEu Hashen for (size_t i = 0; i < nmax; ++i) { if(status[i] == filled) { size_t key; key = hashValue<E>(values[i]); pos = key % newnmax; //erste Hashfunktion if ( newstatus[pos] != filled ) { newvalues[pos] =values[i]; newstatus[pos] =filled; } else { //zweite Hashfunktion size_t seckey; size_t newpos; seckey = 2*(hashValue<E>(e[i]) % 10)+1; newpos = (pos + seckey) % newnmax; for (; newstatus[newpos] == filled;) { if (newpos != pos) newpos = (newpos + seckey) % newnmax; } newvalues[newpos] = values[i]; newstatus[newpos] = filled; } } delete[] values; delete[] status; values=newvalues; status=newstatus; nmax=newnmax; } } size_t pos; size_t key; for (size_t i = 0; i < len; ++i) { if (!member(e[i])) { key = hashValue<E>(e[i]); pos = key % nmax; //erste Hashfunktion if ( status[pos] != filled ) { values[pos] = e[i]; status[pos] = filled; n++; } else { //zweite Hashfunktion size_t seckey; size_t newpos; seckey = 2*(hashValue<E>(e[i]) % 10)+1; newpos = (pos + seckey) % nmax; for (; status[newpos] == filled;) { if (newpos != pos) newpos = (newpos + seckey) % nmax; } values[newpos] = e[i]; status[newpos] = filled; n++; } } } } template <typename E> bool DoubleHashing<E>::member ( const E& e ) const { size_t key; size_t pos; key = hashValue<E>(e); pos = key % nmax; if(status[pos] == filled) { if (values[pos] == e) return true; else { return false; } } else { size_t seckey; size_t newpos; seckey = 2*((hashValue<E>(e))%10)+1; newpos = (pos + seckey) % nmax; while (newpos != pos) { if (status[newpos] == empty) return false; else { if(status[newpos] == filled) { if (values[newpos] == e) return true; } else newpos = (newpos + seckey) % nmax; } } return false; } } template <typename E> std::ostream& DoubleHashing<E>::print( std::ostream& o ) const { o << "HashTable[ n=" << n << " nmax=" << nmax << " values="; for (size_t i = 0; i < nmax; ++i) { if (status[i] == filled ) o << ' ' << values[i] << ' ' << status[i] << ", "; } o << " ]"; return o; } #endifDas wäre mein Programm und ich bin echt am verzweifeln da ich den Fehler nicht finde
Vielleicht könnt ihr mir da weiter helfen!
Lg
-
pepschi schrieb:
von dem mein Header erbt.
Aha.
viel unlesbarer Code
Tag-ig.
size_t
Nanu, wo kommt der denn her?
virtual std::ostream& print( std::ostream& o ) const;
Süß.
values = new E[nmax];
status = new Status[nmax];Ojeh.
for (size_t i = 0; i < nmax; ++i) status [i] = empty;
Naja.
template <typename E>
DoubleHashing<E>::~DoubleHashing ( )Irgendwie habe ich das Bedürfnis, noch andere Funktionen zu schreiben.
E* newvalues = new E[newnmax];
Status * newstatus = new Status[newnmax];Eieiei.
size_t key;
key = hashValue<E>(values[i]);Niedlich.
pos = key % newnmax; //erste Hashfunktion
Kreativ.
{
key = hashValue<E>(e[i]);pos = key % nmax; //erste Hashfunktion
if ( status[pos] != filled )
{values[pos] = e[i];
status[pos] = filled;
n++;
}Abstrakt.
den Fehler
Soso, ein Fehler.
Vielleicht könnt ihr mir da weiter helfen!
Mein Aufratgeber
Du verdienst Geld damit?
-
nein bekomme kein geld muss das auf der uni machen
und bin echt ein anfänger!
-
pepschi schrieb:
und bin echt ein anfänger!
Darauf zielen meine Kommentare ab.
Wie wäre es, wenn du die Sprache lernst, bevor du solch ein (nicht so ganz einfaches) Projekt beginnst?
Grundlegende Stilregeln, die wichtigsten Mittel der Standardbibliothek, die einfachsten "best practices", Übung in grundlegender Abstraktion und die wichtigsten Grunddesigns. Das alles fehlt dir. Irgendwie ein bisschen überraschend, da du anscheinend ein paar schwierigere Syntaxfallstricke und ein paar fortgeschrittenere Techniken doch ganz gut beherrscht. Zusammenkopiert? "Gruppen"arbeit? Einseitige Ausbildung?
Übrigens hast du immer noch keine Frage gestellt. Wir sehen nur einen Haufen unformatierten Code*. Da soll also ein Fehler drin sein. Soso. Lies dir mal den ersten Link in meiner Signatur durch.
*: Guck mal im Editorfenster links unter den Smileys
