heinzelmann256: Verkettete Listen in C++

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 ?

  1. 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.

  2. 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

  3. 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