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
    
    	}
    }
    

  • Mod

    Zunächst das offensichtliche: Der Name unter dem das neue Ding erreicht werden kann, ist das was links vom = steht. Also mNextPtr (Zeile 27) bzw. tmpPtr (Zeile 33).

    Aber: Das ist nicht direkt der "Name" des neuen Elements. Nicht in dem Sinne wie das int i; einen int mit Namen i erzeugt. Denn hier wird mit Pointern gearbeitet, und mNextPtr 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, wo tmpPtr->mNextPtr und mNextPtr 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 dann tmpPtr->mNextPtr (das ist der mNextPtr in dem neuem Element) auf das gleiche Element zeigen wie mNextPtr (welches aber ein anderes ist als das neue Element). Zeile 35 lässt dann mNextPtr auf das gleiche zeigen wie tmpPtr, also auf das neue Element. Am Ende zeigen also sowohl mNextPtr als auch tmpPtr auf das neue Element, und in dem neuen Element zeigt dessen mNextPtr auf das, worauf unser mNextPtr vorher gezeigt hat. Da mNextPtr 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 dessen mNextPtr 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 besser nullptr. NULL ist wie die Zahl 0, während nullptr 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.


  • Mod

    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.


Anmelden zum Antworten