Probleme mit verketteter Liste



  • Hallo zusammen!

    Ich beschäftige mich grad mit verketteten Listen und habe hier einen Code aus meinem Script mit dem ich nicht ganz klar komme. Habe mir das was passiert nun schon drei mal aufgezeichnet - verstehe den Vorgang aber immer noch nicht ganz.

    Könnt ihr euch mal anschauen, ob der Code eurer Ansicht nach so funktioniert? Ich verstehe z.B. nicht wo das p in dr letzten Zeile der Funktion sortiertEinfuegen herkommt. Das wird doch nur in der Funktion voidausgeben verwendet...wie also kann das hier verwendet weren?!(Zeile 43)

    Und in Zeile 4 und 27 wird doch eine Zeigervariable vom Typ Element (das ist ein struct) definiert ... warum steht hier nochmal "struct" davor? Das ist doch unnötig oder?

    [code]
    
    <main.cpp>
    struct Element *anfang; // globaler Zeiger auf Anfang der Liste
    void ausgeben()
    { // ausgeben von Anfang bis Ende
    	Element * p = anfang; // p zeigt auf aktuellen Knoten
    	cout << "Liste: ";
    	while (p != NULL) {
    		cout << p->mData << " "; // Infoteil des aktuellen Knotten ausgeben
    		p = p->mNextPtr; // p auf Folgeelement setzen
    	}
    	cout << endl;
    }
    
    void sortiertEinfuegen(int x)
    { // aufsteigend sortiert einfuegen
    	Element *ptr = new Element; // erzeuge neues Element
    	ptr->mData = x; // mData wird x
    	ptr->mNextPtr = NULL; // next-Wert wird initialisiert mit NULL
    	if (anfang == NULL)
    	{ // Leere Liste
    		anfang = ptr;
    	}
    	else
    	{ // Liste nicht leer
    		struct Element *ptr1;
    		ptr1 = anfang;
    		if (x < anfang->mData) { // x wird erstes Element da kleiner
    			ptr->mNextPtr = anfang; // bisheriger Anfang wird eingehängt
    			anfang = p; // neues Element am Anfang
    		}
    		else
    		{
    			while (ptr1->mNextPtr != NULL) // suche Einfuegestelle p1
    			if (ptr1->mNextPtr->mData < x)
    			{
    				ptr1 = ptr1->mNextPtr; //hier
    			}
    			else
    				break;
    			ptr->mNextPtr = ptr1->mNextPtr; // jetzt an der richtigen Stelle, p verketten
    			ptr1->mNextPtr = p; // verketten Vorgaenger
    		}
    	}
    }
    <main.cpp>
    int main()
    {
    	anfang = NULL; // Leere Liste
    	int eingabe;
    	while (true) {
    		cout << "Integer (Abbruch mit negativem Wert): ";
    		cin >> eingabe;
    		if (eingabe<0) break; // Beende Eingabeaufforderung
    		sortiertEinfuegen(eingabe);
    	}
    	ausgeben();
    	return(0);
    }
    


  • Sorry hab das struct vergessen:

    <verketteListe.h>
    struct Element
    {
    	int mData; 
            Element * mNextPtr;
    };
    


  • RalfZ schrieb:

    Ich verstehe z.B. nicht wo das p in dr letzten Zeile der Funktion sortiertEinfuegen herkommt.

    Was sagt denn der Compiler dazu?

    RalfZ schrieb:

    Und in Zeile 4 und 27 wird doch eine Zeigervariable vom Typ Element (das ist ein struct) definiert ... warum steht hier nochmal "struct" davor? Das ist doch unnötig oder?

    Richtig!
    Vielleicht wurde der Code schon vor 30 Jahren in einer C-Vorlesung verwendet, da braucht man das struct.



  • RalfZ schrieb:

    Hallo zusammen!
    Könnt ihr euch mal anschauen, ob der Code eurer Ansicht nach so funktioniert? Ich verstehe z.B. nicht wo das p in dr letzten Zeile der Funktion sortiertEinfuegen herkommt.

    Das p kommt von nirgendwo. Das wird daher entweder so nicht funktionieren oder du hast nicht den gesamten Code gezeigt (die #includes fehlen beispielsweise auch).

    Und in Zeile 4 und 27 wird doch eine Zeigervariable vom Typ Element (das ist ein struct) definiert ... warum steht hier nochmal "struct" davor? Das ist doch unnötig oder?

    Vermutlich weil das von einem C-Entwickler geschrieben wurde, der aus C++ nur "cout" verwendet und sonst nichts. Auch das "NULL" sollte in C++ nicht vorkommen und durch "nullptr" ersetzt sein.

    Ansonsten sieht das sortiertEinfuegen doch viel zu kompliziert aus. Habs jetzt nicht ganz durchgelesen, aber ich wette, dass das viel kürzer geht.



  • Hallo,

    danke für die Antworten. Ja das p scheint mir auch von nirgendwo zu kommen. Im Script wird nur das <verketteteListe.h> in der main includiert...das hab ich vergessen... ansonsten gibts keine includierungen. Ich vermute dass das p ein Schrfeibfehler ist... nachdem ich nun aber versucht habe den Code nachzuvollziehen, indem ich das p durch ptr oder ptr1 ersetzt habe komme ich immernoch auf keine Lösung.

    Das "struct" in Zeile 4 und 27 hab ich weggelassen... das funktioniert.

    Ich finde diesen Code extrem kompliziert. Was sagt Ihr... gibts da ne andere Variante?

    Noch ne andere Frage - ich verstehe das Prinzip der verketteten Liste immer noch nicht: Werden meine Objekte im Speicher nun sortiert nach "Wert"(z.B. in diesem Fall nach mData) z.b. aufsteigend? Also hab ich z.B. auf Speicherstelle 1000 das struct mit dem Wert 3, auf 1001 das struct mit dem Wert 4 und auf 1002 das struct mit dem Wert 5?
    Oder sind meine structs Kreuz und Quer im Heap(dynamische Var) verteilt und die "Sortierung" ist eigentlich nur im Sinne der " mNextPtr " - Zeiger vorhanden?

    Also z.B. mein struct mit der 3 liegt auf Speicherstelle 500, mein struct mit Wert 4 auf Speicherstelle 12777 und mein struct mit der 5 auf Speicherstelle 2145... ?



  • RalfZ schrieb:

    Ich vermute dass das p ein Schrfeibfehler ist...

    Ja, denke ich auch.

    Ich finde diesen Code extrem kompliziert. Was sagt Ihr... gibts da ne andere Variante?

    s.u.

    Noch ne andere Frage - ich verstehe das Prinzip der verketteten Liste immer noch nicht: Werden meine Objekte im Speicher nun sortiert nach "Wert"(z.B. in diesem Fall nach mData) z.b. aufsteigend? Also hab ich z.B. auf Speicherstelle 1000 das struct mit dem Wert 3, auf 1001 das struct mit dem Wert 4 und auf 1002 das struct mit dem Wert 5?
    Oder sind meine structs Kreuz und Quer im Heap(dynamische Var) verteilt und die "Sortierung" ist eigentlich nur im Sinne der " mNextPtr " - Zeiger vorhanden?

    Also z.B. mein struct mit der 3 liegt auf Speicherstelle 500, mein struct mit Wert 4 auf Speicherstelle 12777 und mein struct mit der 5 auf Speicherstelle 2145... ?

    Letzteres. Wo die Objekte wirklich im Speicher liegen, bestimmt das "new". Das entscheidet nach Gutdünken (bzw. je nach Allocator). Und das new wird ja gemacht, bevor du sortierst. Das ist übrigens auch der riesengroße Nachteil verketteter Listen: die Daten liegen wild verteilt im Speicher rum, was den Zugriff langsam machst. Wenn du willst, dass die Daten hintereinander liegen, dann musst du ein C-Array, ein std::array oder einen std::vector nehmen. Dann kannst du aber nicht mehr mitten in der Liste etwas einfügen bzw. wenn du auf Speicherstelle 42 die 3, auf Stelle 43 die 5 und auf Stelle 44 die 6 gespeichert hast und nun eine 4 einfügen willst, musst du erst Platz machen und die nachfolgenden Elemente verschieben.

    Als lauffähigen Ersatz habe ich deinen Code mal schnell umgeschrieben.

    Wichtig: Es gibt KEINE globale Variable mehr, sondern stattdessen wird einfach der Listenkopf als Parameter übergeben. Globale Variablen machen das Programm kompliziert, weil die unsichtbare Abhängigkeiten reinbringen, die man nicht so direkt sieht. Außerdem kannst du in deiner ursprünglichen Version nicht 2 unterschiedliche Listen haben, da die alle von dem globalen Anfang abhingen.

    Auch noch wichtig:
    - du könntest jetzt hieraus eine Klasse "Liste" machen
    - es wird hier immer noch kein Speicher freigegeben, du hast also einen Leck (wirst du sicher noch was zu lernen)
    - aber es funktioniert und ich hoffe, du verstehst hier besser, wie das Einfügen geht

    #include <iostream>
    #include <random>
    
    using namespace std;
    
    struct Element { 
        int mData; 
        Element* mNextPtr; 
    };
    
    // ausgeben von Anfang bis Ende 
    void ausgeben(const Element *kopf) { 
        cout << "Liste: "; 
        while (kopf) { 
            cout << kopf->mData << " ";
            kopf = kopf->mNextPtr;
        } 
        cout << endl; 
    } 
    
    // aufsteigend sortiert einfuegen 
    void sortiertEinfuegen(Element* &kopf, int x) { 
        Element *neu = new Element;
        neu->mData = x; 
        // muss das Element ganz vorn eingefügt werden?
        if (!kopf || x <= kopf->mData) { 
            neu->mNextPtr = kopf;
            kopf = neu;
            return;
        } 
        auto prev = kopf;
        auto dieses = kopf->mNextPtr;
        while (dieses && x > dieses->mData) {
            prev = dieses;
            dieses = dieses->mNextPtr;
        }
        neu->mNextPtr = dieses;
        prev->mNextPtr = neu;
    } 
    
    int main() { 
        Element *kopf = nullptr;
        sortiertEinfuegen(kopf, 30);
        sortiertEinfuegen(kopf, 40);
        ausgeben(kopf);
        sortiertEinfuegen(kopf, 60);
        sortiertEinfuegen(kopf, 50);
        ausgeben(kopf); 
    
        std::random_device rd;
        for (int i = 0; i < 15; ++i) {
            std::uniform_int_distribution<int> d(0,100);
            sortiertEinfuegen(kopf, d(rd)); 
        } 
        ausgeben(kopf);
    }
    


  • Hallo wob, vielen Dank für deinen Beitrag. Ich werde deinen code gleich mal ausprobieren (wollte das ganze eh auch noch als Klasse programmieren). Das hilft mir auf jeden Fall weiter 😉

    Derweil hab ich auch den Fehler im Code meines Profs gefunden... das p soll einfach ptr heissen ... also die korrigierte und funktionierende Version seht ihr unten. Ein Problemchen macht das Prog allerdings... nach 10 bis 20 eingegebenen Zahlen bleibt das Programm stehn ... hat jemand eine Idee an was das liegen kann. Es kommt kein Fehler...habe das Gefühl dass es in irgendner Schleife stecken bleibt...

    <CsElement.h>
    
    struct sElement
    {
    	int mData;
    	sElement * mnextptr;
    };
    
    <main.cpp>
    
    #include <iostream>
    #include "CsElement.h"
    using namespace std;
    
    sElement *anfang;
    
    void sortierteinfuegen(int x);
    
    void ausgeben();
    
    int main()
    {
    
    	anfang = 0;
    
    	int eingabe;
    	cout << "Dateneingabe, ende mit neg wert: "<<endl;
    	while (true)
    	{
    		cin >> eingabe;
    		if (eingabe < 0)
    			break;
    		sortierteinfuegen(eingabe);
    	};
    
    	ausgeben();
    
    	system("Pause");
    	return 0;
    };
    
    void sortierteinfuegen(int x)
    {
    	cout << "Einfuegefunktion gestartet ... " <<x<<endl;
    	sElement *ptr = new sElement;
    	ptr->mData = x;
    	ptr->mnextptr = 0;
    
    	if (anfang == 0)        //prüfe ob min ein objekt in liste
    	{
    		anfang = ptr;  //nein
    	}
    	else                //ja ...
    	{
    		sElement * ptr1 = anfang;   //Pointervariable ptr1...Sicherung von Anfang
    		if (x < anfang->mData)  //neues Element kleiner als erstes Element?
    		{
    			anfang = ptr;
    			ptr->mnextptr = ptr1; 
    		}
    		else   //neues Element ist größer als erstes
    		{
    			while (ptr1->mnextptr != 0)
    			{
    				if (x>ptr1->mnextptr->mData)
    					ptr1 = ptr1->mnextptr;
    			};
    
    			ptr->mnextptr = ptr1->mnextptr;
    			ptr1->mnextptr = ptr;
    		}
    	}
    }
    
    void ausgeben()
    {
    	sElement *p = anfang;
    	cout << "Liste: ";
    	while (p != 0)
    	{
    		cout << p->mData << " ";
    		p = p->mnextptr;
    	}
    	cout << endl;
    }
    


  • Ahoi!

    Ich hätte da auch nochmal ne Frage zu der Parameterübergabe an die Funktion sortiertEinfuegen (also bei wobs code). Der Code funktioniert bei mir auch ..und das mesite ist mir auch klar.

    Was ich noch nicht ganz verstehe... was für eine Art von Übergabe hat der erste Parameter ...

    Also Funktion:

    void sortiertEinfuegen(Element* &kopf, int x) 
        {
    	Element *neu = new Element;
    	neu->mData = x;
    	// muss das Element ganz vorn eingefügt werden?
    	if (!kopf || x <= kopf->mData) {
    		neu->mNextPtr = kopf;
    		kopf = neu;
    		return;
    	}
    	auto prev = kopf;
    	auto dieses = kopf->mNextPtr;
    	while (dieses && x > dieses->mData) {
    		prev = dieses;
    		dieses = dieses->mNextPtr;
    	}
    	neu->mNextPtr = dieses;
    	prev->mNextPtr = neu;
    }
    

    Und der Aufruf in der main:

    Element *kopf = nullptr;    //Zeigervar Typ Element auf 0;
    sortiertEinfuegen(kopf, 30);
    

    ich check nicht ganz warum hier der erste Parameter " Element* &kopf " ist... Also ich kenne call-by-reference ... also das man einen Pointer übergibt(z.B. berechneDurchmesser(int * radius) ) oder auch den Referenzparameter (z.B. berechneDurchmesser(int &radius) ) Diese Kombination verwirrt mich etwas ... was geschieht hier?

    Vielen Dank schonmal für eure Hilfe 😉



  • Ein Pointer ist auch nur ein Datentyp. Du kannst jeden Datentyp als Value oder als Referenz übergeben.


Log in to reply