Verkettete Liste - Teil 2

Stromberg

Doch, da hab ich mich vorhin wieder dran erinnert. Die "einfache verkettete Liste" und die "doppelte verkettete List" von Werner von Salomon. Schau ich mir grad an....
MfG
Stromberg

Blue-Tiger

Stromberg schrieb:

Kannst du mir dann nicht sagen was ich anderst machen muss sodass es kein Schwachsinn mehr ist? Bzw. hat den niemand nen Code von einer verketteten Liste, der gut ist? Mal irgend n "perfekter verkettet Liste" Code?....

MfG
Stromberg

mach nicht so viel drumrum. Wenn ich mal selber eine LL programmiere, weil aus irgend einem Grund std::list grad nicht passt, dann meistens ohne grosse Kapselung:

// Node-structure for linked list
struct Node
{
    Node* next;
    MyClass* data;

    Node(MyClass* d, Node* n = 0) : data(d), next(n) {}
};

// ... und dann irgendwo im Code
Node* linkedList;

// ... und irgendwas (am Kopf) hinzufuegen:
linkedList = new Node(new MyClass(), linkedList);

// ... oder irgendwo anders einfuegen
Node* someNode;
someNode->next = new Node(new MyClass(), someNode->next);

// ... und drueberiterieren
Node* cur = linkedList;
while (cur)
{
    cur->doSomething();
    cur = cur->next;
}

// ... und loeschen
void deleteList(Node* n)
{
    if (n->next != 0)
       deleteList(n->next);
    delete n->data;
    delete n;
}

deleteList(linkedList);

Das ist jetzt alles nur schnell hingehackt, aber im Prinzip schaut eine simple LL in etwa so aus (gut moeglich dass das nicht alles Fehlerfrei ist). Ist zwar nicht gekapselt oder wiederverwendbar, aber du wolltest eh nur ein anschauliches Beispiel, und in "echtem Code" verwendet man sowieso meistens std::list.

Stromberg

Bin grad am grübel über das Beispiel von Werner:

class SList
{
public:
    typedef int value_type;

private:
    class Node  // Listenelement
    {
    public:
        explicit Node( const value_type& x, Node* next = 0 )
            : m_next( next )
            , m_value( x )
        {}
        Node* m_next;
        value_type m_value;
    };

public:
    SList()     // ersetzt das init()
        : m_kopf( value_type() )
        , m_ende( &m_kopf )
    {}
    ~SList() { clear(); } // immer schön wieder aufräumen

    void push_back( const value_type& x ) // ersetzt das einfuegen() was ein anhaengen() ist
    {
        m_ende->m_next = new Node( x );
        m_ende = m_ende->m_next;
    }

    void clear() // ersetzt das ende()
    {
        for( Node* p = m_kopf.m_next; p; )
        {
            Node* tmp = p;
            p = p->m_next;
            delete tmp;
        }
        m_kopf.m_next = 0;
        m_ende = &m_kopf;
    }

    // --   Ausgabe
    std::ostream& ausgeben( std::ostream& out, const char* delim = "" )
    {
        for( Node* p = m_kopf.m_next; p; p = p->m_next )
        {
            out << p->m_value << delim;
        }
        return out;
    }

private:
    // Kopieren z.Zt. nicht vorgesehen; -> "Regel der drei"
    SList( const SList& );
    SList& operator=( const SList& );

    // --   Member
    Node m_kopf;
    Node* m_ende;
};

diese Zeile hier verstehe ich nicht:

explicit Node( const value_type& x, Node* next = 0 )

Was bedeutet das "explicit" vor dem Node Konstruktor?

MfG
Stromberg

Badestrand

Wofür ist denn die m_kopf-Variable gut? Bzw warum eine direkte Instanz und warum kein Zeiger? Aber ansonsten siehts gut aus

Stromberg

Stromberg schrieb:

Bin grad am grübel über das Beispiel von Werner:

Aber trotzdem verstehe ich immer noch nicht was er mit dem explicite bezwecken wollte, bzw. was das bedeutet.
MfG
Stromberg

Badestrand

Jaja, tschuldigung
Ich kenne explicit nur, um implizite Casts zu vermeiden. Also wenn man in seiner Klasse ein "int operator int()" einbaut, damit ein Objekt der Klasse zu einem int gecastet werden kann, muss man mit explicit "int i = (int)obj;" statt "int i = obj;" schreiben.
Was das da oben konkret macht, keine Ahnung.. *schäm*

Caipi

Badestrand schrieb:

Jaja, tschuldigung
Ich kenne explicit nur, um implizite Casts zu vermeiden.

Soweit ist es richtig ;).

Also wenn man in seiner Klasse ein "int operator int()" einbaut, damit ein Objekt der Klasse zu einem int gecastet werden kann, muss man mit explicit "int i = (int)obj;" statt "int i = obj;" schreiben.

Das stimmt so nicht. explicit und T operator T() haben zuerst einmal nichts mit einander zu tun. Das explicit vor einem Ctor einer Klasse T besagt lediglich, dass der Compiler das implizite erzeugen von Objekten dieser Klasse nicht zulässt und diese nur mit einem expliziten vorausgehenden ctor-Aufruf konstruiert werden können.

Bsp.

class foo
{
    public:
    explicit foo(size_t v) { ... }
};

int main()
{
    size_t x = 9;
    foo f = 10; // aufgrund des explicit geht das nicht.
    foo b = foo(10); // es geht nur so!
};

Was das da oben konkret macht, keine Ahnung.. *schäm*

Genau das. Es verhindert die implizite Erzeugung von Node-Instanzen.

Gruß, Caipi

Stromberg

Aber das würde doch sowieso nicht gehen oder?:

foo f = 10;

da müsste man doch normalerweiße den Operator "=" überladen?
Weil wenn jetzt "foo" 10 Elementvariabeln hat, welche soll dann mit 10 initialisiert werden? Oder wie ist das?

Das sowas geht:

foo b = foo(10);

wusste ich gar nicht (wieder was gelernt :D). Geht das immer, oder geht das jetzt NUR wenn ich vor meinen Konstruktor "explicite" hinschreibe?

MfG
Stromberg

Badestrand

Bei
foo f = 10;
würde auch der Konstruktor aufgerufen werden, der einen Integer erwartet; wenn's keinen entsprechenden gibt, gehts nicht. Ist also dasselbe wie foo f(10);

foo b = foo(10);
Hier wird meines Wissens ein Objekt von foo temporär erzeugt und dann von b der Copy-Constructor mit dem temporären Objekt als Argument aufgerufen.

Stromberg

foo f = 10;

Das geht aber nur wenn der Konstruktor ein Argument hat?

MfG
Stromberg

http://fara.cs.uni-potsdam.de/~kaufmann/?page=GenCppFaqs&faq=copyvsdirect#Answ

camper

KasF schrieb:

http://fara.cs.uni-potsdam.de/~kaufmann/?page=GenCppFaqs&faq=copyvsdirect#Answ

Eine gute Erklärung, sind aber eineinhalb kleine Fehler drin

Stromberg

Der Unterschied zwischen "Zuweisung" und "Initialisierung" ist, das z.B. bei einer Zuweisung das ganze Objekt übernommen wird, und der "=" Operator (wenn vorhanden) aufgerufen? Also:

class Foo;
......
.......
int main()
{
    Foo A(12);
    Foo B(3);
    B=A; //ZUWEISUNG ?!?

    return 0;
}

Und wenn aber jetzt nur einer Elementvariable ein Wert zugewiesen werden soll, dann ist das eine "Initialiesierung"?:

class Foo;
......
.......
int main()
{
    Foo A(12);
    Foo B(3);
    A=33;
    B=44;

    return 0;
}

Korrekt?

MfG
Stromberg