3. doppelt verkettete Liste

doppelt verkettete Liste

  • K

    Hallo Leute!
    Ich möchte eine einfach vetkettete Liste in eine doppelt verkettete Liste endern. Kann mir da einer helfen?
    Danke... 🙂

    Hier ist mein Programm:

    #include <iostream.h>

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

//Zeiger auf den Anfang
listenelement* listenanfang;

//Hilfzeiger, um inder Liste wandern zu können
listenelement* hilfszeiger;

//Funktion zum Einfügen von Elementen in der Liste

void einfuegen(char datenneu [30]){

  //Hilfszeiger an Anfang der Liste setzen
  hilfszeiger = listenanfang;

  //Neues Element in die Liste einfügen
  hilfszeiger->next = new(listenelement);

  //Daten im neuen Element eintragen
  strcpy(hilfszeiger->next->daten,datenneu);
  hilfszeiger->next = hilfszeiger;
}

//Alle Elemente aus der Liste ausgeben
void ausgeben(){
  //Hilfszeiger auf Anfang der Liste setzen
  hilfszeiger = listenanfang;
  //Erstes Element ausgeben
  cout<< hilfszeiger->daten <<"\n";
  //solange das Ende der Liste nicht erreicht ist
  while (hilfszeiger->next != NULL){
    hilfszeiger = hilfszeiger->next;
    //Daten ausgeben
    cout<< hilfszeiger-> daten<<"\n";
  }
}

//Initialisieren der Liste
void init (){
  //erstes Element erzeugen
  listenanfang = new (listenelement);
  //Daten in das erste Element schreiben
  listenanfang->next = NULL;
  strcpy(listenanfang->daten ,"Element 0");
}

//Liste leeren und Speicher freigeben
void ende(){
  //Solange bis die Elemente in der Liste sind
  while (listenanfang != NULL){
    //Hilfszeiger auf das erste Element der Liste
    hilfszeiger = listenanfang;
    //Zieger für den Listenanfang auf das nächste Element setzen
    listenanfang = listenanfang->next;
    //Das herausgenommene Element löschen
    delete(hilfszeiger);
  }
}
void main(){
  init();
  einfuegen("Element 1");
  einfuegen("Element 2");
  ausgeben();
  ende();
  char p[50];
  cin.getline(p,50);
}
    0
  • C

    1. Bitte Cpp-Codetags benutzen.
    2. Bzg. void main().
    3. Bzg. iostream.h.
    4. Was ist dein konkretes Problem, bzw. woran hängst du? Fehlt dir der Ansatz?, etc. pp.

    Btw. Warum machst du alles mit Funktionen und globalen Variablen und erstellst keine Klasse List o.ä.?. Das lässt sich doch wunderbar kapseln. 🙂

    Gruß Caipi

    0
  • C

    Erstmal wäre es nützlich, code-Tags zu verwenden (dann sehen andere User besser, was dein Programm macht) 😉

    Was mir auf Anhieb aufgefallen ist:
    * Du solltest in deiner Einfügen-Funktion auch den next/last-Zeiger des neuen Elements (und der Nachbarn) korrigieren.
    * hilfszeiger kannst du lokal in den Funktionen deklarieren, die ihn benötigen
    * listenanfang würde ich jeweils als Parameter übergeben (oder gleich objektorientiert arbeiten und alles in einer Klasse "liste" unterbringen).

    0
  • V

    Caipi schrieb:

    1. Bitte Cpp-Codetags benutzen.

    hier wäre ein link angebracht, der dein wort erläutert.

    2. Bzg. void main().
    3. Bzg. iostream.h.

    ich hasse es, wenn profis die nubes so nerven. das ist doch im moment ganz irrelevant.

    0
  • C

    volkard schrieb:

    Caipi schrieb:

    1. Bitte Cpp-Codetags benutzen.

    hier wäre ein link angebracht, der dein wort erläutert.

    Tut mir leid. Mein Fehler. Also @kaschelot: Bzg. Code-tags siehe hier.

    2. Bzg. void main().
    3. Bzg. iostream.h.

    ich hasse es, wenn profis die nubes so nerven. das ist doch im moment ganz irrelevant.

    Wen du mit Profi meinst, weiß ich zwar nicht, aber meine Einstellung ist es (zu versuchen) korrekten Stil zu lehren. (und das beginnt imho bei void main() und iostream.h). Wenn ich jetzt entsprechende Stellen im Code sehe möchte ich den Poster einfach darüber aufklären, dass diese Stellen veraltet, etc. sind. Ich möchte niemanden nerven o.ä... ganz im Gegenteil, ich möchte ihm einen Rat für die Zukunft geben, weil es mir _nicht_ egal ist wie er später programmiert.

    Aber Du hast auch tlw. Recht. Ich hätte den Post anders aufbauen müssen. Erst die problembezogenen Antworten (die in meinem Fall nicht vorhanden waren) und dann am Schluss noch die entsprechenden Hinweise...

    Gruß Caipi

    0
  • K

    Sorry, ich bin doch noch Anfänger. Leider muss die Aufgabe in diesem Still lösen. Wer kann mir da weiter helfen??

    #include <iostream.h>

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

//Zeiger auf den Anfang
listenelement* listenanfang;

//Hilfzeiger, um inder Liste wandern zu können
listenelement* hilfszeiger;

//Funktion zum Einfügen von Elementen in der Liste

void einfuegen(char datenneu [30]){

//Hilfszeiger an Anfang der Liste setzen
hilfszeiger = listenanfang;

//Neues Element in die Liste einfügen
hilfszeiger->next = new(listenelement);

//Daten im neuen Element eintragen
strcpy(hilfszeiger->next->daten,datenneu);
hilfszeiger->next = hilfszeiger;
}

//Alle Elemente aus der Liste ausgeben
void ausgeben(){
//Hilfszeiger auf Anfang der Liste setzen
hilfszeiger = listenanfang;
//Erstes Element ausgeben
cout<< hilfszeiger->daten <<"\n";
//solange das Ende der Liste nicht erreicht ist
while (hilfszeiger->next != NULL){
hilfszeiger = hilfszeiger->next;
//Daten ausgeben
cout<< hilfszeiger-> daten<<"\n";
}
}

//Initialisieren der Liste
void init (){
//erstes Element erzeugen
listenanfang = new (listenelement);
//Daten in das erste Element schreiben
listenanfang->next = NULL;
strcpy(listenanfang->daten ,"Element 0");

}
//Liste leeren und Speicher freigeben
void ende(){
//Solange bis die Elemente in der Liste sind
while (listenanfang != NULL){
//Hilfszeiger auf das erste Element der Liste
hilfszeiger = listenanfang;
//Zieger für den Listenanfang auf das nächste Element setzen
listenanfang = listenanfang->next;
//Das herausgenommene Element löschen
delete(hilfszeiger);
}
}
void main(){
init();
einfuegen("Element 1");
einfuegen("Element 2");
ausgeben();
ende();
char p[50];
cin.getline(p,50);
}

    Danke in vorraus...

    0
  • C

    lies dir mal meine Antwort oben durch 😉
    Ansonsten solltest du dir ganz einfach klar machen, was jede Funktion tun SOLL - und das damit vergleichen, was die Funktionen TATSÄCHLICH tun.

    (und schließlich solltest du auch dazusagen, an welcher Stelle du Probleme hast)

    0
  • C

    Hallo,
    Da dein konkretes Problem noch aussteht, gebe ich mal eine kleine Einführung in die doppelt verketteten Listen.

    Wie du sicher weisst, hat eine doublelinked list ungefähr den folgenden Aufbau:

    first (Zeiger auf Anfang der Liste) last (Zeiger auf das Ende der Liste)
           |                                    |
           |                                    |
NULL <---[Element1] ----> [Element2] ----> [Element3] -----> NULL (eventuell hier auch ein dummy-element)
         [        ] <---- [        ] <---- [        ]

    Hier bezeichnen die <----Pfeile den Previous-Ptr (Der Zeiger, der auf das Vorgänger-Element zeigt), die ------->Pfeile den Next-Ptr (Der Zeiger, der auf das folgende Element zeigt).

    Wenn du jetzt ein Element einfügen willst, beispielsweise nach Element1, dann sieht das schematisch so aus:

    first (Zeiger auf Anfang der Liste)          last (Zeiger auf das Ende der Liste)
          |                                              |
          |        [Neues Element]                       |
          |          ^ /    ^  \                         |
          |         / /      \  \                        |
NULL <---[Element1]  /        \  > [Element2] ----> [Element3] -----> NULL
         [        ] <          \   [        ] <---- [        ]

    Der Next-Ptr von "Element1" zeigt jetzt auf "Neues Element", der Previous-Ptr von "Element2" Ebenfalls. Der Previous-Ptr von "Neues Element" zeigt auf "Element1", der next-Ptr von "Neues Element" auf "Element2".

    D.h. wenn du ein Element einfügen willst, musst du sowohl die Zeiger deines Neuen Elements sowie die zeiger der zukünftigen Nachbarn anpassen. (wie bereits erwähnt von CStoll).

    Das Einfügen ans Ende und an den Anfang ist ähnlich dem oben beschrieben Prinzip, nur dass du dich nur um einen Zeiger (next-Ptr oder previous-Ptr) "kümmern" musst. schematisch würde das anfügen ans Ende der Liste so aussehen:

    first (Zeiger auf Anfang der Liste)                     last (Zeiger auf das Ende der Liste)
          |                                                        |
          |                                                        |
NULL <---[Element1] ----> [Element2] ----> [Element3] -----> [Neues Element] ----> NULL
         [        ] <---- [        ] <---- [        ] <----  [             ]

    Der Previous-Ptr von "Neues Element" wird auf das Vorgänger Element (im Beispiel "Element3") gesetzt, der Next-Ptr auf NULL (o.ä.), da es keinen Nachfolger gibt. Desweiteren wird der Next-Ptr des Vorgängers von "Neues Element" (in unserem Beispiel "Element 3") auf "Neues Element") gesetzt. Als letztes wird noch der last-Ptr, der auf das Ende der Liste zeigt, auf das letzte Element "gebogen". Analog hierzu funktioniert das Einfügen an den Anfang der Liste.

    Die Frage ist jetzt, was soll deine Einfügen-Funktion machen? Soll sie Elemente am Anfang, am Ende oder in der Mitte der Liste anfügen?

    Ich hoffe das war ein klein bischen hilfreich :).

    /edit: Doppelt gemoppelt hält besser ;).

    Gruß Caipi

    0
  • K

    Danke das hat mir weiter geholfen. 🙂 🙂 🙂

    0
Anmelden zum Antworten