Listen in C++

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

  • Listen in C++

    Hallo, hab hier ne Aufgabe, die ich leider nicht richtig verstehe. Ich müsste sie nichtmal komplett lösen (eine Teilaufgabe würde reichen, ist nur zur Übung).


    Aufgabenstellung:
    ¨
    Gegeben ist ein Beispielprogramm zur Verwendung von Listen. Dieses besteht aus einer Klasse List, welches eine einfach verkettete
    Liste zur Abspeicherung von positiven ganzen Zahlen implementiert und der main-Funktion,
    über welche die Liste mit Elementen gefüllt wird. Das Anhängen neuer Listenelemente erfolgt
    über die Methode append.
    ¨
    a) Durch das Anhangen der neuen Elemente an die Liste, ergibt sich eine unsortierte Folge
    von Zahlen.

    Erweitern Sie die Klasse List um die Methode insert zur Implementierung einer sortier-
    ten Liste. Uber das Einfugen von Elementen mit der insert-Funktion wird ein sortiertes
    Einfügen von Elementen ermoglicht, sodass zu jeder Zeit eine aufsteigende Folge von
    Zahlen in der Liste gegeben ist.

    b) Schreiben Sie eine Methode delete zum gezielten Loschen von Listenelementen. Diese
    bekommt als Parameter den Wert der zu loschenden Elemente. Erweitern Sie das Haupt-
    über welche der Benutzer selbst gewahlte Elemente aus der
    programm um eine Schleife,
    Liste löschen kann. Weiterhin soll nach jedem Loschen der vollstandige Inhalt der Liste
    ausgegeben werden.


    Das Ganze bezieht sich auf diese .CPP:

    Quellcode

    1. #include <iostream>
    2. using namespace std;
    4. /*
    5. * myList - Version 0.02
    6. *
    7. * (c) 2005 by paedubucher
    8. *
    9. * Eine einfache C++-Klasse, welche eine minimale ArrayList für vorzeichenlose
    10. * Integers darstellt. Es können dabei Zahlen von 0 bis zur Integer-Obergrenze
    11. * gespeichert werden.
    12. *
    13. */
    15. // Struktur für die Speicherung eines Werts
    16. struct Value
    17. {
    18. public:
    19. Value *vluNext; // Zeiger auf das naechste Element
    20. unsigned int intValue; // Wert
    21. };
    23. // Eine einfache ArrayList fuer Zahlen von 0 bis zur Integer-Obergrenze
    24. class List
    25. {
    26. private:
    27. Value *vluFirst; // erstes Element der Liste
    28. Value *vluLast; // letztes Element der Liste
    29. unsigned int intCount; // Anzahl Elemente in der Liste
    31. // Gibt den Listeneintrag mit dem uebergebenen Index zurueck
    32. Value *getValue(unsigned int intIndex) const
    33. {
    34. unsigned int n = 0;
    35. Value *vluTemp = this->vluFirst; // erstes Element
    37. // Index im gueltigen Bereich?
    38. if(intIndex < this->intCount)
    39. {
    40. // vluTemp um intIndex verschieben
    41. for(; n < intIndex && vluTemp->vluNext != NULL; n++)
    42. vluTemp = vluTemp->vluNext; // nächstes Element
    43. }
    44. else
    45. vluTemp = NULL;
    47. return (vluTemp); // Rueckgabe von NULL bedeutet ungueltigen Index!
    48. }
    50. public:
    51. // Konstruktor
    52. List()
    53. {
    54. this->vluFirst = NULL;
    55. this->vluLast = NULL;
    56. this->intCount = 0;
    57. }
    59. // haengt der Liste einen neuen Eintrag mit dem uebergebenen Wert an
    60. void append(unsigned int intNewValue)
    61. {
    62. Value *vluNew = 0;
    64. // neues Element erstellen
    65. vluNew = new Value;
    66. vluNew->intValue = intNewValue;
    67. vluNew->vluNext = NULL;
    69. if(this->vluFirst == 0)
    70. {
    71. // erstes Element
    72. this->vluFirst = vluNew;
    73. this->vluLast = vluNew;
    74. }
    75. else
    76. {
    77. // anhaengen
    78. this->vluLast->vluNext = vluNew;
    79. this->vluLast = vluNew;
    80. }
    82. this->intCount++; // Anzahl der Listenelemente erhoehen
    83. }
    85. // gibt den Wert des Elements mit dem uebergebenen Index zurueck
    86. int get(unsigned int intIndex) const
    87. {
    88. int intRet = -1; // Dummy-Wert
    89. Value *vlu = NULL;
    91. // Index gueltig?
    92. if(intIndex < this->intCount)
    93. {
    94. vlu = this->getValue(intIndex); // Listeneintrag suchen
    95. if(vlu != NULL)
    96. intRet = vlu->intValue; // Wert speichern
    97. }
    99. return (intRet);
    100. }
    102. // Anzahl der Listenelemente zurueckgeben
    103. int getCount() const
    104. {
    105. return (intCount);
    106. }
    107. };
    113. int main ()
    114. {
    115. List zahlenliste;
    117. int zahl = 0;
    119. while (zahl >= 0)
    120. {
    121. cout << "Bitte naechste Zahl eingeben (Abbruch bei Zahlen < 0): ";
    122. cin >> zahl;
    124. if (zahl >= 0)
    125. {
    126. zahlenliste.append(zahl);
    127. }
    128. }
    130. cout << "Liste der eingegebenen Zahlen " << endl;
    131. for (int i=0; i < zahlenliste.getCount(); i++)
    132. cout << zahlenliste.get(i) << " ";
    134. return 0;
    135. }
    Alles anzeigen


    Gruß,

    cewbie

  • Wo hakts denn? Bei einfachen verketteten Listen ist das sortierte einfügen nur möglich wenn die Liste sowieso schon sortiert ist. Entweder prüfst du das ab oder gehst einfach davon aus, dass es so ist. Dann musst du solange die Elemente angucken, bist du die Stelle gefunden hast wo dein Listeneintrag hingehört, biegst zwei Zeiger um un fertig. Beim löschen genauso.

    Laufzeit ist O(n), das ist halt bei einfach verketteten Listen nicht schneller machbar.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]

  • SeBa schrieb:

    ... gehst einfach davon aus, dass es so ist. Dann musst du solange die Elemente angucken, bist du die Stelle gefunden hast wo dein Listeneintrag hingehört, biegst zwei Zeiger um un fertig. Beim löschen genauso.


    Ja wie mache ich denn das? Ich verstehe schon WAS ich machen soll, nur nicht WIE. DIe Aufgabe ist irgendwie viel schwieriger als alles, was wir vorher hatten...

    :roll:

    cewbie

  • Ein Listenelement ist ein Record und beinhaltet die Zahl und einen Zeiger. Guck dir die Zahl an wenn die es ist die du suchst dann nimmst du den Record den du einfügen willst, und setzt den Zeiger (vluNext) von deinem Record auf den Wert vom gefundenen Record und den Zeiger vom gefunden Record lässt du auf dein Record zeigen.
    Wenn die Zahl es nicht ist, guckste was im Record steht auf den vluNext zeigt.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]