Liste, ohne Knoten zu verlieren
Mission
Implementiere die fehlenden Listenfunktionen auf Papier. Dein Sicherheitsgesetz: Erst den Restweg sichern, dann head verändern.
struct liste_node {
int ele;
liste_node* next;
};
struct liste {
liste_node* head;
size_t len;
};Ein Symbol übersetzen
lis->head->next bedeutet …
-> heißt: „Gehe zu dem Objekt, auf das der Zeiger zeigt, und nimm sein Feld …“lis → head führt zum ersten Knoten; dessen Feld next führt zum zweiten Knoten.Den Restweg retten
Die Liste ist 7 → 18 → 43 → null. Du willst den ersten Knoten löschen. Klicke die Codezeilen in sicherer Reihenfolge.
- Noch keine Zeile ausgeführt.
Liste direkt manipulieren
Arbeite wie im main: Führe die Operationen aus und beobachte, welche Pointer sich ändern.
Start: head = nullptr, len = 0.
Nach diesen vier Aufrufen: Welche Zeile implementiert pushfront(lis, t) ohne die Restliste zu verlieren?
Kernfunktionen zusammensetzen
Wähle jeweils die mechanisch passende Zeile. Es geht um eine tiefe Kopie: neue Knoten, gleiche Werte.
clear darfst du nach delete head nicht mehr head->next lesen. Sichere oder verschiebe den Zeiger zuerst.src wird nur gelesen; für dst entsteht pro Quellknoten ein new.Prüfungs-Trace aus dem Original
lis ist nach dem Erhöhen [7 18 43 667]. lisb und lisc sind tiefe Kopien. Danach:
liste_append(&lis, &lisb); // Ausgabe 5
liste_clear(&lis);
lis = liste_plus(&lisc, &lisc); // Ausgabe 6Prüfungsabschluss
Du hast Pointerbewegung und Listen-Trace produziert. Jetzt darfst du den vollständigen Musterweg mit allen geforderten Funktionen vergleichen.
Initialisierung, tiefe Kopie und Zuweisung
void liste_init(liste* lis) {
lis->head = nullptr;
lis->len = 0;
}
void liste_init(liste* lis, const liste* src) {
lis->head = nullptr;
lis->len = 0;
liste_assign(lis, src);
}
void liste_assign(liste* dst, const liste* src) {
liste_clear(dst);
liste_node* sn = src->head;
liste_node* n;
while (sn != nullptr) {
if (dst->head == nullptr)
dst->head = n = new liste_node{sn->ele, nullptr};
else {
n->next = new liste_node{sn->ele, nullptr};
n = n->next;
}
sn = sn->next;
}
dst->len = src->len;
}Löschen, Push und Size
void liste_clear(liste* lis) {
while (lis->head != nullptr) {
liste_node* todel = lis->head;
lis->head = lis->head->next;
delete todel;
}
lis->len = 0;
}
void liste_pushfront(liste* lis, T t) {
lis->len += 1;
lis->head = new liste_node{t, lis->head};
}
void liste_pushback(liste* lis, T t) {
if (lis->head == nullptr) liste_pushfront(lis, t);
else {
lis->len += 1;
liste_node* n = lis->head;
while (n->next != nullptr) n = n->next;
n->next = new liste_node{t, nullptr};
}
}
size_t liste_size(const liste* lis) {
return lis->len;
}Anhängen und Plus
void liste_append(liste* lis, const liste* src) {
if (lis->head == nullptr) {
liste_assign(lis, src);
return;
}
liste_node* tail = lis->head;
while (tail->next != nullptr) tail = tail->next;
for (liste_node* n = src->head; n != nullptr; n = n->next) {
tail->next = new liste_node{n->ele, nullptr};
lis->len += 1;
tail = tail->next;
}
}
liste liste_plus(const liste* src1, const liste* src2) {
liste dst;
liste_init(&dst);
liste_assign(&dst, src1);
liste_append(&dst, src2);
return dst;
}Prüfungssatz: Jeder überschriebene oder gelöschte Zeiger braucht vorher einen weiterhin erreichbaren Weg zur Restliste. Kopieren heißt hier neue Knoten anlegen, nicht nur head teilen.