Verkettete Listen

Stromberg

Da mein Buch anscheinend so sch**** ist, hätt vll. jemand n gutes "verkettete Listen" Tutorial? Oder eine "eleganteres" Beispiel. Weil wenn will ichs ja gleich gescheit lernen.
MfG
Stromberg

Stromberg

Weiß echt keiner eine "www-Adresse" für mich? Also ich hab gegoogelt und so, aber nix gefunden irgendwie.
MfG
Stromberg

Braunstein

Dann hast du aber nicht gut geschaut. Ich habe bei Google z.Bsp. das hier gefunden.
http://hal.iwr.uni-heidelberg.de/lehre/inf1-ws02/html/node47.html
http://cib.bau.tu-dresden.de/lehre/scripte/bauinfo1/U-3-1_verk-List_02-02-01.ppt

Simon2

Braunstein schrieb:

Dann hast du aber nicht gut geschaut. Ich habe bei Google z.Bsp. das hier gefunden.
http://hal.iwr.uni-heidelberg.de/lehre/inf1-ws02/html/node47.html
http://cib.bau.tu-dresden.de/lehre/scripte/bauinfo1/U-3-1_verk-List_02-02-01.ppt

Hab' mir mal die 2. angesehen und finde die aber auch nicht so dolle (wildes C/C++-Mix, tw. konfuse Darstellung, Fehler in Beispielprogrammen, "iostream.h", ...)

Gruß,

Simon2.

Hast du dir meinen ersten Link angeschaut !?
Da kannst du dir das von mir für den ersten Einstieg anschauen und das dann von Werner versuchen zu verstehen ...

Edit: Wenn du das von Werner dir anschaust, nimm die Stift und Papier dazu und versuche es zu verfolgen, wenn du es dann einmal gerafft hast, vergisst du es nie wieder.

Badestrand

Ich weiß gar nicht, ob du überhaupt ein Tutorial brauchst; verkettete Listen sind eigentlich sehr einfach. Ich versuche einfach mal zusammenzufassen, was ich weiß:
Es gibt einfach verkettete und doppelt verkettete Listen. Es gibt zirkuläre und nicht-zirkuläre, intrusive- und nonintrusive-Listen.

Eine einfache einfach-verkettete Liste mag so aussehen:

template<class T> struct Node
{
    T     value;
    Node* next;
};

template<class T> class SingleLinkedList
{
private:
    Node* start;

public:
    // add, delete, search, ...
};

Dabei hat einfach jedes Teil der Liste einen Zeiger auf das nächste Element und NULL für "es gibt kein nächstes", jedenfalls bei nicht-zirkulären. Bei zirkulären Listen zeigt das letzte Element wieder auf das erste.

Bei doppelt verketteten Listen hat jedes Element noch einen Zeiger auf das vorherige Element.

Intrusivität hat hustbaer ja schon erklärt, hier aber nochmal ausführlicher: Bei non-intrusive-Listen fügt man ein Element in die Liste z.B. mit list.add( "hallo" ); ein, man gibt also den Datenwert an; die Liste fügt ein Node ein, setzt die Zeiger und der Member "value" der Node bekommt den Wert, der bei list.add übergeben wurde (per Copy-Konstruktor z.B.).

Bei instrusive-Listen bekommt man bei list.add einen fertigen Node gereicht (bzw einen Zeiger darauf) und braucht diesen nur noch einzufügen.

Beispiel non-intrusive:

template<class T> struct Node
{
    T     value;
    Node* next;

    Node( Node* n, T v ) : next(n), value(v)
    {}
};

template<class T> class SingleLinkedList
{
private:
    Node* start;

public:
    void push_to_front( T value )
    {
        start = new Node( start, value );
    }
};

..

SingleLinkedList<int> list;
list.push_to_front( 10 );

Beispiel intrusive:

template<class T> struct Node
{
    T     value;
    Node* next;

    Node( T v ) : value(v), next(NULL)
    {}
};

template<class T> class SingleLinkedList
{
private:
    Node* start;

public:
    void push_to_front( Node* n )
    {
         n->next = start;
         start = n;
    }
};

..

SingleLinkedList<int> list;
Node* n = new Node( 10 );
list.push_to_front( n );

Aso, zwei Sachen noch: Die Klasse (hier z.B. SingleLinkedList) kann auch noch einen Zeiger auf die letzte Node haben, um leichter hinten einfügen zu können, oder zum rückwärts-iterieren. Und zum Suchen von Elementen oder einfügen in der Mitte musst du dich natürlich von Node zu Node hangeln.

Braunstein

@Simon2
Ich wollte anhand der Links erstmal nur zeigen, dass es bei Google etwas gibt. Kann sein, dass die verbesserungswürdig sind.
Das Problem ist hier wahrscheinlich die Existenz von std::list. Seit es die gibt, ist der Bedarf an Tutorials über verkettete Listen für C++ etwas gesunken.

Simon2

Braunstein schrieb:

@Simon2
Ich wollte anhand der Links erstmal nur zeigen, dass es bei Google etwas gibt....

Ich weiß.
Sollte auch keine Kritik an Dir sein, sondern lediglich ein Hinweis für den unbedarften "Draufclicker", dass die 2. Quelle mit Vorsicht zu genießen ist.

Gruß,

Simon2.

Simon2

Badestrand schrieb:

...verkettete Listen sind eigentlich sehr einfach....

Finde ich eigentlich auch ... kannst Du mir mal sagen, warum in dem OP-Beispiel und auch dem einen von Brauns Links "Head" und "Tail" eine Sonderrolle bekommen ?
(Ich hätte das so wie Du implementiert und "ungefüllte Verweise" auf 0 gebogen)

Braucht man irgendwo die Unterscheidung in "Node, Head, Tail" ?

Gruß,

Simon2.

Badestrand

Simon2 schrieb:

Braucht man irgendwo die Unterscheidung in "Node, Head, Tail" ?

Mir kommt es jedenfalls nur vor als wäre das ein wenig über-objektorientiert. Im Code vom OP hat ja die Node-Klasse virtuelle Funktionen und drei abgeleitete Klassen, imho ein wenig zuviel des Ganzen, für diese Funktionalität auf jeden Fall. Obwohl die Liste dort wohl auch sortiert, was ich so auch noch nicht kenne, wofür man aber sicherlich auch nicht den ganzen Overhead braucht

Stromberg

Ncoh mal ganz ganz kurz zu dem "schlechten" Beispiel aus meinem Buch, da hieß es ja am anfang:

#include <iostream> 
using namespace std; 

enum {kIsSmaller,kIsLarger,kIsSame}; 

class Data 
{ 
    public: 
    Data(int val):myValue(val){} 
    ~Data(){} 
    int Compare(const Data &); 
    void Show() {cout << myValue << endl;} 

    private: 
    int myValue; 
}; 

int Data::Compare(const Data &theOtherData) 
{ 
    if (myValue < theOtherData.myValue) 
    return kIsSmaller; 
    if (myValue > theOtherData.myValue) 
    return kIsLarger; 
    else 
    return kIsSame; 
} 

class Node;  // <--?
class HeadNode; //<--?
class TailNode;  //<--?
class InternalNode;  //<--?

class Node 
{ 
    public: 
    Node() {} 
    virtual ~Node() {}
//..........

//..............

//......................

//:..........................

Da wo ich jetzt im Code überall so "<--" hingemacht habe, was ist das? Ist das irgendeine Sonderform die nur bei "verketteten Listen" angewndet wird...oder was ist das? Sry, sowas hab ich irgendwie noch nie gesehen, oder steht ich jetzt irgendwie nur auf der LEitung, eine andere schreibweise für was bock "bekanntes" was ich auch kenne?..Kann mirs jemand sagen?
MfG
Stromberg

Badestrand

Das sind einfach nur Vorwärts-Deklarationen, hat auch nix mit Listen speziell zu tun
Braucht man öfters mal, um den Compiler ruhig zu stellen. Wenn man z.B. zwei Klassen hat, wo jede davon einen Zeiger auf die jeweils andere hat,

class A {
    B* b;
};

class B {
    A* a;
};

kennt der Compiler natürlich die Klasse B noch nicht, wenn er versucht, die Klasse A zu verstehen. Deshalb macht man eine Vorwärts-Deklaration und sagt damit dem Compiler: "Da gibts eine Klasse B, über die erzähl ich dir später was":

// Mensch an Compiler: "Da gibts eine Klasse B, über die erzähl ich dir später was"
class B;

class A {
    B* b;
};

// Mensch an Compiler: "Siehst du, hier ist sie"
class B {
    A* a;
};

Stromberg

MH achso, also wenn man jetzt schon was aufgreift, obwohl die Klassen Deklaration erst später kommt.

//class B; <--kann ich auch hier hin schreiben, anstatt vor das ";" nach der Klasse A!?

class A
{
    public:
    A() {};
    ~A() {};
    private:
    B *object;
}
class B;

class B
{
    public:
    B() {};
    ~B() {};
    private:
};

ist sowas gemeint? Aber ich mein, dann kann man ja auch gleich einfach:

class B
{
    public:
    B() {};
    ~B() {};
    private:
};

class A
{
    public:
    A() {};
    ~A() {};
    private:
    B *object;
};

so machen?
Oder liegt es da einfach wieder am "Stil"...kp :D, oder weil der Programmierer erst bock hat die eine Klasse zu machen als die andere?

Mh, also im großen und ganzen hab ichs verstanden glaub ich.

MfG
Stromberg

Badestrand

class A
{
    B* b;
}
class B;

Geht gar nicht! Das muss schon vor der Deklaration von A sein, weil der Compiler bei "B* b;" ja den Bezeichner B noch nicht kennt. Und zwischen "}" und ";" am Ende der Klasse steht wenn dann nur eine Instanzdeklaration der Klasse. Soll heißen (), dass man mit class A { ... } a; gleich schon eine Variable vom Typ "A" deklariert.

Stromberg schrieb:

ist sowas gemeint? Aber ich mein, dann kann man ja auch gleich einfach:
class B
{
    public:
    B() {};
    ~B() {};
    private:
};

class A
{
    public:
    A() {};
    ~A() {};
    private:
    B *object;
};
so machen?

Ja klar, aber in meinem Beispiel oben hatte die Klasse B ja noch einen Zeiger auf die Klasse A. Nennt sich dann glaubich zirkuläre Abhängigkeit oder so. Jedenfalls braucht man dann in jedem Fall eine Vorwärts-Deklaration

finix

Simon2 schrieb:

Badestrand schrieb:

...verkettete Listen sind eigentlich sehr einfach....

Finde ich eigentlich auch ... kannst Du mir mal sagen, warum in dem OP-Beispiel und auch dem einen von Brauns Links "Head" und "Tail" eine Sonderrolle bekommen ? [sic]
(Ich hätte das so wie Du implementiert und "ungefüllte Verweise" auf 0 gebogen)

Braucht man irgendwo die Unterscheidung in "Node, Head, Tail" ? [sic]

Keine Unterscheidung wie im OP, aber es kann durchaus nützlich sein Head und Tail als Dummy-Elemente zu haben.