Doppelt verkettete Liste

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Doppelt verkettete Liste

    Hallo, :)

    Vorab erst mal, ich weiss dass es zig Möglichkeiten gibt verkettete Listen zu bauen, selbstverständlich auch nur mit Klassen als Container usw. mir geht es aber hier ums Verständnis der hier benutzten Art von verketteten Listen.
    Das Problem ist wahrscheinlich sehr gering aber ich dreh mich schon seit Tagen um mich selbst und find den Bug nicht!

    Was Funktioniert: :wink:
    1. Die Liste wird korrekt angelegt und ausgegeben auch die Anzahl der Elemente.
    2. Das neue erste Element wird korrekt angelegt und die Liste wird ebenso korrekt ausgegeben auch die Anzahl der Elemente.


    Was nicht funktioniert: :(
    Das neue letzte Element wird wahrscheinlich nicht richtig angelegt und deshalb wird das letzte Element nicht ausgegeben wenn die Liste ausgegeben wird.

    Wird jedoch der obere Teil in der Funktion addNewLastElement(int wert) einkommentiert,
    in diesem Teil füge ich das letzte Element wie bei einer einfach verketteten Liste ein dann funktioniert alles.

    Ich gehe übrigens davon aus dass sich schon ein Element in der Liste befindet (keine Plausibilitätsprüfung) da ich die Liste ja zuvor erstellt habe.
    Ich habe versucht alles so gut und so verständlich wie möglich zu kommentieren.

    Hier der Code für die main():

    Quellcode

    1. #include "List.h"
    3. void main()
    4. {
    5. mvList mvListe;
    6. int i;
    7. int j = 1;
    10. cout << "Liste ist leer !!! ==> Liste mit 3 Elementen bauen" << endl;
    12. for (i = 0; i < 3; i++)
    13. {
    14. mvListe.addElement(j++);
    15. }
    16. mvListe.showElements();
    19. cout << "Neues Erstes Element einfuegen" << endl;
    20. mvListe.addElement(5, FIRST);
    21. mvListe.showElements();
    24. cout << "Neues letztes Element einfuegen" << endl;
    25. mvListe.addElement(10, LAST);
    26. mvListe.showElements();
    28. }
    Alles anzeigen


    Hier der Code für die List.h:

    Quellcode

    1. #include <iostream>
    2. using namespace std;
    4. enum { NONE = 0,FIRST, LAST, MIDDLE };
    6. class mvList
    7. {
    8. private:
    10. //*************************************** SRTUCT ERSTELLEN *************************************
    11. struct Listenknoten
    12. {
    13. int data;
    14. Listenknoten *next;
    15. Listenknoten *prev;
    16. };
    18. public:
    19. //******************************* ZEIGER AUF STRUCT ERSTELLLEN *********************************
    20. Listenknoten *neu;
    21. Listenknoten *head;
    22. Listenknoten *tail;
    23. Listenknoten *current1;
    24. Listenknoten *current2;
    25. int counterElements;
    27. //********************************** KONSTRUKTOR / DESTRUKTOR **********************************
    28. mvList()
    29. {
    30. neu = NULL; // Zeiger mit Null initialisieren
    31. head = NULL; // Zeiger mit Null initialisieren
    32. tail = NULL; // Zeiger mit Null initialisieren
    33. current1 = NULL; // Zeiger mit Null initialisieren
    34. current2 = NULL; // Zeiger mit Null initialisieren
    35. counterElements = 0;
    36. }
    38. ~mvList()
    39. {
    40. neu = NULL; // Zeiger mit Null initialisieren
    41. head = NULL; // Zeiger mit Null initialisieren
    42. tail = NULL; // Zeiger mit Null initialisieren
    43. current1 = NULL; // Zeiger mit Null initialisieren
    44. current2 = NULL; // Zeiger mit Null initialisieren
    46. delete neu;
    47. delete head;
    48. delete tail;
    49. delete current1;
    50. delete current2;
    51. }
    54. //******************************* PROTOS DER MEMBERFUNKTIONEN **********************************
    55. void showElements();
    57. void addElement(int wert, int , int);
    58. void addNewFirstElement(int wert);
    59. void addNewLastElement(int wert);
    60. void addNewMiddleElement(int wert, int atPosition);
    61. };
    64. //**********************************************************************************************
    65. //******************************* ENTSCHEIDUNG FUNKTIONAUFRUFE *********************************
    67. void mvList::addElement(int wert, int atPos = NONE, int pos = 0)
    68. {
    69. if (atPos != NONE)
    70. {
    71. switch(atPos)
    72. {
    73. case FIRST: addNewFirstElement(wert);
    74. break;
    75. case LAST: addNewLastElement(wert);
    76. break;
    77. default:
    78. break;
    79. }
    80. }else
    81. {
    82. addNewFirstElement(wert);
    83. }
    84. }
    85. //**********************************************************************************************
    86. //****************************** NEUES ERSTES ELEMENT EINFÜGEN *********************************
    88. void mvList::addNewFirstElement(int wert)
    89. {
    90. neu = new Listenknoten;
    92. neu->prev = NULL;
    93. neu->next = head;
    94. head = neu;
    96. neu->data = wert;
    98. counterElements++;
    99. cout << "Elemente: " << counterElements;
    100. }
    103. //**********************************************************************************************
    104. //************************* NEUES LETZTES ELEMENT EINFUEGEN INSERT AFTER ***********************
    106. void mvList::addNewLastElement(int wert)
    107. {
    109. neu = new Listenknoten;
    110. //
    111. //
    112. // current1 = head; // einkommentieren
    113. // while (current1->next != NULL) // einkommentieren
    114. // { // einkommentieren
    115. // current1 = current1->next; // einkommentieren
    116. // } // einkommentieren
    117. // neu->next = NULL; // einkommentieren
    118. // // einkommentieren
    119. // current1->next = neu; // einkommentieren
    120. // // einkommentieren
    121. // neu->data = wert; // einkommentieren
    125. neu->next = NULL; // auskommentieren
    126. neu->prev = tail; // auskommentieren
    128. tail = neu; // auskommentieren
    130. neu->data = wert; // auskommentieren
    132. counterElements++;
    133. cout << "Elemente: " << counterElements;
    135. }
    Alles anzeigen


    Vorab schon mal vielen Dank für eure Mühe
    ShadowEater :wink:

  • also ich hab nur mal schnell drüber geschaut und da is mir was ins Auge gefallen:
    du rufst

    Quellcode

    1. mvListe.addElement(5, FIRST);
    mit zwei parametern auf.
    der Prototyp sieht so aus:

    Quellcode

    1. void addElement(int wert, int , int); //(3 Parameter)

    und die ganze Methode:

    Quellcode

    1. void mvList::addElement(int wert, int atPos = NONE, int pos = 0)
    2. {
    3. if (atPos != NONE)
    4. {
    5. //...

    und das frisst dein Compiler??

  • Hallo!

    Erst mal etwas kurzes Programmiertechnisches:
    1. Versuch dir die 8 Einrückungen abzugewöhnen und statt dessen 2 oder 4 Zeichen zu nehmen, da du sonst bei komplexen Programmen leicht den Überblick verlierst (ist aber subjektiv, und dass ist nur meine Meinung).
    2. Im Destruktor von mvList setzt du die Variablen erst auf NULL und rufst dann delete auf - das kann nicht funktionieren, da durch das NULL setzen ja nix mehr drin steht. Lösung: einfach das NULL setzen weg lassen
    3. "neu", "current1" und "current2" sollen keine Membervariablen sein (bei der Klasse definiert) sondern in der Methode, dort wo du sie brauchst.
    Außerdem führt das Löschen dort höchstwahrscheinlich zu einer Zugriffsverletzung (Absturz).
    4. Du löscht im Destruktor nur die 5 Variablen (wovon die 3 oben genannten nicht dort hin gehören), nicht aber die Listenelemente. Daher bleibt dir Speicher übrig (Speicherleak). Lösung:

    Quellcode

    1. virtual ~myList () {
    2. Listenknoten *p = head;
    3. while (p != NULL)
    4. {
    5. Listenknoten *next = p->next; // holen, bevor "p" gelöscht wird!!
    6. delete p; // Speicher freigeben
    7. p = next;
    8. }
    9. }



    Folgenden "Spezialfall" hast du übersehen:
    Wenn addNewFirstElement zum ersten mal aufgerufen wird, musst du sowohl head als auch tail setzen, da das erste Element Anfang und Ende ist! Für addNewLastElement gilt das naatürlich auch.


    Und dein Hauptfehler ist der, dass du einfach immer head und tail neu belegst, aber die vorherigen "head" und "tail" Objekte nicht anpasst:

    Quellcode

    1. // Vergessen: setzen des Vorgängers des "alten" heads
    2. if (head != NULL)
    3. head->prev = neu;
    4. head = neu;

    bzw.

    Quellcode

    1. // Vergessen: setzen des Nachfolgers des "alten" tails
    2. if (tail != NULL)
    3. tail->next = neu;
    4. tail = neu;


    Hierzu ein kleines Beispiel, beginnend bei einer leren Liste, anhand der einzelnen modifizierten Listenknoten:
    addFirst(3):

    Quellcode

    1. [1] neu={3,NULL,NULL)
    2. [2] head={3,NULL,NULL}
    3. [3] tail={3,NULL,NULL)


    addFirst(2):

    Quellcode

    1. [1] neu={2,NULL,head}
    2. [2] head={3,head,NULL}
    3. [3] head=neu --> head={2,NULL,{3,...}}
    4. Zur Info: tail={3,head,NULL} siehe Aktion [2]


    usw. Mir ist klar, dass das nicht ganz intuitiv ist, aber denk mal drüber nach und versuchs zu behirnen. Du kannst das am einfachsten verifizieren, wenn du die Liste einmal von vorne nach hinten durchgehst und schaust, ob genau die umgekehrte Reihenfolge rauskommt wie wenn du von vorne nach hinten durchgehst (siehe Code).

    Adaptiertest List.h:

    Quellcode

    1. #include <iostream>
    2. using namespace std;
    4. enum { NONE = 0,FIRST, LAST, MIDDLE };
    6. class mvList
    7. {
    8. private:
    10. //*************************************** SRTUCT ERSTELLEN *************************************
    11. struct Listenknoten
    12. {
    13. int data;
    14. Listenknoten *next;
    15. Listenknoten *prev;
    16. };
    18. public:
    19. //******************************* ZEIGER AUF STRUCT ERSTELLLEN *********************************
    20. Listenknoten *head;
    21. Listenknoten *tail;
    22. int counterElements;
    24. //********************************** KONSTRUKTOR / DESTRUKTOR **********************************
    25. mvList()
    26. {
    27. head = NULL; // Zeiger mit Null initialisieren
    28. tail = NULL; // Zeiger mit Null initialisieren
    29. counterElements = 0;
    30. }
    32. ~mvList()
    33. {
    34. Listenknoten *p = head;
    35. while (p != NULL)
    36. {
    37. Listenknoten *next = p->next; // holen, bevor "p" gelöscht wird!!
    38. delete p; // Speicher freigeben
    39. p = next;
    40. }
    41. // tail zeigt auf gelöschten Speicher!
    42. }
    45. //******************************* PROTOS DER MEMBERFUNKTIONEN **********************************
    46. void addElement(int wert, int , int);
    47. void addNewFirstElement(int wert);
    48. void addNewLastElement(int wert);
    50. void showElements ()
    51. {
    52. cout << "Vorne nach hinten: ";
    53. Listenknoten *p = head;
    54. while (p)
    55. {
    56. cout << p->data;
    57. if (p->next)
    58. cout << ", ";
    59. p = p->next;
    60. }
    61. cout << endl;
    63. cout << "Hinten nach vorne: ";
    64. p = tail;
    65. while (p)
    66. {
    67. cout << p->data;
    68. if (p->prev)
    69. cout << ", ";
    70. p = p->prev;
    71. }
    72. cout << endl;
    73. }
    74. };
    77. //**********************************************************************************************
    78. //******************************* ENTSCHEIDUNG FUNKTIONAUFRUFE *********************************
    80. void mvList::addElement(int wert, int atPos = NONE, int pos = 0)
    81. {
    82. if (atPos != NONE)
    83. {
    84. switch(atPos)
    85. {
    86. case FIRST: addNewFirstElement(wert);
    87. break;
    88. case LAST: addNewLastElement(wert);
    89. break;
    90. default:
    91. break;
    92. }
    93. }else
    94. {
    95. addNewFirstElement(wert);
    96. }
    97. }
    98. //**********************************************************************************************
    99. //****************************** NEUES ERSTES ELEMENT EINFšGEN *********************************
    101. void mvList::addNewFirstElement(int wert)
    102. {
    103. Listenknoten *neu = new Listenknoten;
    105. neu->prev = NULL;
    106. neu->next = head;
    107. neu->data = wert;
    109. // Vergessen: setzen des Vorgängers des "alten" heads
    110. if (head != NULL)
    111. head->prev = neu;
    113. head = neu;
    115. // Neu:
    116. if (tail == NULL)
    117. tail = head;
    119. counterElements++;
    120. cout << "Elemente: " << counterElements << endl;
    121. }
    124. //**********************************************************************************************
    125. //************************* NEUES LETZTES ELEMENT EINFUEGEN INSERT AFTER ***********************
    127. void mvList::addNewLastElement(int wert)
    128. {
    130. Listenknoten *neu = new Listenknoten;
    132. neu->next = NULL;
    133. neu->prev = tail;
    134. neu->data = wert;
    136. // Vergessen: setzen des Nachfolgers des "alten" tails
    137. if (tail != NULL)
    138. tail->next = neu;
    140. tail = neu;
    142. // Neu:
    143. if (head == NULL)
    144. head = tail;
    146. counterElements++;
    147. cout << "Elemente: " << counterElements << endl;
    149. }
    Alles anzeigen


    Roman-Ende