Was ist an diesem Code falsch (C)?
Was ist an diesem Code falsch?
Das ist die main-Funktion:
Ich bekomme 42 1 3 4 99 raus, aber es soll so 42 3 4 1 99 aussehen.
was wollen sie eigentlich programmieren?
Ich übe etwas mit doppelt verketteten Listen. Ich spiel damit ein bisschen rum, in dem ich eine Liste von Zahlen erstelle.
aber wieso benutzen sie eigentlich c und nicht c++?
Ich möchte erst c lernen und danach c++ :D
3 Antworten
In deiner append Funktion liegt das Verhalten:
Du hängst immer an das letzte Element was an. Also völlig egal, welchen Knoten du aus deiner Liste der append Funktion gibst: in der while, wird immer bis zum Ende durchgehangelt und dort der neue Knoten angehangen.
Wenn du zwischen drin was einfügen möchtest, dann darfst du dich nicht immer bis ans Ende durchhangeln, sondern musst von dem Knoten, den du rein bekommst das next direkt auf den neuen Knoten stellen (und wenn du nichts verloren haben möchtest, den alten Knoten ins next vom neuen einfügen)
Kannst du mir folgen?
Jein ... die Funktion append finde ich tut das, was der name beschreibt.
Schreib besser eine neue Funktion, die irgendwie 'insert' oder 'insert_after' oder so, die dein gewünschtes Verhalten abbilden soll. Dort kannst du ganz bequem die while weglassen ja, dann sollte es schonmal für den Anfang gehen. Das Problem dann ist aber, dass du alles am Ende der Liste (also nach dem neu eingefügten Knoten) verloren hast. Das solltest du eben bedenken und richtig machen bzw. musst du auch an den Vorgänger denken, weil doppelt verkettet. Grob als Pseudocode zur Idee:
insert_after(vert, val)
new_vert = new() // Speicher allokieren
new_vert.val = val
new_vert.next = vert.next // rest der Liste an neuen Knoten anhängen
vert.next = new_vert // neuen Knoten endgültig einfügen
Das ist die Aufgabenstellung:
Implementieren Sie ein dynamisches Integer-Array mithilfe einer doppelt verketteten Liste.
Schreiben Sie zum Einfügen eine Funktion, die eine Zahl hinten an die Liste anhängt (append) und das neue Element zurückgibt, eine Funktion, die alle Elemente ausgibt (print), sowie zwei Funktionen, die das erste und letzte Element zurückgeben.
Deine append-Funktion geht immer zuerst bis zum letzten Listenelement und hängt dann an. Daran ist nichts falsch. Es scheint aber, dass du außerdem weitere Funktionen haben möchtest, die du noch garnicht definiert hast:
- Anhängen an den Anfang der Liste (oft "prepend" genannt)
- Einfügen nach einem angegebenen Listenelement
- Einfügen vor einem angegebenen Listenelement
prepend und Einfügen sind aber etwas anderes als Anhängen ans Ende einer Liste und müssen deshalb auch extra programmiert werden.
Aber ich hab doch die beiden Funktionen "first" und "last" die wieder an den anfang bzw. ans ende gehen.
Das hilft aber nichts, weil append stur ans Ende geht. Du brauchst zwei Einfügefunktionen: Einfügen vor ausgewähltem Element und Einfügen nach ausgewähltem Element. Diese Funktionen sollten jeweils drei Aufrufargumente haben: Die ganze Liste, die Einfügestelle und das einzufügende Element.
Tut mir leid, dass das nicht einfacher zu haben ist.
Aber was wenn ich die While-Schleife in der append-Funktion lösche?
Keine schlechte Idee. Immerhin würdest du dann an der gewünschten Einfügestelle bleiben.
Allerdings ist Einfügen bei doppelt verketteten Listen etwas anderes als Anhängen: Beim Einfügen musst für das neu angefügte Element "neu" sowohl das Vorgängerelement als auch das Nachfolgerelement in das neu eingefügte Element eintragen. Bisher trägst du in deinem Code nur den Vorgängerknoten ins neue Element ein, was beim Anhängen ans Ende reicht, aber nicht beim Einfügen.
Was könnte ich deiner Meinung nach dann machen? Bin grad bisschen Planlos. :D
Mache dir eine Zeichnung, die zwei aufeinanderfolgende Elemente einer doppelt verketteten Liste mit ihren Verkettungen next und prev zeigt. Wähle das zweite dieser Elemente als Einfügepunkt und füge ein neues Element vor dem Einfügepunkte ein. Du wirst sehen, dass du den prev-Verweis des Einfügepunkts und den next-Verweis des Vorgängerelements des Einfügepunkts auf das neue Element setzen musst. Das neue Element übernimmt den Einfügepunkt als seinen Nachfolger und den Vorgänger des Einfügepunkts als seinen Vorgänger.
Mein Entwurf für das Einfügen vor einem Listenelement ist also:
numberItem *insertBefore(numberItem *insertPt, int value) {
numberItem *neu
= (numberItem*) malloc(sizeof(numberItem));
numberItem *ptr = insertPt;
neu -> value = value;
neu -> next = NULL;
neu -> prev = NULL;
if (insertPt == NULL) { // Sonderfall leere Liste
return neu;
}
// Einfügung vor dem Element, das durch
// insertPt identifiziert wird
if (insertPt -> prev != NULL) {
// Der neue Knoten wird neues erstes Listenelement
neu -> next = insertPt;
insertPt -> prev = new;
neu -> prev = NULL;
} else { // das hier ist wirklich trickreich. Hier hilft nur eine Zeichnung
neu -> prev = insertPt -> prev;
neu -> next = insertPt;
insertPt -> prev -> next = neu;
insertPt -> prev = neu;
}
return neu;
}
Das Einfügen nach einem Listenelement wird durch diese Funktion nicht geleistet und muss extra programmiert werden. Da ist der Sonderfall dann der, dass der Nachfolger des Einfügepunkts nicht existiert.
Ich hoffe mal, dass ich da jetzt keine Fehler gemacht habe. Es ist lange her, dass ich so etwas mit Algol 68 und mit Simula 67 mal programmiert habe.
Ist das die einzige Möglichkeit? Ich finde das ein bisschen zu kompliziert für mich :D (Auch wenn ich mir das später nochmal anschauen bzw. aufzeichnen werde) Ich mein, wenn ich die While-Schleife lösche kommt fast die richtige Lösung raus, außer dass eine Zahl nicht geprintet wird. Trotzdem vielen Dank für deine Hilfe und Bemühung. Ich werd deinen Code auf jeden fall versuchen zu verstehen und benutzen wenn alle Stricke reißen.
Einfügen an einer bestimmten Stelle ist in der Tat so kompliziert.
In der Diskussion zur Antwort von SirNik hast du die Aufgabenstellung mitgeteilt. Du schreibst:
Implementieren Sie ein dynamisches Integer-Array mithilfe einer doppelt verketteten Liste.
Schreiben Sie zum Einfügen eine Funktion, die eine Zahl hinten an die Liste anhängt (append) und das neue Element zurückgibt, eine Funktion, die alle Elemente ausgibt (print), sowie zwei Funktionen, die das erste und letzte Element zurückgeben.
Genau das leistet der Code, den du in deiner Frage gezeigt hast. Dieser Code ist also eine fehlerfreie Lösung der gestellten Aufgabe. Du hast hier keinen Programmierfehler, sondern ein kleines Verständnisproblem: Offensichtlich stellst du dir vor, dass ein Aufruf von first (und ebenso ein Aufruf von last) auf einen nachfolgenden Aufruf von append einwirkt. Du denkts also, dass du durch die Kombination von first (bzw. lst) mit append die Einfügestelle wählen kannst. Das ist aber nicht der Fall und das ist auch in der Aufgabe nicht verlangt.
Das Einfügen an einer vorher gewählten Stelle ist in der Aufgabe nicht verlangt. Insofern kannst du meinen Lösungsvorschlag für das Einfügen vergessen oder für die nächste Aufgabe aufheben, die ja wohl sicher kommen wird.
Aber wie soll ich die Aufgabe dann lösen oder ist das so nicht möglich?
Du beziehst dich auf
aber es soll so 42 3 4 1 99 aussehen.
in deiner Frage. Wenn in der Aufgabe steht, dass die Zahlenwerte in dieser Folge in der Liste stehen und von print so ausgegeben werden sollen, dann müssen sie auch in dieser Folge mit append in die Liste eingetragen werden.
Ja also ist die Aufgabe nicht möglich. Weil laut Aufgabe werden die Zahlen ja anders eingegeben. Und ich soll nur die Funktionen benutzen die es in der Aufgabe gibt.
Den vollständigen Aufgabentext kenne ich nicht, was du mitgeteilt hast, ist nur der Arbeitsauftrag für die Programmierung, aber nicht der Arbeitsauftrag für den Programmtest. Trotzdem habe ich ein wenig den Eindruck, dass die Person, die die Aufgabe gestellt hat, vielleicht an ihrer Formulierungskompetenz arbeiten sollte. In der Informatik geht es um äußerste Genauigkeit des Ausdrucks - und zwar sowohl beim Programmieren als auch bei der Kommunikation mit Kollegen.
Hast du vielleicht die Bedingung
insertPt -> prev != NULL
verkehrt herum bzw. die Blöcke vertauscht?
Tatsächlich! Die Bedingung muss natürlich heißen
insertPt -> prev == NULL
Besten Dank für diesen Hinweis, der natürlich auch dem Fragesteller nützen wird.
Es funktioniert noch nach Jahrzehnten C-Abstinenz - wenn ich malloc() sehe, suche ich automatisch nach dem zugehörigen free(). Wenn das der vollständige Code ist, ist das schon mal der erste Fehler.
Das Aufräumen gehört in diesem Fall ans Ende der main()-Funktion, wo wenigstens ein Element der Liste noch bekannt ist.
(Zwar spielt dies bei einem Übungsprogramm, das praktisch sofort wieder geschlossen wird, für die Funktionalität praktisch keine Rolle, aber bei Übungsprogrammen ist es umso wichtiger, dass man sich angewöhnt, NIEMALS ein malloc() zu schreiben ohne zeitgleich das zugehörige free() zu schreiben - und sicherzustellen, dass es UNTER ALLEN UMSTÄNDEN (außer Totalcrash) auch aufgerufen wird. Es gibt schon mehr als genug Memory Leaks in freier Wildbahn.)
Kein wirklicher Fehler, aber etwas, wovon ich mir angewöhnt habe, es als schlechten Stil zu empfinden: Funktionsparameter werden innerhalb der Funktion neu zugewiesen. Wenn man sicher ist, niemals Programmiersprachen zu verwenden, die diese Änderungen an den Aufrufer zurückzugeben, ist das ok. Aber nur dann. (Ich verwende u. A. VBA, wo sich geänderte Funktionsparameter auf den Aufrufer auswirken, es sei denn, man verbietet es ausdrücklich.)
Ebenfalls kein wirklicher Fehler, aber schlechter Stil: die while-Schleife, die ans Ende der Liste führt, kommt mehrfach in exakt gleicher Form vor. Besser wäre, nur die Funktion last() beizubehalten und die übrigen Schleifen durch
item = last(item);
zu ersetzen.
Eine weitere Stilfrage: ich würde print() als erstes first() aufrufen lassen, damit in jedem Fall die komplette Liste ausgegeben wird. (Die Funktion hier würde ich z. B. printFrom() nennen.)
Wenn wirklich nur angehängt werden soll, sind die Aufrufe
item = first(item);
und
item = last(item);
überflüssig.
Vermutlich liegt hier aber ein weiterer Fehler: es soll in die Mitte eingefügt oder am Anfang vorangestellt werden, hier wird aber lediglich ans Ende angehängt.
Dafür brauchst du entweder zwei Funktionen
insertBefore(numberItem* item, int value)
insertAfter(numberItem* item, int value)
oder zwei Funktionen
insertBefore(numberItem* item, int value)
append(numberItem* item, int value)
oder eine ähnliche Kombination.
Oder du setzt an den Anfang der Liste ein Dummy-Element, das niemals mit ausgegeben wird und dessen next-Element nur bei Einfügen oder Löschen am Anfang der Liste geändert wird. Könnte sogar die eleganteste Lösung sein, in C eine Variable zu emulieren, die für die Liste selbst (anstatt für ein einzelnes Element der Liste) steht.
Ja ich konnte dir fast zum Schluss folgen. Also sollte ich die While-Schleife am besten löschen oder?