Verkettete Liste



  • Hallo,
    ich tue mich die letzten Tage ganz schwer damit, eine verkettete Liste zu verstehen..
    ich habe folgenden Code geschrieben:

    er scheint zu funkionieren, ich verstehe die Zeiger auf die Elemente einfach nicht perfekt..
    Vielleicht hat ja mal jemand Lust, mir die einzelnen Punkte im Code zu erklären..

    Code:

    template <typename T0>
    bool List<T0>::insert(int pos, const T0 &x)
    {
    	if ((pos < 0) || (pos > this->n))
    	{
    		return 0;
    	}
    
    	Node* h = new Node; //erstelle pointerKnoten, der next Pointer hat und Daten, die übergeben werden
    	h->data = x; // Knoten greift auf Member Data zu und bekommt den String übergeben
    	
    
    	if (pos == 0) // Erste position
    	{
    		h->next = head; // next Pointer wird der head Pointer und zeigt dadruch auf Node1
    		head = h; // und head bekommt den string aus h Knoten mit Data 
    	}
    	else
    	{
    		Node* q = head; // Erstellung erstes Listenelemnt 
    		for (int i = 1; i < pos; i++)
    		{
    			q = q->next;
    		}
    		h->next = q->next; // Unklar... warum?
    		q->next = h;
    	}
    	n++;
    	return 1;
    

  • Mod

    q ist das Element an der Stelle, wo du einfügen möchtest. Genauer: Dein neues Element h soll dann an der Stelle hinter q stehen.

    q zeigt derzeit auf ein ihm nachfolgendes Element. Wenn nun h der neue Nachfolger von q werden soll, dann muss hinterher folgendes gelten:

    1. q zeigt auf h als Nachfolger
    2. h zeigt auf den alten Nachfolger von q als Nachfolger
    3. Sonst bleibt alles wie es war

    Und genau das ist, was die beiden Zeilen 25 und 26 machen. Wenn du es immer noch nicht verstehst, mal es dir auf. Ein Bild auf Papier hilft oft ungemein.



  • Okay, danke..
    also ich versuche nochmal genauer zu fragen:

    Bei if (pos == 0)...

    h->next = head; ... Warum soll aus meinem ersten Element der next Zeiger gleich der Head sein, wobei Head auf mein erstes Listenelement zeigt..?
    Meiner Meinung nach muss der h->next Zeiger = 0 sein, weil es das erste und letzte Element ist..

    head = h .. okay, head bekommt den Knoten von h.. für mich verständlich.



  • Du fügst einen neuen Knoten am Anfang der Liste ein. Das heißt, der Nachfolger des neue Knoten ist der alte Head. Der neue Knoten ist als erstes Element in der Liste der neue Head.



  • @spiegelbirke2 sagte in Verkettete Liste:

    ich habe folgenden Code geschrieben:

    @spiegelbirke2 sagte in Verkettete Liste:

    Meiner Meinung nach

    Warum schreibst du etwas anderes als du meinst?


  • Mod

    @spiegelbirke2 sagte in Verkettete Liste:

    Meiner Meinung nach muss der h->next Zeiger = 0 sein, weil es das erste und letzte Element ist..

    Diese Annahme ist falsch. pos=0 bedeutet nicht, dass die Liste leer ist. Es bedeutet, dass die Einfügeposition am Anfange ist. Das ist der Sonderfall! Es ist egal, ob die Liste leer ist, oder nicht, die Sonderbehandlung ist für das Einfügen am Anfang.

    Jetzt hast du also ein head, welcher auf ein erstes Element der Liste zeigt (welches existieren kann oder auch NULL sein kann, egal). Du willst nun ein neues Element h einfügen, welches stattdessen an erster Stelle stehen soll. Hinterher muss also gelten:

    1. head muss nun auf das neue erste Element h zeigen
    2. h muss auf das vormals erste Element zeigen, auf das head vorher gezeigt hat (welches existieren kann oder auch NULL sein kann, egal).
    3. Sonst ändert sich nichts.

    Das ist es, was deine Zeilen 15 und 16 machen.

    @manni66 sagte in Verkettete Liste:

    Warum schreibst du etwas anderes als du meinst?

    Tja, das kommt eben davon, wenn man Code klaut, ohne ihn zu verstehen.


Log in to reply