3. einfache verkette liste

einfache verkette liste

  • ?

    hallo,
    ich muss eine einfache verkette liste zu einer doppelten verketten liste machen
    benutz den borland c++ 6pro

    beim rückwärstausgeben muss ich ja zuerst das letzte element ausfindig machen
    d.h. next = NULL
    und dann die liste rückwärst ausgeben (richtig???)
    d.h. next = last und von last bis listenanfang

    danke für die hilfe...

    #include<iostream.h>

struct listenelement {
    char daten[30];
    listenelement* next;
    listenelement* last;
};

listenelement* listenanfang;
listenelement* hilfszeiger;
listenelement* listenende;

void einfuegen(char datenneu[30]) {
    hilfszeiger = listenanfang;
    while (hilfszeiger->next != NULL) {
       hilfszeiger = hilfszeiger->next;
    }
    hilfszeiger->next = new(listenelement);
    hilfszeiger = hilfszeiger->next;
    strcpy(hilfszeiger->daten,datenneu);
    hilfszeiger->next = NULL;
}

// nichts ändern
void ausgeben() {
    hilfszeiger = listenanfang;
    cout << hilfszeiger->daten << "\n";
    while (hilfszeiger-> next != NULL) {
        hilfszeiger = hilfszeiger->next;
        cout << hilfszeiger->daten << "\n";
    }
}

void init() {
    listenanfang= new(listenelement);
    listenanfang->next = NULL;
    strcpy(listenanfang->daten, "Element 0");
}

void ende() {
    while (listenanfang != NULL) {
        hilfszeiger = listenanfang;
        listenanfang = listenanfang->next;
        delete(hilfszeiger);
    }
}

void ausgaberueckwaerts() {
    hilfszeiger = listenanfang;
    while (hilfszeiger-> next != NULL) {
        hilfszeiger = hilfszeiger->next;
    }
}
// nichts ändern
void main() {
        init();
        einfuegen("element 1");
        einfuegen("element 2");
        ausgeben();
        ausgaberueckwaerts();
        ende();

char p[50];
cin.getline(p,50);
}
    0
  • C

    Und jetzt bitte auf Deutsch: Wo ist dein Problem? Du hast doch schon einen Zeiger 'listenende' definiert, den du beim Einfügen und Löschen von Elementen auch aktualisieren solltest, wenn es erforderlich ist. Damit kommst du sofort an das letzte Element und kannst dich dann entlang der last-Zeiger vorhangeln bis zu Listenanfang (der z.B. durch last==NULL gekennzeichnet werden kann).

    0
  • B

    hats du den sinn einer doppelt verketten liste verstanden?

    in einer einfachverketten liste, zeigen die elemente ja ommer auf ihren nächsten (rechten) bruder. Bei einer doppelt verketten liste zeigen alle elemetne jeweil auf ihr nächsten und vorhigen (linken/ und rechten ) bruder

    class element{

 element *pNext; //Rechter bruder
 element *pPref; //Linker bruder

 //DATA

};
    0
  • ?

    ok mein problem ist wie akutalisier ich den zeiger in der funktion einfügen?

    mein code guckt grade so aus. blos das ja totaler misst...

    #include<iostream.h>

struct listenelement {
    char daten[30];
    listenelement* next;
    listenelement* last;
};

listenelement* listenanfang;
listenelement* hilfszeiger;
listenelement* listenende;

void einfuegen(char datenneu[30]) {
    hilfszeiger = listenanfang;

    while (hilfszeiger->next != NULL) {
       hilfszeiger = hilfszeiger->next;
    }

    hilfszeiger->next = new(listenelement);
    listenende = hilfszeiger;
    hilfszeiger = hilfszeiger->next;

    strcpy(hilfszeiger->daten,datenneu);
    hilfszeiger->next = NULL;
    hilfszeiger->last = listenende;
    listenende = hilfszeiger;
    }

// nichts ändern
void ausgeben() {
    hilfszeiger = listenanfang;
    cout << hilfszeiger->daten << "\n";
    while (hilfszeiger-> next != NULL) {
        hilfszeiger = hilfszeiger->next;
        cout << hilfszeiger->daten << "\n";
    }
}

void init() {
    listenanfang= new(listenelement);
    listenanfang->next = NULL;
    listenanfang->last = NULL;
    listenende = listenanfang;
    strcpy(listenanfang->daten, "Element 0");
}

void ende() {
    while (listenanfang != NULL) {
        hilfszeiger = listenanfang;
        listenanfang = listenanfang->next;
        delete(hilfszeiger);
    }
}

void ausgaberueckwaerts() {
    hilfszeiger = listenanfang;
    while (hilfszeiger->last != NULL) {
        hilfszeiger = hilfszeiger->last;
    cout << hilfszeiger->daten << endl;
    }
}
// nichts ändern
void main() {
        init();
        einfuegen("element 1");
        einfuegen("element 2");
        ausgeben();
        ausgaberueckwaerts();
        ende();

char p[50];
cin.getline(p,50);
}
    0
  • C

    Mein Vorschlag: Zeichne es dir auf, dann siehst du leichter, welcher Zeiger wohin gebogen werden muß:

    ...<-- El     x- El
   --> alt-x     neu -x
        ^
last ---+

...<-- El <-- El
   --> alt--> neu-x
               ^
last ----------+
    0
  • B

    absolut, zeichne es dir auf.. 😉 😃 Ich weis wovon ich spreche;)

    0
  • ?

    Hier mal sowas wie nen grafisches Tutorial für einfach verkette Listen.
    Musste ich mal für die Klasse vorbereiten. Ist zwar nicht so gut, wenn ich nicht dazu referiere aber egal 😉 :
    http://www.livetip.de/data/list.htm

    Edit: In ne html Datei eingebetet, damit man nicht die Datei runterladen muss.

    0
  • W

    Ich finde den Code des Threaderstellers furchtbar. Furchtbar, weil er globale Variablen benutzt, char-Arrays mit festen Längen benutzt und weil es reiner C-Code ist, und das im C++-Forum vorstellt wo C++ doch alle Möglichkeiten hat, diese Nachteile aus dem Weg zu räumen.
    Ich find's auch deshalb furchtbar, weil ich genau diesen Code hier mindestens schon drei mal gesehen habe - der scheint irgendwo in einem Lehrbuch zu stehen 👎

    Das ist die gleiche einfach verkette Liste in C++ implementiert (jedenfalls nach meiner unbedeutenden Meinung):

    // SList.h
template< typename T >
class SList
{
public:
    typedef T value_type;

private:
    class Node  // Listenelement
    {
    public:
        explicit Node( const value_type& x, Node* next = 0 )
            : m_next( next )
            , m_value( x )
        {}
        Node* m_next;
        value_type m_value;
    };

public:
    SList()     // ersetzt das init()
        : m_kopf( value_type() )
        , m_ende( &m_kopf )
    {}
    ~SList() { clear(); } // immer schön wieder aufräumen

    void push_back( const value_type& x ) // ersetzt das einfuegen() was ein anhaengen() ist
    {
        m_ende->m_next = new Node( x );
        m_ende = m_ende->m_next;
    }

    void clear() // ersetzt das ende()
    {
        for( Node* p = m_kopf.m_next; p; )
        {
            Node* tmp = p;
            p = p->m_next;
            delete tmp;
        }
        m_kopf.m_next = 0;
        m_ende = &m_kopf;
    }

    // --   Ausgabe
    std::ostream& ausgeben( std::ostream& out, const char* delim = "" )
    {
        for( Node* p = m_kopf.m_next; p; p = p->m_next )
        {
            out << p->m_value << delim;
        }
        return out;
    }

private:
    // Kopieren z.Zt. nicht vorgesehen; -> "Regel der drei"
    SList( const SList& );
    SList& operator=( const SList& );

    // --   Member
    Node m_kopf;
    Node* m_ende;
};

    .. und wer nicht weiß was ein Template ist, ok kein Problem; der lassen die Zeile mit dem 'template' einfach weg und ersetze das T bei typedef durch den Typ seiner Wahl (z.B. int oder std::string)

    und das gleiche nochmal mit der doppelten Verkettung:

    // DList.h
class DList
{
public:
    typedef T value_type;

private:
    class Node  // Listenelement
    {
    public:
        explicit Node( const value_type& x, Node* prev, Node* next )
            : m_next( next )
            , m_prev( prev )
            , m_value( x )
        {}
        Node* m_next;
        Node* m_prev;
        value_type m_value;
    };

public:
    DList()     // ersetzt das init()
        : m_kopf( value_type(), &m_kopf, &m_kopf )
    {}
    ~DList() { clear(); }

    void push_back( const value_type& x ) // ersetzt das einfuegen() was ein anhängen ist
    {
        m_kopf.m_prev->m_next = new Node( x, m_kopf.m_prev, &m_kopf );
        m_kopf.m_prev = m_kopf.m_prev->m_next;
    }

    void clear() // ersetzt das ende()
    {
        for( Node* p = m_kopf.m_next; p != &m_kopf; )
        {
            Node* tmp = p;
            p = p->m_next;
            delete tmp;
        }
        m_kopf.m_next = &m_kopf;
        m_kopf.m_prev = &m_kopf;
    }

    // --   Ausgabe
    std::ostream& ausgeben( std::ostream& out, const char* delim = "" )
    {
        for( Node* p = m_kopf.m_next; p != &m_kopf; p = p->m_next )
        {
            out << p->m_value << delim;
        }
        return out;
    }
    std::ostream& ausgaberueckwaerts( std::ostream& out, const char* delim = "" )
    {
        for( Node* p = m_kopf.m_prev; p != &m_kopf; p = p->m_prev )
        {
            out << p->m_value << delim;
        }
        return out;
    }

private:
    // Kopieren z.Zt. nicht vorgesehen; -> "Regel der drei"
    DList( const DList& );
    DList& operator=( const DList& );

    // --   Member
    Node m_kopf;
};

    und das main dazu

    #include <iostream>
#include <string>

#include "DList.h"

int main()
{
    using namespace std;
    DList< string > l;
    l.push_back( "Hello" );
    l.push_back( "World" );
    l.ausgeben( cout, " " ) << endl;
    l.ausgaberueckwaerts( cout, " " ) << endl;
    return 0;
}

    und schlussendlich halte ich es immer noch für wichtiger, dass ein Anfänger lernt std::list<> anzuwenden, bevor er lernt eine Liste selber zu programmieren.

    KasF schrieb:

    Hier mal sowas wie nen grafisches Tutorial für einfach verkette Listen.
    Musste ich mal für die Klasse vorbereiten. Ist zwar nicht so gut, wenn ich nicht dazu referiere aber egal 😉 :
    http://www.livetip.de/data/list.htm

    das finde ich richtig gut 👍 . Wenn Du noch Initialisierungslisten nutzen würdest und die Regel der drei einbaust (Kopy-ctor und Assignment-operator) dann wär's perfekt.

    Gruß
    Werner

    0
  • ?

    Werner Salomon schrieb:

    das finde ich richtig gut 👍 . Wenn Du noch Initialisierungslisten nutzen würdest und die Regel der drei einbaust (Kopy-ctor und Assignment-operator) dann wär's perfekt.

    Danke. Vielleicht erweitere ich es mal irgendwann. Mein Lehrer hatte schon genug Probleme der Klasse ne verkette Liste in den Kopf zu setzen, da wären Initialisierungsliste, Templates, Regel der drei etc. der Tod der Schüler 🙂

    0
Anmelden zum Antworten