C++ Problem Klassen

[Tijay]

Hi Ihr

Ich habe ein Problem.

Und zwar muss ich ein Hash Verfahren realisieren mit verketteten Listen.

Es Soll Quasi ein Array aus verketteten Listen sein.

und zwar rechne ich den Platz volgendermaßen aus:

x(einzugebende Zahl) mod m = Platz in der Tabelle.

wenn der Platz belegt ist, dann soll er an der Position in der verketten Liste eine Position weiter gehen und da sehen, ob er das abspeichern kan.

Beispiel:

1 mod 100 = Platz 1

Platz frei -> ja -> dann speichern (in erstem element verkettete Liste)

nächste eingabe

101 mod 100 = platz 1

platz frei -> nein -> verkettete Liste next -> Platz frei -> ja -> dann speichern

class LinkedListSortedSet: public LinkedListUnsortedSet, SortedSet{
private:
	ListElementSortedSet* anker;
public:
	LinkedListSortedSet();
	void insert(int);
	void del(int);
	void ausgabe()const;
	~LinkedListSortedSet();
};

LinkedListSortedSet::LinkedListSortedSet(){
	anker = NULL;}

void LinkedListSortedSet::insert(int z){
	ListElementSortedSet* neu = new ListElementSortedSet(z);
	if (anker == NULL)
	{	anker = neu;
		return;}
	if ( anker->zahl > z)
	{	neu->next = anker;
		anker = neu;}
	else
	{	ListElementSortedSet* lfd = anker;
	while(lfd->next != NULL && lfd->next->zahl < z)
		lfd = lfd->next;
	neu->next = lfd->next;
	lfd->next = neu;
	}
}
void LinkedListSortedSet::del(int z)
{
	if (anker == NULL){ 
		return;
	}
	if (anker->getzahl() == z){ 
		ListElementSortedSet* hilf = anker;
		anker = anker->getnext();
		delete hilf;
	}
	else { ListElementSortedSet* lfd = anker;
		   bool found = false;
		   while (lfd->getnext() != NULL && ! found){
			   if (lfd->getnext()->getzahl() == z)
				   found = true;
			   else
				   lfd = lfd->getnext();
		   }
		   if (found){ // Löschen
			   ListElementSortedSet* hilf = lfd->getnext();
			   lfd->setnext(lfd->getnext()->getnext());
			   delete hilf;
		   }
	}
}

void LinkedListSortedSet::ausgabe() const
{
	ListElementSortedSet *lfd = anker;
	while(lfd != NULL){
		lfd->ausgabe();
		lfd = lfd->next;
	}
}

LinkedListSortedSet::~LinkedListSortedSet()
{	ListElementSortedSet* hilf;
	while(anker != NULL){
		hilf = anker;
		anker = anker->next;
		delete hilf;
	}
}

class HashUnsorted: public UnsortedSet{
public:

private:
};

class SepVerkettungHash: public HashUnsorted, LinkedListUnsortedSet{
public:
	SepVerkettungHash();
	~SepVerkettungHash();
	void insert(int in);
    int search(int in);
	bool del(int in);
	void schreib() const;
	LinkedListUnsortedSet& operator[](int index) const;
private:
	LinkedListUnsortedSet *HashTab;
	int m;
};

SepVerkettungHash::SepVerkettungHash()
{
HashTab = NULL;
m = 10007;

}

SepVerkettungHash::~SepVerkettungHash()
{
delete[] HashTab;
}

LinkedListUnsortedSet& SepVerkettungHash::oerator[]
{
return HashTab[index];
}

 

[badday]

Und was genau ist dein Problem, also was macht er nicht, welcher Fehler tritt auf etc.?

Gruß,

badday

 

[Tijay]

ich komme irgendwie nicht weiter, wie ich ein array aus verkettenlisten mache.

siehe beispiel

die verketteten listen funktionieren.

nur wie nutze ich die Klasse dann in SepVerkettungHash?

 

[Limit]

Wo ist denn das Problem? Das sieht ja soweit ganz brauchbar aus. Du musst nur noch das Array initialisieren und benutzen?!?!

Für die search Fkt würde es die ganze viel schöner machen, wenn schon die verkettete Liste eine solche Fkt für sich bieten würden. Außerdem solltest du die Hash-Fkt separat definieren.
Die Fkt für die SepVerkettungHash Klasse könnte dann z.B. so ähnlich aussehen:

int insert(int in) {
	if (this.HashTab == NULL)
		this.HashTab = new LinkedListUnSortedSet[10007]; // falls die Hash-Fkt einfach x mod 10007 ist
	this.HashTab[hash_fct(in)].insert(in);	
        return 1;
}

int search(int in) {
	if (this.HashTab == NULL)
		return -1;
	else
		return HashTab[hash_fct(in)].search(in);
}

int del(int in) {
	if (this.HashTab == NULL)
		return false;
	else {
		HashTab[hash_fct(in)].del(in);
		return true;
        }
}