verkettete liste

[MisterNO]

hi,

ich wäre sehr dankbar wenn mir zu folgendem problem helfen würde:
ich habe eine klasse mit der eine verkettete liste mit zahlen in aufsteigender reihenfolge erstelt wird.
diese verkettete liste soll in einer abgeleiteten klasse mit hilfe eines kopierkonstruktors in eine perfekte (balancierte) skipliste transformiert werden.
jeder vorschlag würde mir helfen.
bin leider c++anfänger und tüftle an der aufgabe seit sechs wochen.

[finix]

MisterNO schrieb:

bin leider c++anfänger und tüftle an der aufgabe seit sechs wochen.

Wie sieht denn deine bisherige Lösung aus und wo hapert's noch?

[fehlersucher]

Was meinst du mit dieser Liste? Also wie soll sie aussehen?
Zum umsortieren von Elementen ist die verkettete Liste schonmal gut geeignet.
Wenn du zwei Elemente vertauschen willst, musst du nur die prev und next-Zeiger der beiden jeweils tauschen.

Post doch mal ein Codebeispiel

[MisterNO]

hi,

hier ist was ich bis jetzt gemacht habe.

Die klassen von der verketteten liste sehen so aus:

#include<iostream>
using namespace std;

class ListEl
{
private:
// ListEl *next;
// int atom;
public:
ListEl *next;
int atom;
ListEl();
ListEl(int a);
~ListEl();

ListEl* getNext();

};

#include "ListEl.h"

ListEl::ListEl()
{}

ListEl::ListEl(int a)
{
atom = a;
}

ListEl::~ListEl()
{}
ListEl* ListEl::getNext(){ return next; }

#include "ListEl.h"
using namespace std;

class SortList
{
private:
ListEl *first;
int anz;
public:
SortList();
~SortList();

ListEl* getFirst();
void Insert(int e);
int Search(int i);
void display();

};

#include "SortList.h"

SortList::SortList(){ first = 0; }

SortList::~SortList(){}

void SortList::Insert(int e)
{
ListEl *newPtr = new ListEl(e);
if(first == 0 || e < first->atom)
{
newPtr->next = first; // Am Anfang einfügen
first = newPtr;
}
else
{
ListEl *elPtr = first;

for( ; elPtr->next != 0; elPtr = elPtr->next)
if( e < elPtr->next->atom)
break;

newPtr->next = elPtr->next; // nach *elPtr einfügen
elPtr->next = newPtr;
}

}
void SortList::display()
{
//Ausgabe der Liste
ListEl *elPtr = first;
while(elPtr != 0)
{
cout << elPtr->atom << "\t";
elPtr = elPtr->next;
}
}
int SortList::Search(int i)
{
int ii = i;
ListEl *elPtr = first;

while(elPtr != 0)
{
if(elPtr->atom == ii)
{
cout << "Der gesuchte Wert (Schluessel): " << elPtr->atom <<"\n";
break;
}
elPtr = elPtr->next;
}
if(elPtr == 0)
cout << "Der gesuchte Wert befindet sich nicht in der sortierten verketteten Liste.\n";
return -1; // -1, falls nicht gefunden
}

Hier ist die SkipList-klasse in der die verkettete liste in eine perfekte skipliste transformiert werden soll (in einem kopierkonstruktor):

class SkipList:public SkipListEl
{
private:

public:
SkipList(const SkipList& src);
~SkipList();

ListEl* Search();
void setPtr();
ListEl* getPtr();

};

Die Zahlen für die verkettete liste werden in der main()-funktion mit der srand() funktion erzeugt. Die insert()-methode in der SortList-klasse sortiert die zahlen in aufseigender reihenfolge.
Mein problem:
Wie kann man in der SkipList-klasse die verkettete liste aus SortList in eine skipliste umwandeln?

vg

[MisterNO]

ii