Ist "Knoten" ein ADT? Wenn ja, wie ist seine Schnittstelle?

Question

Knoten sind nützlich für die Implementierung von ADTs, aber ist "Knoten" selbst ein ADT? Wie implementiert man "Knoten"? Wikipedia verwendet eine einfache alte Struktur ohne Methoden in seinem (kurzen) Artikel über Knoten. Ich googelte Knoten, um zu versuchen, einen erschöpfenden Artikel über sie zu finden, aber meistens fand ich Artikel, die komplexere Datentypen besprechen, die mit Knoten implementiert werden.

Was ist ein Knoten? Sollte ein Knoten über Methoden zum Verknüpfen mit anderen Knoten verfügen, oder sollte dies den Eigentümern der Knoten überlassen werden? Sollte ein Knoten sogar eine eigenständige Klasse sein? Oder ist es genug, um es als innere Struktur oder innere Klasse einzuschließen? Sind sie zu allgemein, um diese Diskussion überhaupt zu führen?

Answer 1

Ein Knoten ist ein unglaublich allgemeiner Begriff. Im Wesentlichen ist ein Knoten ein Eckpunkt in einem Graphen - oder ein Punkt in einem Netzwerk.

In Bezug auf Datenstrukturen bedeutet ein Knoten normalerweise eine einzelne Basiseinheit von Daten, die (normalerweise) mit anderen Einheiten verbunden sind und eine größere Datenstruktur bilden. Eine einfache Datenstruktur, die dies demonstriert, ist eine verkettete Liste. Eine verkettete Liste ist lediglich eine Kette von Knoten, wobei jeder Knoten (über einen Zeiger) mit dem folgenden Knoten verbunden ist. Der Endknoten hat einen Nullzeiger.

Knoten können komplexere Strukturen bilden, z. B. eine Grafik, bei der ein einzelner Knoten mit einer beliebigen Anzahl anderer Knoten verbunden sein kann, oder eine Struktur, bei der jeder Knoten zwei oder mehr untergeordnete Knoten hat. Beachten Sie, dass jede Datenstruktur, die aus einem oder mehreren verbundenen Knoten besteht, ein Graph ist. (Eine verkettete Liste und ein Baum sind beide auch Graphen.)

Um das Konzept eines "Knotens" auf objektorientierte Konzepte wie Klassen abzubilden, ist es in C++ normalerweise üblich, eine Datenstrukturklasse (manchmal bekannt) zu haben als Container), der intern die gesamte Arbeit an einzelnen Knoten erledigt. Zum Beispiel könnten Sie eine Klasse namens LinkedList haben. Die Klasse LinkedList hätte dann eine intern definierte (verschachtelte) Klasse, die einen einzelnen Knoten darstellt, wie beispielsweise LinkedList::Node.

In einigen gröberen Implementierungen können Sie auch einen Knoten selbst als die einzige Möglichkeit sehen, auf die Datenstruktur zuzugreifen. Sie haben dann eine Reihe von Funktionen, die auf Knoten arbeiten. Dies wird jedoch häufiger in C-Programmen gesehen. Zum Beispiel könnten Sie eine struct LinkedListNode, die dann an Funktionen wie void LinkedListInsert(struct LinkedListNode* n, Object somethingToInsert);

übergeben wird. Meiner Meinung nach ist der objektorientierte Ansatz überlegen, weil es Details der Implementierung vom Benutzer besser versteckt.

Answer 2

Im Allgemeinen möchten Sie die Knotenoperationen dem ADT überlassen, dem sie gehören. Zum Beispiel sollte eine Liste die Fähigkeit haben, ihre eigenen Knoten zu durchlaufen. Es braucht den Knoten nicht, um diese Fähigkeit zu haben.

Denken Sie an den Knoten als ein einfaches Bit der Daten, die die ADT hält.

Answer 3

Im Zusammenhang mit ADT ist ein Knoten die Daten, die Sie in der Datenstruktur speichern möchten, sowie einige Installationsmetadaten, die für die Datenstruktur erforderlich sind, um ihre Integrität zu bewahren. Nein, ein Knoten ist kein ADT. Ein gutes Design einer ADT-Bibliothek wird hier Vererbung vermeiden, weil es wirklich nicht nötig ist.

Ich schlage vor, Sie lesen den Code std::map in der Standard-C++ - Bibliothek Ihres Compilers, um zu sehen, wie es richtig gemacht wird. Zugegeben, Sie werden wahrscheinlich keinen ADT-Baum sehen, sondern einen Rot-Schwarz-Baum, aber die Knotenstruktur sollte gleich sein. Insbesondere werden Sie wahrscheinlich eine leichtgewichtige Struktur sehen, die privat für die Datenstruktur bleibt und aus wenig anderem als Daten besteht.

Answer 4

Knoten sind ein Detail der Implementierung der höheren Klasse.Knoten existieren nicht oder funktionieren nicht von selbst. Sie existieren nur aufgrund der Notwendigkeit für separate Lebensdauern und Speicherverwaltung als die anfängliche, sagen wir verknüpfte Liste, Klasse. Als solche definieren sie sich nicht wirklich als ihren eigenen Typ, sondern existieren glücklich ohne Verkapselung von der besitzenden Klasse, wenn ihre Existenz effektiv vom Benutzer verkapselt wird. Knoten zeigen normalerweise auch keinen Polymorphismus oder andere OO-Verhaltensweisen an.

Im Allgemeinen, wenn der Knoten nicht in der öffentlichen oder geschützten Schnittstelle der Klasse, dann nicht stören, machen Sie sie nur Strukturen.

Answer 5

Ein ADT ist kein echter Typ. Deshalb nennt man es ADT. Ist 'Knoten' ein ADT? Nicht wirklich, IMO. Es kann ein Teil von einem sein, wie eine verknüpfte Liste ADT. Ist 'dieser Knoten, den ich gerade erstellt habe, um ein ADT zu enthalten? Absolut nicht! Es ist bestenfalls ein Beispiel für die Implementierung eines ADT.

Es gibt wirklich nur einen Fall, in dem ADTs als Code ausgedrückt werden können, und das ist wie Templates. Zum Beispiel ist std :: list aus der C++ - STL eine tatsächliche ADT und nicht nur ein Beispiel für eine Instanz von eins. Auf der anderen Seite ist std::list<thingy> ein Beispiel für eine Instanz eines ADT.

Einige könnten sagen, dass eine Liste, die alles enthalten kann, was einer Schnittstelle gehorcht, auch ein ADT ist. Ich würde ihnen leicht widersprechen. Es ist ein Beispiel für eine Implementierung eines ADT, das eine Vielzahl von Objekten enthalten kann, die alle einer bestimmten Schnittstelle unterliegen müssen.

Ein ähnliches Argument könnte über die Anforderungen der std :: list "Konzepte" gemacht werden. Zum Beispiel muss dieser Typ T kopierbar sein. Ich würde dem entgegensetzen, indem ich sage, dass dies nur Anforderungen des ADT selbst sind, während die vorherige Version tatsächlich eine spezifische Identität erfordert. Konzepte sind höher als Schnittstellen.

Wirklich, ein ADT ist einem "Muster" ziemlich ähnlich, außer dass mit ADT wir über Algorithmen sprechen, großes O, usw. ... Mit Mustern sprechen wir über Abstraktion, Wiederverwendung, usw ... Mit anderen Worten, Muster sind ein Weg, um etwas zu bauen, das durch Implementierungen einen bestimmten Problemtyp löst und erweitert/wiederverwendet werden kann. Ein ADT ist eine Möglichkeit, ein Objekt zu erstellen, das durch Algorithmen manipuliert werden kann, aber nicht genau erweiterbar ist.

Answer 6

Im engeren Sinne ist jede Zusammenfassung von einem oder mehreren primitiven Typen in einer Art Bündel, normalerweise mit Elementfunktionen, um mit den Daten zu arbeiten, ein abstrakter Datentyp.

Der Graubereich ergibt sich weitgehend aus der Sprache, in der Sie arbeiten. In Python zum Beispiel betrachten einige Programmierer die Liste als primitiven Typ und somit nicht als ADT. Aber in C++ ist die STL-Liste definitiv eine ADT. Viele würden die STL-Zeichenfolge als ADT betrachten, aber in C# ist sie definitiv ein Primitiv. Um Ihre Frage direkter zu beantworten: Jedes Mal, wenn Sie eine Datenstruktur definieren, sei es struct oder class, mit oder ohne Methoden, ist dies notwendigerweise ein ADT, weil Sie primitive Datentypen in eine Art Konstrukt abstrahieren, für das Sie haben einen anderen Zweck.

Answer 7

Sie mischen drei meist orthogonale Konzepte in Ihre Frage: C++, Knoten, ADTs.

Ich denke nicht, dass es sinnvoll ist, zu versuchen, herauszufinden, was allgemein über die Schnittmenge dieser Konzepte gesagt werden kann.

Jedoch können Dinge über z.B. Einzeln verknüpfte Listenknoten in C++.

#include <iostream> 

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

    Node(): next(0) {} 
    Node(Payload const& v): next(0), value(v) {} 

    void linkInFrom(Node*& aNextPointer) 
    { 
     next = aNextPointer; 
     aNextPointer = this; 
    } 

    static Node* unlinked(Node*& aNextPointer) 
    { 
     Node* const result = aNextPointer; 
     aNextPointer = result->next; 
     return result; 
    } 
}; 

int main() 
{ 
    using namespace std; 
    typedef Node<int> IntNode; 

    IntNode* pFirstNode = 0; 

    (new IntNode(1))->linkInFrom(pFirstNode); 
    (new IntNode(2))->linkInFrom(pFirstNode); 
    (new IntNode(3))->linkInFrom(pFirstNode); 

    for(IntNode const* p = pFirstNode; p != 0; p = p->next) 
    { 
     cout << p->value << endl; 
    } 

    while(pFirstNode != 0) 
    { 
     delete IntNode::unlinked(pFirstNode); 
    } 
} 

Ich schrieb zuerst diese Operationen in Pascal, sehr frühen achtziger Jahren.

Es überrascht mich immer wieder, wie wenig sie bekannt sind. :-)

Beifall & hth.,