Einfügen und Löschen in einer sortierten Liste?
Hallo, ich habe eine einfach verkette Liste in C++ mit Einfüge- und Lösch-Operation.
Leider funktioniert sie noch nicht, wie sie soll. Beim Einfügen werden die Werte mit cin gelesen, aber wenn ich die Zahlen 1.4 2.3 5.6 eingebe, wird nur 1.4 ausgegeben.
Habe ich in der Methode inserte() einen Logikfehler?
#include <iostream>
using namespace std;
class Elem {
private:
const double zahl;
Elem *next;
public:
Elem(double a, Elem *b): zahl(a), next(b) {
}
friend class List;
};
class List {
private:
Elem *head;
public:
List(): head(nullptr) {
}
void inserte(double a) {
if ((head == nullptr) || (head->zahl > a)) {
head = new Elem(a, head);
}
else {
Elem *b = head;
for(; ((b->next != nullptr) || (b->next->zahl <= a)); b = b->next) {
}
Elem* tmp = new Elem(a, b->next);
b->next = tmp;
}
}
bool remove(double a) {
Elem *tmp;
if ((head == nullptr) || (head->zahl > a)) {
return false;
}
else if (head->zahl == a) {
tmp = head;
head = head->next;
delete tmp;
}
else {
for (tmp = head; tmp->next->zahl < a; tmp = tmp->next) {
}
if ((tmp->next == nullptr) || (tmp -> next->zahl > a)) {
return false;
}
else {
Elem * help = tmp->next;
tmp ->next = tmp->next->next;
delete help;
return true;
}
}
return false;
}
void output() {
int i = 0;
for (Elem *tmp = head; tmp != nullptr; tmp = tmp->next) {
cout << tmp->zahl << '\n';
i++;
}
cout << "Anzahl der Elemente: " << i << '\n';
}
};
int main() {
double a;
List b;
while (cin >> a) {
if (a > 0) {
b.inserte(a);
}
else if (a < 0) {
b.remove(-a);
}
else {
break;
}
b.output();
}
return 0;
}
1 Antwort
Sehe da schon ein kleines Problem: Ich vermute, dass deine for-Schleife nie aufgerufen wird. Du setzt (aus mir bisher nciht ganz ersichtlichen Gründen) einen neuen Element-Pointer b auf den head (statt einfach head zu nutzen - okay. Vielleicht wolltest du damit bis zum Ende iterieren?) Danach willst du in die Schleife, die aber nur unter der Bedingung ausgeführt wird, dass b->next != nullptr (was nicht der Fall sein wird, da der next-Pointer von head nach dem ersten Element definitiv nullptr sein wird (oder random bullshit, ist mir auch schon mal passiert)), oder, falls b->next->zahl <= a (was auch nicht der Fall sein wird, denn wenn b->next, was ja head->next ist, nicht existiert, kannst du auch cniht auf b->next->zahl zugreifen).
Generell hast du da glaube ich in der for-schleife etwas durcheinandergebracht, deshalb hier zwar eine semantische Lösung, aber kein Code (damit du nciht einfach kopierst, sondern auch was lernst):
Der erste Part ist korretk: Sofern head nicht existiert, bist du beim ersten Element einer neuen Liste. Setze dieses also als head.
Sollte head bereits existieren, nimm' dir ein Element tmp und setze es auf head.
Iteriere nun so lange durch deine Liste, indem du tmp immer auf das nächste Element setzt, bis du beim letzten Element ankommst (Tipp: was gilt dann für tmp->next?).
Jetzt erstellst du ein neues Element mit deiner eingegebenen Zahl, und setzt es als Nachfolger des aktuell letzten Elements. Somit zeigt dein zuvor letztes Element auf das neue am Ende der Liste, und das neue letzte Element zeigt auf ... ja, wohin wohl?
Falls das Ganze keine Queue werden soll, und die Reihenfolge der Elemente egal ist, hier noch eine etwas simplere Semantik:
Das mit dem nicht existenten head bleibt so.
Wenn head bereits existiert, erstelle direkt ein neues Element, und lasse es als nächstes auf den aktuellen head zeigen.
Setze nun den head auf dein neues Element.
Einfügen am Anfang der Liste wirkt zwar weird, weil es die Reihenfolge der eingegebenen Elemente umkehrt, wenn die jedoch nicht wichtig ist (oder du einfach rückwärts iterieren kannst, was in der Gesamtlaufzeitkomplexität vermutlich schneller ist, als bei jedem Einfügen über alles zu iterieren, sofern du häufiger einfügst, als du liest), geht das schneller und einfacher.
Und weil mir langweilig ist, ein Bonus:
willst du die Reihenfolge beibehalten, aber trotzdem schnell einfügen, speichere dir neben head auch noch end bzw. tail ab, was ein Pointer auf das letzte Element darstellt. Den änderst du einfach nach jedem Einfügen, und schon ist einfügen statt O(n) auch O(1).
Irgendwas davon sollte dir sicherlich weiterhelfen können :D
