Verkettete Listen in C++

[heinzelmann256]

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 ?

[Christoph Schnauß]

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.

[michamab]

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

[Thomas Schmieder]

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:

• start , zeigt auf das erste Elemet der Kette
• AktElement, zeigt auf das gerade im Zugriff befindliche Element der Kette
• ende, zeigt vpm Ende zurück auf das letzte Element der Kette

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:

• Bubblesort
• Heapsort
• Quicksort

etc

C++ bietet da vorgefertigte Objekte.

Das führt hier aber tatsächlich zu weit.

Viel Erfolg

Tom