「ノード」はADTですか？もしそうなら、そのインターフェースは何ですか？

Question

ノードはADTを実装するのに便利ですが、ノード自体はADTですか？どのように "ノード"を実装していますか？ Wikipediaはノード上の（簡単な）記事ではメソッドを持たない単純な古い構造体を使います。私は彼らに徹底的な記事を試してみるためにノードを探索しましたが、ほとんどがノードで実装されたより複雑なデータ型について論じる記事を発見しました。

ノードとは何ですか？ノードに他のノードへのリンクのためのメソッドを持たなければならないか、それともノードを所有しているものに残すべきですか？ノードは独自のスタンドアロンクラスでなければなりませんか？それとも、それを内部構造体または内部クラスとして含めるだけで十分ですか？この議論をするにはあまりにも一般的ですか？

Answer 1

ノードは非常に一般的な用語です。基本的に、ノードはグラフの頂点、またはネットワーク内のポイントです。

データ構造に関しては、ノードは通常、（通常）他のユニットに接続され、より大きなデータ構造を形成する単一の基本単位のデータを意味します。これを実証する単純なデータ構造はリンクされたリストです。リンクされたリストは単なるノードのチェーンであり、各ノードはポインタを介して次のノードにリンクされています。エンドノードにはヌルポインタがあります。

ノードは、任意の単一のノードが任意の数の他のノードに接続されているグラフや、各ノードが2つ以上の子ノードを持つツリーなど、より複雑な構造を形成できます。 1つ以上の接続されたノードからなる任意のデータ構造がグラフであることに留意されたい。

"ノード"の概念をクラスのようなオブジェクト指向の概念にマッピングするという点では、C++では通常はデータ構造クラス（時には既知のコンテナとして）、個々のノードですべての作業を内部的に行います。たとえば、LinkedListというクラスがあるとします。したがって、LinkedListクラスは、LinkedList::Nodeのように、個々のノードを表す内部定義（ネスト）クラスを持ちます。

さらに複雑な実装では、データ構造にアクセスする唯一の方法としてノード自体が表示されることがあります。次に、ノードで動作する一連の関数があります。しかし、これはCプログラムでよく見られます。たとえば、struct LinkedListNodeがあるとしたら、void LinkedListInsert(struct LinkedListNode* n, Object somethingToInsert);

のような関数に渡されます。オブジェクト指向のアプローチは、ユーザーからの実装の詳細がよく隠れているので、優れています。

Answer 2

通常、ノード操作は、ADTが所有するものに任せます。例えば、リストはそれ自身のノードをトラバースする能力を持たなければならない。ノードにその能力を持たせる必要はありません。

ノードは、ADTが保持するデータの単純なビットと考えてください。

Answer 3

ADTの文脈でノードは、データ構造に保存したいデータと、データ構造が完全性を維持するために必要ないくつかの配管メタデータです。いいえ、ノードはADTではありません。 ADTライブラリの優れた設計は、実際には必要ないため、ここでは継承を避けます。

コンパイラの標準C++ライブラリのstd::mapのコードを読んで、正しく実行されているかどうかを確認することをお勧めします。確かに、あなたはおそらくADTツリーを見ることはできませんが、Red-Blackツリーは見えますが、ノード構造は同じでなければなりません。特に、データ構造にプライベートな構造を持ち、データ以外にはほとんど含まれない軽量構造体が存在する可能性があります。

Answer 4

ノードは、上位クラスを実装する詳細です。ノードは、存在しないか、それ自身で動作しません。リンクされたリストクラスなどの初期のライフタイムとメモリ管理とは別のライフタイムとメモリ管理の必要性のために存在します。したがって、実際には自分自身の型として自分自身を定義することはできませんが、その存在が効果的にユーザーからカプセル化されていれば、所有クラスからのカプセル化がなくてもうれしく存在します。ノードは、典型的には多型や他のオブジェクト指向の振舞いも表示しません。

一般的に言えば、ノードがクラスのパブリックインターフェイスまたは保護されたインターフェイスに含まれていない場合、ノードを構造化するだけで構いません。

Answer 5

ADTは実数型ではありません。それがADTと呼ばれる理由です。 「ノード」はADTですか？実際には、IMO。それはリンクされたリストADTのような1の一部であることができます。私はちょうど物事をADTに入れるために作ったこのノードですか？絶対違う！それはせいぜいADTの実装例です。

実際にADTをコードとして表現することができるケースは1つしかありません。これはテンプレート化されたクラスです。たとえば、C++ STLのstd :: listは実際のADTであり、単なるインスタンスの例ではありません。一方、std::list<thingy>は、ADTのインスタンスの例です。

一部のインターフェイスに従うものを含むことができるリストは、ADTでもあるとも言われることもあります。私はそれらに軽く反対するでしょう。これは、すべてが特定のインターフェイスに従わなければならない多種多様なオブジェクトを含むことができるADTの実装例です。

std :: listの「概念」の要件についても同様の議論ができます。例えば、タイプTはコピー可能でなければならない。私は、これはADT自体の要件であり、以前のバージョンでは実際には特定のIDが必要なものであると言います。概念はインタフェースよりも高いレベルです。

実際に、ADTは、ADTのアルゴリズム、ビッグOなどについて言及していること以外は、「パターン」と非常によく似ています。パターンでは、抽象化、再利用などについて話しています。言い換えれば、パターンは、実装が特定のタイプの問題を解決し、拡張/再利用できるものを構築する方法です。 ADTは、アルゴリズムによって操作できるオブジェクトを構築する方法ですが、正確には拡張できません。

Answer 6

厳密に言えば、通常、データを操作するメンバ関数を持つ、ある種のバンドルへの1つ以上のプリミティブ型のアセンブリーは、抽象データ型です。

灰色の領域は主にあなたがどの言語を使用しているのかによって異なります。たとえば、Pythonでは、一部のコーダーはリストをプリミティブ型とみなし、ADTではないと考えています。しかし、C++では、STLリストは間違いなくADTです。多くの人がSTL文字列をADTとみなしますが、C＃では間違いなくプリミティブです。

質問に直接答える：データ構造を定義するときはいつでも、構造体またはクラスであり、メソッドの有無にかかわらず、プリミティブデータ型を抽象化しているので、必ずADTです。あなたは別の目的を持っています。

Answer 7

あなたは3つのほとんど直交した概念、つまりC++、ノード、ADTを混在させています。

これらの概念の共通点について一般的に言えることを整理しようとすると便利ではないと思います。

ただし、 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); 
    } 
} 

私は最初にこれらの操作をパスカルの80年代初頭に書きました。

それは、彼らがどれほど知られているかわからなくても、私は絶えず驚いています。

乾杯& HTH :-)。すべての周り、