Indizierung via Index-Listen

hallo leute,
ich hoffe ich hab mich nicht zu blöd angestellt bei der suche ob dieses thema hier schonmal besprochen wurde.

ich hab folgende aufgabe und bräuchte hilfe oder anregungen wie ich das realisieren könnte:

Werden Daten mittels einer einfach verketteten Liste verwaltet, so sind Sortiervorgänge in der Regel nur mit großem Zeitaufwand zu realisieren. Sollen die Listenelemente nach unterschiedlichen Kriterien sortiert werden, so ist dies nur durch Vervielfachung der Daten selbst möglich. Ein Ausweg bietet das Anlegen von Indexlisten. Hierbei werden nur Verweise auf die Datensätze in der geforderten Reihenfolge angelegt. Die Indexlisten sind in der Regel Felder mit einer Anzahl an Elementen, die der Anzahl der Datenelemente entsprechen. Der Inhalt dieser Feldelemente sind die Verweise auf die Daten selbst. Jedes Datum besitzt jedoch die Eigenschaft, dass ein Vergleich auf größer, kleiner und gleich auf dieses Datum ausgeführt werden kann.
Es ist eine Verwaltungsstruktur in Form einer Basisklasse zu entwickeln, die einerseits die Daten in Form einer verketteten Liste aufnehmen kann und andererseits bis zu drei Indexlisten zur Festlegung der Reihenfolge entsprechend einer Sortierregel beinhaltet. Die Basisklasse soll folgende Funktionen unterstützen:
− Verwaltung der verketteten Liste
− Einfügen eines Elementes an die Liste
− Löschen eines Elementes aus der Liste
− Indizierung aufsteigend
− Indizierung absteigend
− Zugriff auf die Daten über Indexliste

Hinweise zur Modellierung und Umsetzung
Für den Nachweis der Funktionalität soll eine Listenklasse abgeleitet werden, die als Daten Texte enthält. Über ein Textobjekt soll die Liste mit mindestens 10 Werten gefüllt werden. Die Indizierung nach größten und kleinsten Wert ist durchzuführen. Der Listeninhalt ist über den Indexzugriff auszugeben. Der Zugriff auf die Daten über die Indexlisten könnte in folgender Form möglich sein: z.B. Datum = MyList.Index. Aufsteigend(5); MyList ist hier ein Objektname. Andere Formen sind ebenfalls denkbar.

ich würde mich sehr über ideen oder gar lösungsansätze freuen.
danke schonmal im voraus

tom

SeppJ

Nun, dann fang doch einfach mal an. Es ist doch sehr viel vorgegeben, wo du schon einmal das Grundgerüst hinschreiben kannst, ohne die Methoden konkret auszufüllen: Du brauchst eine verkettete Listenklasse (habt ihr vermutlich schon gemacht?), dann eine Indexlistenklasse und eine Klasse die alles zusammen fasst. Für die zusammenfassende Klasse ist schon vorgegeben, was sie können muss, dadurch wird auch vieles impliziert, was die anderen Klassen können müssen. Wenn die zusammenfassende Klasse zum Beispiel Listenelemente einfügen können muss, dann sollte deine Listenklasse dies besser unterstützen (wenn das nicht offensichtlich sein sollte, dass eine Liste dies können sollte).
Wenn man solche Grundgerüste schreibt, dann kommen einem meistens auch schon Ideen, wie man das umsetzen könnte. Wichtig ist, sich nicht von der komplexen Aufgabenstellung abschrecken zu lassen. Das lässt sich wunderbar in kleine Probleme zerlegen. Die Listenklasse muss nichts über die Indexliste oder die zusammenfassende Klasse wissen. Das Einfügen in eine Liste muss nichts über das löschen wissen, usw.
Wenn du dann konkrete Fragen hast, komm noch einmal her.

ok ich habs mit viel mühe jetzt hinbekommen mir eine funktionierende einfach verkettete liste zu programmieren. jetzt weiß ich allerding nich richtig wie ich weitermachen kann. Irgendwie brauch ich jetzt noch die Basisklasse und die indexliste. hat jemand vorschläge wie ich weitermachen könnte? vielen dank schonmal im voraus.

class Liste
{
	private:
		ListElement* first;

	public:
		//Konstruktor
		Liste()
		{
			first = NULL;
		}

		//Destruktor
		virtual ~Liste()
		{
			delete first;
		}

		// fügt einen neuen Wert am Ende ein:
		void add( string sTempData )
		{
			// Wenn die Liste noch leer ist, dann einfach ein
			// Element an den Anfang setzen:
			if( first == NULL )
			{
				first = new ListElement( sTempData );
			}
			else
			{
				// Suche nach dem letzten Element:
				ListElement* last = first;
				while( last -> getNext() != NULL )
				{
					last = last -> getNext();
				}
				// letztes hat jetzt keinen Nachfolger mehr.
				// Das wird geändert:
				last -> add( sTempData );
			}
		}

		// sucht nach einem Wert, und liefert true, wenn der gesuchte Wert
		// enthalten ist:
		bool searchforValue( string sTempData )
		{
			// Leere Liste?
			if( first == NULL )
			{
				return false;
			}
			else
			{
				return first -> searchforValue( sTempData ) != NULL;
			}

		}	

};// class Liste

class ListElement
{
	private: 
	string sData;
	ListElement* next;

	public:
	//Konstruktor
	ListElement( string sTempData )
	{
		sData = sTempData;
		next = NULL;
	}

	//Destruktor
	virtual ~ListElement()
	{
		delete next;
	}

	//Anfügen eines neuen Elements
	void add( string sTempData )
	{
		next = new ListElement(sTempData);

		next -> next = NULL;
	}

	//Einlesen des Textes
	string getData()
	{
	  return sData;
	}

	void setNext( ListElement *next_neu )
	{
	  next = next_neu;
	}

	ListElement* getNext()
	{
	  return next;
	}

	// sucht nach einem Wert, und liefert das ListenElement
	// (falls gefunden), oder NULL.
	ListElement* searchforValue( string sTempData )
	{
		// Schleife notfalls über alle Elemente:
		ListElement* currentElement = this;
		do
		{
			if( currentElement -> getData()==sTempData )
			{
				return currentElement;
			}

			currentElement = currentElement -> getNext();
		}
		while( currentElement -> getNext()!=NULL );

		// wenn alle Elemente nicht paßten, dann ist die Suche
		// fehlgeschlagen:
		return NULL;
	}

};// class ListElement

void main()
{
	string sData;
	Liste MyList;

	std::cout << "Geben Sie bitte die Elemente die Sie in die verkettete Liste schreiben moechten an!\n";

	for(int i = 0; i < 10; i++)
	{
		std::cout << "Geben Sie das "<< i+1 <<". von maximal 10 Elementen an!\n";
		std::cin >> sData;

		MyList.add(sData);
	}

}