C++ Klasse geordnete String-Liste
-
Hallo zusammen,
wir haben in unserem Informatik Kurs folgendes Programm geschrieben, bei dem ich nicht so ganz durchsteige. Es fängt schon an bei der if-Bedingung der Einfügen() Funktion, in der ein neues dynamisches Element erzeugt wird, welches dann später wieder ausgegeben wird. Dabei verstehe ich nicht genau, wie bzw unter welchem Namen dieses gespeichert wird, um später wieder darauf zugreifen zu können...wäre sehr dankbar wenn mir da jemand helfen könnte, bin noch Anfänger in der objektorientierten Programmierung.PS: Der Sinn des Programms(Code zeigt nur die Klasse) ist es, eine Liste mit Namen zu erzeugen und diese in geordneter Reihenfolge wieder auszugeben.
Schonmal Danke im Vorraus!
MfG Jan#include <iostream> #include "CElement.h" #include <string.h> using namespace std; CElement::CElement():mName(""), mNextPtr(NULL) {} CElement::CElement(string pName) { mName = pName; mNextPtr = 0; } CElement::CElement() // Destruktor { if (0 != mNextPtr) // nur Löschen wenn Pointer auf ein Objekt zeigt { delete mNextPtr; } } bool CElement::Einfuegen(string pName) { if (mNextPtr == NULL) // Ende erreicht? { mNextPtr = new CElement(pName); // dann anhängen } else if(mNextPtr -> mName > pName) // alpahbetisch an der richtigen Stelle? { // einketten CElement* tmpPtr = new CElement(pName); // Schritt 0 tmpPtr -> mNextPtr = mNextPtr; // Schritt 1 mNextPtr = tmpPtr; // Schritt 2 } else { mNextPtr->Einfuegen(pName); // Falls nicht an der richtigen Stelle, } return true; } void CElement::Traversieren() { if (mName != "") { cout << mName << " "; } if (mNextPtr != NULL) // Nachfolger? { mNextPtr -> Traversieren(); // weiterdelegieren } }
-
Zunächst das offensichtliche: Der Name unter dem das neue Ding erreicht werden kann, ist das was links vom
=
steht. AlsomNextPtr
(Zeile 27) bzw.tmpPtr
(Zeile 33).Aber: Das ist nicht direkt der "Name" des neuen Elements. Nicht in dem Sinne wie das
int i;
einenint
mit Nameni
erzeugt. Denn hier wird mit Pointern gearbeitet, undmNextPtr
bzw.tmpPtr
sind die Namen der Pointer, die auf das neue Element verweisen. Das neue Element selber hat gar keinen eigenen Namen, den du im Programmcode benutzen kannst. Es kann nur über Pointer erreicht werden, die auf das Element verweisen. Es kann viele verschiedene Pointer geben, die auf das gleiche Element verweisen (Passiert hier beispielsweise in Zeile 34, wotmpPtr->mNextPtr
undmNextPtr
auf das gleiche Element zeigen) oder es kann auch überhaupt kein Zeiger darauf zeigen (Das ist aber schlecht, denn dann ist es verloren).So ein Pointer kann auch seinen Wert ändern, das heißt er verweist dann auf etwas anderes. Das wird hier benutzt, um die Listenstruktur zu erzeugen, beispielsweise in Zeile 33 bis 35. Zeile 33 lässt
tmpPtr
auf ein neues Element zeigen. Zeile 34 lässt danntmpPtr->mNextPtr
(das ist dermNextPtr
in dem neuem Element) auf das gleiche Element zeigen wiemNextPtr
(welches aber ein anderes ist als das neue Element). Zeile 35 lässt dannmNextPtr
auf das gleiche zeigen wietmpPtr
, also auf das neue Element. Am Ende zeigen also sowohlmNextPtr
als auchtmpPtr
auf das neue Element, und in dem neuen Element zeigt dessenmNextPtr
auf das, worauf unsermNextPtr
vorher gezeigt hat. DamNextPtr
so viel bedeuten soll, wie was "hinter" uns in der Liste kommt, haben wir also quasi das neue Element hinter uns eingefügt, aber haben dabei dafür gesorgt, dass das, was vorher hinter uns war, nun hinter dem neuen Element ist (weil dessenmNextPtr
nun darauf verweist).Das mag jetzt alles sehr verwirrend klingen, für jemanden, der Pointer nicht gewöhnt ist. Lies die Erklärung bei Bedarf mehrmals langsam durch, am besten auch dein Lehrmaterial. Und mal dir hin, was da vor sich geht! Das ist nicht so schwer, wie man anfangs denkt.
-
#include <string.h>
Wozu? Die .h-Header sind für C (ohne ++) bzw. C-Kompatibilität. (oder wird hier string.h etwa nur für NULL includet?)
NULL
Nutze in modernem Code (seit 2011, was auch schon ein paar Jahre her ist) statt
NULL
bessernullptr
. NULL ist wie die Zahl 0, währendnullptr
der Nullpointer (und nur der Nullpointer!) ist.Ob es so eine gute Idee ist, Listen rekursiv durchzugehen? Gut, tail recursion, aber wer garantiert mir, dass der Stack nicht explodiert?
-
Okay, vielen Dank! @SeppJ
Hat mir bereits sehr weitergeholfen...hat diese Art von "Sortieren und Einfügen" einen bestimmten Namen/Stichwort das ich Nachschlagen kann?MfG,
Jan
-
Hmm. Für immer an der richtigen Stelle einfügen würde ich jetzt unter https://de.wikipedia.org/wiki/Insertionsort nachschlagen. Wobei das genaugenommen schon eine gesamte Liste sortiert. Bei dir ist die Liste aber immer sortiert. Ansonsten würde ich einfach "Sortierte verkettete Liste" oder "sorted/ordered linked list" nachschlagen.
-
Was du hier machst, hat nicht wirklich praktische Bedeutung. Ist eher als eine nicht vollkommen sinnlose Übung zu Zeigern gedacht, und hat vom Vorgehen her eine gewisse Ähnlichkeit mit anderen häufigen Vorgehensweisen. Eine selbstsortierende Datenstruktur würde man gewöhnlich anders organisieren. Kommt sicherlich als eine deiner nächsten Übungen.