Unsere Datenschutzrichtlinie wird in Kürze aktualisiert. Bitte sehen Sie sich die Vorschau an.

C++

Baumstrukturen

Testen Sie unsere 2016 Kurse

10 Tage kostenlos!

Jetzt testen Alle Abonnements anzeigen
Lernen Sie anhand dieses Beispiels, wie einfach es ist, eine sortierte Liste als Baumstruktur abzubilden. Der Trainer erklärt ausführlich die einzelnen Schritte dieser Routine und gibt weiterführende Tipps zu diesem Thema.

Transkript

Jetzt wird es ein bisschen komplizierter. Neben der verketteten Liste gibt es natürlich auch unterschiedliche andere Datenstrukturen, zum Beispiel Baumstrukturen, das möchte ich jetzt Ihnen mal zeigen. Hier mal zur Erinnerung, wie eine verkettete Liste aussieht. Ich habe hier eineb Begriff, und hier mit einem next. Also, hier gibt es immer einen Pointer, der zeigt mir hier auf das nächste Objekt, und hier kann ich diese Liste durchlaufen. Das ist eine lineare Liste, ist ja ganz schön, aber man kann das auch noch eleganter machen, kann man hier das nächste Beispiel rein. Man kann zum Beispiel Rückwertspointer definieren. Das ist die erste Variante, die man damit machen kann, also einen Pointer, der zunächst ein Element zeigt, ein Pointer, der aus vorhergehendem Element zeigt. Ich habe hier wieder mein Start, hier wird nach vorne gezeigt, und hier definiere ich einen Pointer, der zurückzeigt, und hier wieder einen nach vorne und der ein zurück. Der Vorteil ist, dass ich könnte mir das Ende zum Beispiel merken, und kann dann rückwärts durchlaufen durch die Liste, und hier kann ich schön nach vorne laufen. Ich kann also hin un her laufen, während ich bei der linearen Liste, wenn ich mal hier hinten bin mit meinem Pointer und ich was vorne suchen will, eigentlich von vorne anfangen muss und wieder durchlaufen Das geht hier jetzt hin und her. Das ist also eine Variante, also eine zweiseitig verknüpfte Liste. Und gehe ich jetzt mal weiter. Jetzt komme ich zu Baumstrukturen. Da möchte ich Ihnen auch ein Programmbeispiel zeigen. Die Baumstruktur hat auch zwei Pointer, und zwar ein, der auf das linke Element, und ein, der auf das rechte Element zeigt. Wann das links und wann das rechts geht, es ist abhängig von den Datenstrukturen, könnte jetzt hier so machen, wie es jetzt mal lexikographische Sortierung zum Beispiel. Also, wenn ich den Begriff "Adam" habe, dann ist er vor "Kurs", also lege ich ihn hier hin. Wenn dan ein CPP kommt, ist es wieder vor "Kurs", aber hinter "Adam", also das muss ich dann hier einsortieren, und hier ein Windows wäre dann nach K einzusortieren. Das ist eine Baumstruktur, binärer Baum, der jetzt nicht optimiert sortiert ist. Da gibt es natürlich tausend Strategien und na her auch wie die Bibliotheken, die dabei helfen. So einen Teil selber aufzubauen ist hier nicht ganz einfach, aber wir machen das jetzt hier mal nach diesem Schema her. Das ist nämlich gar nicht so kompliziert, wie es eigentlich aussieht. Algorithmisch gesehen geht das relativ leicht, und ich zeige Ihnen mal hier das fertige Programm. Hier habe ich erst mal meine Datenstruktur definiert. struct links_str Bergriff, hier mal null begriff ohne dem i1 einen linksseitigen und einen rechtsseitigen Pointer - left und right. Das ist schon alles. Jetzt wird es ein bisschen kompliziert, da wird ich in Datenwert eindrangen. Ich definiere gleich mal die Funktion. Die soll hier auf den Pointer eines Pointers zeigen, wenn ich muss den Pointer auch noch verändern können. Deshalb brauche ich zwei Sterne und den String, den ich dahin kopieren möchte. Jetzt definiere ich mir hier nochmal diese Variable pliste, mit der ich dadurch laufen kann. Und die setzt sich einfach mal auf den Startwert. Es ist dann *pstart. Start, wie gesagt, muss ich hierher auch noch entsprechend modifizieren unter Umständen So, pliste ist Null, es ist der Anfang, dann alloziere ich nämlich jetzt einfach mal, die Struktur, wie früher kopiere ich mit dem Datenwert, und links und rechts sind NULL, und hier brauche ich jetzt die Zuweisung auf die pstart pliste, weil sonst zeigt diese Liste nämlich gar nichts. Damit habe ich jetzt den anfang der Liste definiert und meinen Startwert natürlich auf die Art und Weise auch. Jetzt wird es so ein bisschen komplizierter. wenn die Liste nämlich nicht NULL ist, dann habe ich da schon die Elemente, und jetzt muss ich suchen nach einem leeren Eintrag abhängig davon, ob er links oder rechts liegen soll. Das mache ich hier mit einem String Vergleich, lexikographische Ordnung. Wenn s1 kleiner gleich ist als der Begriff, der schon in der Liste steht, gehe ich nach links und sonst nach rechts, und da muss ich jetzt hier mal gucken, wenn die linke Liste ungleich Null ist, dann muss ich einfach weiter schalten. Ist die linke Liste aber gleich NULL, bin ich am Ende angekommen und kann mir hier, schiebe das ein bisschen drüber, die neue Datenstruktur definieren, das alles festlegen, links und rechts Null setzen und pliste auf Null setzen, und die Schleife ist nämlich dazu Ende. Sonst wenn ich auf Größe sortiere, mache ich eigentlich genauso weit, ich gehe auf die rechte Seite. Wenn die ungleich NULL ist, mache ich weiter, in der Schleife kommt dann das nächste Element dran, solange bis ich das Ende dieser Liste erreicht habe, des Baums eigentlich genau genommen. Und hier, wenn ich am Ende anbinde, und das immer noch rechts ist, dann lege ich hier entsprechend mit malloc den Wert. Ich habe das Wechsel zwischen links und rechts hin und her, solange bis ein freier Eintrag gefunden wird, dann wird es hier entsprechend definiert. Damit bin ich fertig. Ausgeben ist sehr raffiniert, und sehr einfach machen wir mit einer Rekursion. Wie bei der Fakultät mal gelernt, wenn die plist NULL ist, dann ist es fertig, weil es gibt nichts zu holen. Sonsten gebe ich einfach die linke Seite der Liste aus, und danach die rechte Seite der Liste. Das ist die Rekursion, ausgabe wird hier einfach doppelt aufgerufen. Aber damit das da passiert, muss ich hier natürlich auch noch den Wert eingeben cout "Sortiert", nehme ich *pbegriff ende. Damit gebe ich den Wert aus, das tricke ich es, dass ich jetzt eine alphabetisch sortierte Liste bekomme, wenn ich auf die Art und Weise rekursiv durchlaufe. Und nicht vergessen genauso, rekursiv muss ich das ganze Ding noch freigeben, nehme ich hier, wenn gleich NULL ist fertig, ansonst gebe ich links frei und dann rechts frei, und dann gebe ich den Begriff frei, nämlich den eigentlichen Kern, vorher gebe ich die Unterelemente, die im Baum hängen, also die Unterbäume eigentlich frei, und dann die Liste selber, das Ganze läuft rekursiv,ist schon kompakt. Und das Hauptprogramm sieht genauso einfach aus. Hier mache ich erst mal eine Schleife bis "QUIT" kommt, trage ich einfach die Werte ein außer QUIT selber und da gebe ich ausgabe an zu ausgebender Liste und freigeben. Und das Ganze gucken wir uns jetzt mal an, indem ich das starte ohne Debug. Jetzt kann ich hier irgendwelche Begriffe eingeben abc am anfang so, das steht sicher in der Vorne, ende auch gut, es ist jetzt ganz egal, was ich hier eingebe, hans maier begin. Ich mache mal ein bisschen eine Mischung in den Buchstaben. wurst und am Schluss dann QUIT. So, jetzt schauen mal! abc am anfang, b, e, h, m, w funktioniert wunderbar. Da können Sie gerne mal herum experimentieren. Das ist eine ganz hübsche Übung, an diesen Baumstrukturen da umzubauen.

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!