C++

Verkettete Listen

LinkedIn Learning kostenlos und unverbindlich testen!

Jetzt testen Alle Abonnements anzeigen
Da während der Programmierung nicht immer klar ist, wie viele Eingaben ein User machen wird, haben Sie die Möglichkeit, verkettete Listen anzulegen, die dynamisch mit den Bedürfnissen wachsen. Lernen Sie in diesem Film, wie das funktioniert.

Transkript

Ganz wichtig bei der Programmierung sind sogenannte verkettete Listen, und ich zeige Ihnen, wie man so eine verkettete Liste aufbaut. Zunächts mal definiert man hier eine Datenstruktur, das ist noch ganz normal, ich habe die mal links Struktur genannt, genannt, ich habe hier den eigentlichen Datensatz, nämlich int (Integer), unten Pointer auf einen string (String), das habe ich hier definiert. Ich möchte als einen String dadrin speichern und nenne Integer-Wert. Was bedeutet "verkettete Liste"? "verkettete Liste" bedeutet dieser Teil, dass die Liste hier drin einen Pointer hat, *next ist ein Pointer, der wieder auf die gleiche Liste zeigt, nämlich hier deshalb link_str, link_str. Er hat sowas bisschen, was von Rekursivität. Es ist aber nicht, ist etwas Anderes. Ich kann nämlich auf die Art und Weise eine dynamische Liste aufbauen, also mehrere solche Elemente, die über diese Pointer miteinander veknüpft sind. Und wenn ich den Pointern entlang lauf, na her, kann ich auf die Inhalte der Elemente zugreifen. Der Vorteil ist es eine dynamische Liste, die man nachher aufeinander aufbauen kann. Bei einem Array muss hier das gesamte Array zum Beispiel mit dem malloc festlegen oder per Definition gleich am Anfang festlegen. Hier kann ich das dynamisch machen. ich kann hier ganz komplizierte Strukturen aufbauen mit mehreren solchen Pointern. Also, das ist auf jeden Fall mal hier die Deklaration von unserem struct link_str, und jetzt definiere ich mir hier mal zwei Pointer - einen Startpointer pstart, das soll auf die Linkstruktur zeigen, und ich brauche irgendeinen Pointer, mit dem ich in der Liste herumlaufen kann, das nenne ich pliste. Hier Startpointer sollte dann immer auf Anfang zeigen, sonst bewege das ich weg, ist das Ganze verloren, ich komme auf die Element nie wieder ran. Und hier haben wir noch einen Arbeitstring, s1 für die Angabe. Jetzt kommen wir zur Schleife, jetzt können natürlich die Werte einlesen. Als Erstes ich mache mit getline mal einen Input auf s1, das s1 wird dadurch definiert, und ich haben jetzt mal den Wert, den ich anlesen möchte. Jetzt gibt es hier den ersten Sonderfall, wenn pstart nämlich NULL ist, dann muss ich erst mal die Datenstruktur allozieren. Mit malloc (sizeof (link_str)) reserviere ich genauso viel Elemente, wie dieser Datenblock groß ist, besteht aus einem Integer, einem Pointer und noch mal einem Pointer. Und hier muss ich Kasten machen, damit kein Fehler kommt. Dann kann ich den Begriff definieren. Das ist auch eine dynamische Struktur. Der String, hier mit new string (s1) definiere ich den gleich, und wird hier gleich kopiert und da reingesetzt. Das macht der new string von s1 automatisch, das ist ganz praktisch, kann man durch andere Varianten nehmen, für C-Strings ist das ein bisschen aufwendiger. Das ist eigentlich sehr elegant. Wenn ich hier einen bloßen Integer habe in Anführungzeichen, dann kann ich hier sowas machen i++, hier starte ich mit NULL und dann weise ich das einfach zu. Und die next Variable, der Pointer next, den muss ich natürlich auch definieren, und zwar auf NULL, weil das Ende der Liste erreicht. Dass wenn ich das vergesse, habe ich ein Problem, dann läuft es unter Umständen gleich eine Schutzverletzung, wenn ich hier der Kette entlang laufe. Jetzt kann ich die pliste auch definieren, nämlich mal auf das erste Element. Jetzt laufe in die Schleife rum while (s1 != "ENDE"), dann gehe ich hier wieder hin, jetzt ist der pstart aber nicht mehr NULL, wenn Speicher da war, sonst natürlich nicht. Fehlerfall, es ist was Anderes. Also, laufe ich nochmalerweise in else rein, und kann jetzt pliste, zeigt die auf den Anfang, next wieder eine entsprechende Datenstruktur zuweisen, also allozieren, dann schalte ich die Liste weiter. Jetzt ist next von dem vorhergehenden Wert definiert, von dem Start. Dann schalte ich einfach weiter, zeige also auf das neue Element. Bevor habe ich erst mal das all den next definiert, ganz tricke ich diese Struktur. Und pliste-Begriff kann ich wieder, wie gewohnt, den String zuweisen. Ich kann die mal 1 zuweisen und next wieder auf NULL setzen, Das ist eigentlich das Gleiche, wie ich hier oben auch gemacht habe. Kann man auch anders schreiben. Mit dem Start habe ich immer gerne eine eigene Initialisierungsroutine für das erste Mal. Das andere arbeitet aber jetzt mit dem hier oft in der Schleife. Wenn ich fertig bin, will ich das Ganze natürlich nochmal ausgeben, weise also pliste hier auf den start-Wert, dann fange ich wieder von vorne an, solange pliste ungleich NULL ist, gebe ich jetzt mal die eins aus. und dann mit * Klammer auf pliste pbegriff,, weil das ist ein Pointer auf dem String, gebe ich mir den String als Nächstes praktisch aus. Und dann kann ich die Liste fortschalten. Das mache ich solange, bis pliste hier oben mit NULL das Ende der Liste anzeigt. Und Freigeben darf man nicht vergessen, sonst bleibt ein Müll im Speicher, zumindest wenn man es im Unterprogramm verwendet. Im Hauptprogramm ist es nicht so dramatisch, sollte man aber immer machen. pliste ist gleich start, wieder den Zeiger zurück auf den Anfang, solange ungleich NULL, das ist der gleiche Mechanismus, den ich hier oben habe, aber ein bisschen anders wird es. Ich definiere jetzt gleich mal start auf pliste, weil wir wollen die Liste ja nacheinander weglöschen. pliste - pliste - next schalte ich sofort weiter. Ich muss nämlich die Nachfolge merken, wenn ich jetzt die Liste lösche, habe ich eine Nachfolge nicht mehr. Ich lösche erst mal den String, solange pstart noch definiert ist, und mit free (pstart) gebe ich auch den Speicher für pstart frei, also die aktuelle Liste, danach darf ich nicht mehr drauf zugreifen. Ich gehe aber in die Schleife weiter. pliste ist hier definiert, könnte schon NULL sein, wenn es Ende erreicht es, wenn nicht, kann ich hier solange weiter machen, bis NULL erreicht ist. Und am Schluss setze ich alles auf NULL. Damit ist der Speicher freigegeben, und jetzt starten wir das Ganze mal, ich will aber jetzt hier ohne Debug eigentlich starten, so. Und schauen uns mal an, wie das funktioniert. erstes lement tippe ich ein, noch eines nicht eines egal, und hier ENDE. Und jetzt geht es hier los. Das erste element, habe ich mir auch ein bisschen vertippt, ist 0, nicht eines ist 1, und ENDE ist 2. Das ist eines, was da immer hochgezählt wurde. Damit habe ich die verkettete Struktur eigentlich schon verwendet. Sie können hier gerne mal das Ganze ein bisschen erweitern, hier die Datenstruktur nochmal Element reinschreiben, das Element wieder initialisieren und wieder ausgeben, damit Sie ein bisschen Gefühl bekommen für diese verketteten Datenstrukturen.

C++

Machen Sie sich mit den einfachen Grundlagen zu C++ vertraut und lernen Sie anhand zahlreicher Übungs- und Codebeispiele die Klassenkonzepte, Prozeduren und Funktionen kennen.

9 Std. 3 min (143 Videos)
Derzeit sind keine Feedbacks vorhanden...

Video-Training auf DVD mit Bonusmagazin

+ Tutorial to go: Mit Videos für iPod, iPhone & Co.

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!