Verkettete Listen in C++
heinzelmann256
- programmiertechnik
In bin momentan fleißig am C++ lernen (brauch es für ein Server-Projekt). Ich hab mir ein Buch gekauft und bin schon recht schnell voran gekommen. Leider bin ich gerade beim Thema Verkettete Listen stecken geblieben. Irgendwie verstehe ich nicht, wie man mit Hilfe der Zeiger, die Liste sortiert. Kann mir jemand helfen ?
hi,
In bin momentan fleißig am C++ lernen (brauch es für ein Server-Projekt). Ich hab mir ein Buch gekauft und bin schon recht schnell voran gekommen. Leider bin ich gerade beim Thema Verkettete Listen stecken geblieben. Irgendwie verstehe ich nicht, wie man mit Hilfe der Zeiger, die Liste sortiert. Kann mir jemand helfen ?
ich weiß ja nicht, was für ein Buch du dir da besorgt hast. Aber vielleicht hilft dirhttp://www.volkard.de/vcppkold/zeiger.html weiter
Christoph S.
Hmm, du hast deine Frage zimelich algemein gehalten und außerdem passt sie nicht ganz zum Thema dieses Forums. Ein richtiges C++Forum wäre hier besser, <schleichwerbung> besuche doch z.B. mal http://www.c-plusplus.de </schleichwerbung>.
<img src="/images/08.gif" width=213 height=100 border=0 alt="Schau mal unter folgenden Links nach:">
Ich versuche es aber trotzdem mal in den Grundzügen zu erklären, denn ich hab heute meine gute Laune :) .
Du hast eine Klasse, welche eine Menge Anwendungen und Variablen für ein Objekt enthält. Jedes mal, wenn du ein Objekt erstellst, musst du den Konstruktor aufrufen.
Hier erstmal eine Bsp.-Klasse:
// vorher noch notwendige Header inkludieren
class Auto
{
privat:
int max_geschw;
int farbe;
char name;
char hersteller;
public:
Auto *autoNext; // Zeiger dient zum Anhängen des nächsten Elements
void getWerte();
void setWerte(int t_max_geschw, int t_farbe, char t_hersteller, char t_name);
}
class verkettListe
{
private:
Auto *obObj; // Zeiger auf das erste Objekt der Liste
public:
verkettListe (void); // Konstruktor
void push (int t_max_geschw, int t_farbe, char t_hersteller, char t_name); // Neues Objekt dazu
void pop (void); // Oberstes Objekt löschen
void first (void); // Oberstes Objekt anzeigen
void show (void);
// Ich verzichte mal hier auf den Destruktor, benutze den
// Standard-Destruktor
}
Auto::getWerte()
{ // Werte ausgeben
cout << "Name: " << name << endl;
cout << "Farbe: " << farbe << endl;
cout << "Hersteller: " << hersteller << endl;
cout << "Max. Geschw.: " << max_geschw << endl;
}
Auto::setWerte(int t_max_geschw, int t_farbe, char t_hersteller, char t_name)
{ // Werte zuweisen
name = t_name;
farbe = t_farbe;
hersteller = t_hersteller;
max_geschw = t_max_geschw;
}
// Bis herher solltest du noch alles verstehen
// jetzt werden die Listen-Funktionen definiert
// Konstruktor
verkettListe::verkettListe()
{
obObj = NULL;
}
// Element an die Liste anhängen
verkettListe::push (int t_max_geschw, int t_farbe, char t_hersteller, char t_name)
{
Auto *autoNew = new Auto; // neues Raumschiff-Objekt
autoNew->setWerte (int t_max_geschw, int t_farbe, char t_hersteller, char t_name);
autoNew->autoNext = obObj; // Zeiger umbiegen
obObj = autoNew; // Oberstes Objekt
}
// obObj zeigt also immer auf das oberste Objekt unserer Liste
void verkettListe::pop (void)
{
if (obObj != NULL)
{
Auto *aPop = obObj;
obObj = obObj->autoNext;
delete aPop;
aPop = NULL;
}
}
// ein neues Objekt wird an die Liste rangehängt
// der Zeiger obObj wird auf das neue
// oberste Objekt umgebogen
void verkettListe::first (void)
{
obObj->getWerte ();
}
// das oberste Objekt wird gezeigt
// logisch, da wir dank dem Zeiger obObj noch
// direkten Zugriff auf das Objekt haben
void verkettListe::show (void)
{
int counter = 1;
Auto *aTemp = obObj; // Zeiger auf das erste Objekt
while (aTemp != NULL) // Ende der Liste erreicht ?
{
cout << "Nummer : " << counter << endl;
aTemp->getWerte ();
aTemp = aTemp->autoNext; // Zeiger auf das nächste Objekt richten
counter++;
}
}
An diesem Beispiel erkennt man ganz gut wie die Liste funktioniert. Jedes Obj. hat einen Zeiger, welcher auf seinen Vorgänger zeigt. Da das oberste Objekt aber keinen Nachfolger hat, der auf das Objekt zeigt, haben wir diesen in der verkettListe-Klasse (Zeiger: obObj).
Wenn es noch weitere Fragen gibt, frage am besten in einem dafür gedachten Fachforum ! Ich hoffe es hilft dir weiter.
Für Fehler keine Haftung :)
Gruß Michamab
Leider bin ich gerade beim Thema Verkettete Listen stecken geblieben. Irgendwie verstehe ich nicht, wie man mit Hilfe der Zeiger, die Liste sortiert.
Hallo Heinzel..,
besonders ausführliche Antwort hast Du ja schon von Micha bekommen.
Ich will deshalb auch nur wenig Senf dazugeben:
1. Mal Dir ein Bild, um den Überblick zu behalten
---------
start ---->|Wert |
NULL <-----|lastPtr| ---------
|nextPtr| ----> |Wert |
--------- <---- |lastPtr|
^ |nextPtr| ----> ..... ----> NULL
| --------- <---- ..... <---- ende
|
|
|
AktElementPtr
Es gibt drei statische Pinter-Variablen:
Um mit der Kette arbeiten zu können, benötigt man mindesten einen Hilfszeiger. Man kann ja nicht AktElement testweise einfach ein Element weiterrücken, ohne sich gemerkt zu haben, wohin der voerher gezeigt hat...
2. Entscheide Dich für eine Sortiermethode:
etc
C++ bietet da vorgefertigte Objekte.
Das führt hier aber tatsächlich zu weit.
Viel Erfolg
Tom