[C++] Sortierte Listen

MesserJack

Cadet 4th Year
Registriert
Dez. 2006
Beiträge
102
Moin Leute,

und zwar habe ich probleme bei den Abstrakten Datenstrukturen. Ich möchte eine sortierte Liste implementieren, welche schon beim einfuegen der Daten die richtige Stelle einfuegt.
PHP:
template <class T>
class sortListe
{
private:
	T data;
	sortListe<T> *next;
public:
	sortListe(T elem);   // Konstruktor erstellt ein neues Objekt und Desktruktor löscht halt alles
	~sortListe();

	void einfuegen(T elem); // einfuegen bereitet mir am meisen Probleme
	bool is_elem();
	void loesch_elem( T elem);
	void print();
};
l
PHP:
#include <iostream>
#include "liste.h"

using namespace std;
/*
Erstellt einfach ein neuers Objekt. Das Element wird halt in data geschrieben und der Zeiger wird auf Null gesetzt.*/
template <class T> sortListe<T>::sortListe(T elem)
{
	sortListe<T> *neu = new sortListe<T>();
	neu->data = elem;
	neu->next = NULL;
}
/*
Die while-Schleife läuft so lange, bis sie die vorletzte Liste gelöscht hat. Die letzte muss man noch separat löschen*/
template <class T> sortListe<T>::~sortListe()
{
	while(sortListe->next != NULL)
	{
		sortListe<T> *next = sortListe->next;
		delete sortListe<T>();
		sortListe<T>()= next;
	}
	delete sortListe<T>();
}

template <class T> void sortListe<T>::print()
{
	if(sortListe == 0)
	{
		cout << "Liste ist leer" << endl;
		return;
	}
	sortListe<T> * tmp=list; // Der listenkompf wird kopiert und dann läuft er halt von vorne nach hinten
	while(tmp != 0){
		cout << tmp->data << " ";
		tmp = tmp->next;
	}
	cout << endl;
}

template <class T> void sortListe<T>::einfuegen(T elem)
{
	sortListe<T> *neu = new sortListe<T>();
	if(sortListe->next == 0) // Erster Fall) Falls die Liste leer sein sollte wird hier halt der Fall abgefangen
	{
		neu->data = elem; // Funktioniert so wie der Kontruktor
		neu->next = 0;
	}
	if(elem < sortListe->data) // Als 2. Fall habe ich angenohmen, dass das neue Element das kleinste ist und am Anfang eingefügt wird
	{
		neu->next = sortListe<T>();
	}
	sortListe<T> *tmp = sortList<T>(); // Hier happert es bei mir. Mir fehlt allgemein das Verständnis bei den ADT.
	while(sortListe->next !=0 && sortListe->next->data < elem) // Hier sollten die Fälle abgefangen werden, wenn das Listenelement 
//mittendrin ist oder an das Ende kommt.
	{
          sortListe<T>() = sortListe->next; // Mittendrin
	}

}
template <class T> bool sortListe<T>::is_elem(T elem)
{
	while(sortListe->next!=0){
		if (sortListe->data == elem)
			return true;
		else return false;
	}
}
Wie es zu erwarten war lässt es sich nicht compilieren. Und ich verstehe auch nicht, so richtig, wie es mit den Klassen funktioniert.
Bei eine struct musste man noch die liste übergeben, also würde die Funktionsdeklaration is_elem ungefähr so aussehen
bool is_elem(sortListe *list, T elem);
Die Methode löschen versuche ich noch selber, aber ich hoffe ihr könnt mir bei diesen Methoden hier erstmal helfen.

Mit freundlichen Grüßen
Michael K.
 
Zuletzt bearbeitet:
Wozu willst du den Aufwand treiben und die Liste sortieren?
Du musst doch nur in der Einfügefunktion darauf achten, an welche Stelle das Element kommt. Dazu müssen die Elemente natürlich vergleichbar sein.
Es gibt nur 2 Sonderfälle, einmal, wenn die Liste leer ist, das neue Element also das Einzige ist und wenn das neue Element das Größte ist, also am Ende eingefügt wird. Für den Rest iterierst du über alle Elemente, bis das aktuelle Element größer als das neue Element ist und hängst die Zeiger so um, dass das neue Element vor dem aktuellen Element eingefügt wird.
 
Ich will eine sortierte Liste erstellen, also dass sie sich schon zur Laufzeit selbst sortiert, wie ich es oben geschrieben habe.
Mir ist klar, dass es den Fall gibt, wenn die Liste leer ist, also muss ein neues Objekt erstellt werden. Dann der Fall, dass das neue Element das kleinste ist. Dann muss das neue Objekt am Anfang hinzugefügt werden. Und dann, wenn es mittendrin bzw. zum Schluss kommt. Nur dass was mir Probleme bereitet ist, wie ich die Methoden richtig schreibe. Von der Idee her ist es mir klar, aber dann tauchen die Probleme auf.
 

Anhänge

  • list.png
    list.png
    23,4 KB · Aufrufe: 333
Zurück
Oben