Verkettete Listen

G

Gladiator6

Erfahrenes Mitglied
Hallo

Ich bin mehr oder weniger Anfänger in C++! Im Moment beschäftige ich mich mit dynamischen Strukturen, insbesondere Verkette Listen! Das Grundprinzip hab ich schon verstanden, aber ich hab absolut keinen Durchblick!

Verkettete Listen enthalten Knoten. In einem Knoten stehen jeweils irgendwelche Daten und ein Pointer der auf den nächsten Knoten zeigt! richtig?

Mein Ziel ist eigentlich eine doppelt zirkulare verkette Liste mit Zahlen von 1-n!
Soweit bin ich aber noch nicht, im ersten Schritt möchte ich einach zB. 10 Zahlen in eine einfache Liste einlesen! Da happerts bei mir schon!

Mein Anfang sieht folgendermassen aus:

PHP: 
#include<iostream>
using namespace std;

struct tNode
{ 
       int nummer;
       tNode* next;
};
int main()
{
    
tNode *node;
for(int i=1; i<=10; i++)
{
        node=new tNode;
        node->nummer=i;
        
}
system("pause");
}

Nach meinem bisherigen Verständnis wäre "node" ein Zeiger der auf den neu reservierten Speicher zeigt! Mit node->nummer greife ich auf die variable "nummer" im aktuellen Knoten zu und speichere dort eine Zahl (i).Wie kann ich jetzt die Adresse des nächsten Knotens in node->next schreiben?

Kann ich wenn eine Liste fertig ist mit node[i].nummer auf das i-te Element der Liste zugreifen?

Danke für eure Hilfe
 
Hallo Gladiator6,

wenn ich dich richtig verstanden habe, willst du eigentlich eine Liste von Knoten erstellen. Allerdings deklarierst du lediglich einen Pointer. In deiner for-Schleife erstellst du immer wieder ein neues Objekt an derselben Stelle im Speicher. Kurzum: Du hast nur einen einzigen Knoten mit dem Wert 10.
Was du also zuerst einmal brauchst, ist ein Pointer-Array:

Code: 
tNode * nodes[10];
Somit hast du zehn verschiedene Knoten.
Das nächste, was wichtig ist, ist die Tatsache, dass Arrays nullbasiert sind, d.h. das Element hat den Index 0. Dementsprechend muss die for-Schleife bei 0 statt bei 1 beginnen und bis 9 statt bis 10 laufen.

Um nun die Adresse des nächsten Knotens zu ermitteln, kannst du einfach den Knoten mit dem nächsten Index der Struktur-Variablen next zuordnen. Dabei musst du beachten, dass das letzte Element deiner Auflistung keinen Nachfolge-Knoten besitzt:

Code: 
for(int n = 0; n < 10; n++)
{node[n] = new tNode;
node[n]->nummer = n;

if(n < 10) node[n]->next = node[n+1];
}
Das sollte dann eigentlich funktionieren. Falls nicht, sag einfach Bescheid. :)

Gruß
PhoenixLoe
 
Hi
Verbesserungsvorschlag:

tNode *anfang,*node;
anfang=new tNode;
anfnag->nummer=1;
node=anfang;
for(int i=2; i<=10; i++)
{
node->next=new tNode;
node=node->next;
node->nummer=i;
}

Bezüglich Zugriff: Bei einem Array geht das deswegen so, weil alle Elemente genau hintereinander liegen, somit kann sich der COmpiler schon ausrechnen wo das gewünschte Element ist.
Bei Listen ist aber jedes Element irgendwo, bei jedem Programmdurchlauf anders.
Deshalb müssen die einzelnen Knoten ja auch durch das next wissen, wo das jeweilige Nächste Element ist.
DH: Du musst dich bei jedem Zugriff vom Anfang weg durchhanteln, bi du das jeweilige Element gefunden hast.

Gruß
 
@sheel:
Naja, ein Array ist auch eine Liste, allerdings - wie du ja schon richtig angemerkt hast - eine, deren Elemente hintereinander im Speicher liegen. Ergo: Kein Blödsinn.

Deine Antwort war richtig, was aber kein Grund ist, unverschämt zu werden...

In diesem Sinne,

Gruß
PhoenixLoe
 
Ist ja C++:
C++: 
template<typename value_type>
class List
{
    typedef value_type value_t;
    struct Node
    { 
        value_t data;
        Node* ptr_next;
        Node(value_t const& data, Node* ptr_next = NULL)
            : data(data), ptr_next(ptr_next)
        {}
    };
    typedef Node itertator_t;
    iterator_t* m_begin;
    iterator_t*  m_current;

public:
    List()
        : m_begin(NULL), m_current(NULL)
    {}
    ~List()
    {  
        for (iterator_t* ptr_next(m_begin); ptr_next;)
        { 
            iterator_t* ptr_tmp(ptr_next);
            ptr_next = ptr_tmp->next;
            delete ptr_tmp;
        }
    }

public:
    void push_back(value_t const& data)
    {
        m_current = (m_begin == NULL ? m_begin : m_current->ptr_next) = new Node(data);
    }        
};

C++: 
#include <iostream>

int main()
{
    List<int> data;
    for (std::size_t i(0); i < 10; ++i) data.push_back(i + 1);
    std::cin.get();    
}
...
 
Zuletzt bearbeitet:
Danke für die Antworten!

Ich versuchs mal so wie sheel vorgeschlagen hat!

Mit Klassen min ich im Moment noch nicht vertraut, die Liste mit struct ist mir im Moment schon genügend kompliziert!

Ich wäre noch froh wenn mir jemand ein Beispiel einer doppelt zirkular verketteten Liste mit zB. 10 Zahlen geben könnte!
 
Zuletzt bearbeitet:
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück