3. doppelt verkettete liste

doppelt verkettete liste

  • ?

    Hallo an alle Programmierer,
    Habe hier eine einfach verkettete Liste und verstehe einfach nicht wie ich daraus eine doppelt verkettete liste mache, kann mir irgendjemand helfen und ein paar tipps geben(DANKE IM VORAUS!!!)

    Hier:

    /*#####################################
Einfach verkettete Liste
#####################################*/

#include <iostream.h>

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

listenelement* listenanfang;

listenelement* hilfszeiger;

void einfuegen(char datenneu[30]) {

        hilfszeiger=listenanfang;

        while(hilfszeiger->next!= NULL) {
                hilfszeiger=hilfszeiger->next;
        }
        hilfszeiger->last=hilfszeiger->next;
        hilfszeiger->next=new(listenelement);
        hilfszeiger=hilfszeiger->next;
        strcpy(hilfszeiger->daten,datenneu);
        hilfszeiger->next = NULL;
}

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 main() {
        init();
        einfuegen("Element 1");
        einfuegen("Element 2");
        ausgeben();
        ende();

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

    Du brauchst in der Struct 'listenelement' noch einen zweiten Zeiger auf den Vorgänger - und dann mußt du in allen Funktionen dafür sorgen, daß dieser immer angepasst wird (analog zum Nachfolger-Zeiger).

    PS: "<iostream**.h**>" und "void main()" sind solltest du dir schleunigst abgewöhnen 😉

    0
  • ?

    Ja das weiss ich und ich brauche noch eine funktion die das ganze rückwärts ausgibt, so ist halt die aufgabe, bitte ich stehe voll auf dem schlauch, könnte jemand mir den code ausbessern und einen lösungsvorschlag liefern, wäre sehr dankbar, bitte!!!!!!!!!!

    0
  • C

    In der einfügen()-Methode mußt du nicht nur den next-Zeiger umbiegen, sondern auch den (neu ergänzten) prev-Zeiger, so daß er immer auf den Vorgänger verweist, außerdem brauchst du noch einen globalen Zeiger auf das letzte Element, um dich von dort aus nach vorne durchhangeln zu können.

    (stammt der obige Code wirklich von dir? wenn ja, sollte das eigentlich kein großes Problem werden)

    0
  • ?

    OK ich habs jetzt fast geschafft, und danke für den tipp, aber bei der rückwärts ausgabe fehlt mir das erste element das wird nicht ausgegeben sondern ich glaube die adresse oder sonst noch was ,probiers einfach mal aus, einen tipp noch und dann bin ich fertig und zufrieden:

    /*#####################################
Einfach verkettete Liste
#####################################*/

#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->last=new(listenelement);
        hilfszeiger->next->last=hilfszeiger;
        hilfszeiger=hilfszeiger->next;
        strcpy(hilfszeiger->daten,datenneu);
        hilfszeiger->next = NULL;
        listenende=hilfszeiger;
}

void ausgeben() {
        hilfszeiger=listenanfang;
        cout<<hilfszeiger->daten<<"\n";

        while(hilfszeiger->next!=NULL) {
                hilfszeiger=hilfszeiger->next;
                cout<<hilfszeiger->daten<<"\n";
        }
}

void rueckwaertsausgabe() {
        hilfszeiger=listenende;
        cout<<hilfszeiger->daten<<"\n";

        while(hilfszeiger->last!=NULL) {
                hilfszeiger=hilfszeiger->last;
                cout<<hilfszeiger->daten<<"\n";
        }
}

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

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

void main() {
        init();
        einfuegen("Element 1");
        einfuegen("Element 2");
        ausgeben();
        rueckwaertsausgabe();
        ende();

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

    Das Einfügen ist schon falsch - du mußt nur ein neues Objekt mit new anlegen und in die Liste integrieren:

    --> (letztes) --> NULL
<-- (Element)
        ^
        |
        HZ

--> (letztes) --> ( neues ) --> NULL
<-- (Element) <-- (Element)
                      ^
                      |
                      HZ

    (die Pfeile sollen die beteiligten Pinter darstellen)

    0
  • ?

    und was bedeutet das in code, ich habe es doch richtig gemacht, sobald ein neues auf ein neues element mit next gezeigt wird, zeigt das neue element worauf next zeigt auf das aktuelle(was später das letzte ist) in dem es den wert vom hilfszeiger nimmt da der noch auf das aktuelle zeigt und erst nach dieser zuweisung auf das nächste zeigt, also bei der ausgabe funktioniert es doch, nur das erste element wird nicht ausgegegeben, was ist also daran falsch?

    0
  • ?

    ok moment mal ich habs glaube ich also die zeile hilfszeiger->last=new(listenelement); habe ich einfach weggelassen, und siehe da es funktioniert, hast du das gemeint?

    0
  • C

    Nein, hast du nicht - du hast zusätzlich noch den Vorgängerzeiger des (bisherigen) letzten Elements umgebogen auf ein Element, das irgendwo im Raum steht (und selber nirgends in die Liste eingebunden ist).
    ('hilfszeiger->last' zeigt auf das vorletzte Element - und das sollte auch so bleiben)

    (edit - ja genau die Zeile hatte ich gemeint ;))

    Ansonsten:

    • init() sollte auch das Listenende initialieren (auf das selbe Element, das du dort bereits angelegt hast)
    • in einfügen() ist es nicht notwendig, erst das Ende zu suchen - du hast (wenn du alles richtig gemacht hast) bereits einen Zeiger darauf
    • die cout<<... Zeile in den beiden Ausgabefunktionen kannst du in die Schleife(n) mit reinpacken:
    void ausgeben()
 {
        hilfszeiger=listenanfang;

        while(hilfszeiger!=NULL) {
                cout<<hilfszeiger->daten<<"\n";
                hilfszeiger=hilfszeiger->next;
        }
}
    • Und globale Variablen sind "out" (bei den Zeigern auf Listenanfang und -ende bleibt dir hier nicht viel übrig, obwohl ich die ganze Verarbeitung in einer Klasse gekapselt hätte, aber den Hilfszeiger brauchst du definitiv nicht funktionsübergreifend)
    0
  • W

    c++-starter schrieb:

    Hallo an alle Programmierer,
    Habe hier eine einfach verkettete Liste und verstehe einfach nicht wie ich daraus eine doppelt verkettete liste mache, kann mir irgendjemand helfen und ein paar tipps geben ...

    Du bist nicht der erste, der diese Frage hier stellt. Schau Dir mal diesen und diesen und diesen
    und vielleicht noch den Thread an - und ich bin sicher es gibt noch ein halbes Dutzend davon.

    Es ist überall der selbe Code, der aussieht wie C++ von 1990. Ich würde zu gerne mal wissen, wo die Quelle ist, um davor zu warnen.

    Gruß
    Werner

    PS.: die Suchfunktion scheint zu funktionieren 👍 /Danke

    0
Anmelden zum Antworten