"노드"는 ADT입니까? 그렇다면 인터페이스는 무엇입니까?

Question

노드는 ADT를 구현하는 데 유용하지만 ADT 자체의 "노드"입니까? 어떻게 "노드"를 구현합니까? Wikipedia는 노드에 대한 (간단한) 기사에서 메소드가없는 일반 오래된 구조체를 사용합니다. 나는 그들에 대한 철저한 기사를 찾으려고 시도했지만 대부분은 노드로 구현 된보다 복잡한 데이터 유형을 논하는 기사를 찾았다.

노드 란 무엇입니까? 노드가 다른 노드에 연결하는 메소드를 가져야합니까, 아니면 노드를 소유하고있는 노드에 남겨 두어야합니까? 노드가 독립 실행 형 클래스 여야합니까? 아니면 그것을 내부 구조체 또는 내부 클래스로 포함하는 것으로 충분합니까? 이 토론을하기에는 너무 일반적입니까?

Answer 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 라이브러리가 필요 없기 때문에 좋은 디자인의 ADT 라이브러리는 상속을 피할 것입니다.

컴파일러의 표준 C++ 라이브러리에서 std::map의 코드를 읽고 해당 코드가 제대로 수행되었는지 확인하는 것이 좋습니다. 물론 ADT 트리가 아니라 Red-Black 트리가 표시되지만 노드 구조체는 동일해야합니다. 특히 데이터 구조에 대해 사적이고 데이터 이외의 다른 부분으로 구성된 가벼운 구조체를 볼 수 있습니다.

Answer 4

노드는 상위 클래스를 구현하는 세부 사항입니다.노드는 존재하지 않거나 독자적으로 작동합니다. 링크 된 클래스라는 초기 클래스보다 별도의 수명과 메모리 관리가 필요하기 때문에 존재합니다. 따라서, 그들은 실제로 자신을 자신의 타입으로 정의하지는 않지만, 자신의 존재가 효과적으로 사용자로부터 캡슐화되면 소유 클래스의 캡슐화없이 행복하게 존재합니다. 노드는 일반적으로 다형성 또는 다른 객체 지향 동작을 표시하지 않습니다.

일반적으로 노드가 클래스의 공용 또는 보호 된 인터페이스에 포함되어 있지 않으면 신경 쓰지 않고 구조체로 만드십시오.

Answer 5

ADT는 실제 유형이 아닙니다. 그것이 ADT라고 불리는 이유입니다. '노드'가 ADT입니까? 진짜로, IMO. 연결된 목록 ADT와 같이 하나의 일부일 수 있습니다. '이 노드는 방금 ADT를 포함하도록 만들었습니까? 절대적으로하지! 기껏해야 ADT를 구현 한 예입니다.

실제로 ADT를 코드로 표시 할 수있는 유일한 경우는 템플릿 클래스입니다. 예를 들어 C++ STL의 std :: list는 실제 ADT이며 인스턴스의 예가 아닙니다. 한편, std::list<thingy>은 ADT 인스턴스의 예입니다.

일부 사용자는 일부 인터페이스를 따르는 항목을 포함 할 수있는 목록도 ADT라고 말할 수 있습니다. 나는 그들과 약간 동의하지 않을 것이다. 이것은 특정 인터페이스를 준수해야하는 다양한 객체를 포함 할 수있는 ADT 구현의 예입니다.

std :: list의 "개념"의 요구 사항에 대해서도 비슷한 논의가있을 수 있습니다. 예를 들어 T 유형은 복사 가능해야합니다. 나는 이전 버전이 실제로 특정 신원을 요구하는 동안 이것들이 단순히 ADT 자체의 요구 사항이라고 말함으로써 그것을 반박 할 것입니다. 개념은 인터페이스보다 상위 수준입니다.

실제로 ADT는 ADT에서 알고리즘, 빅 O 등을 말하는 것 외에는 "패턴"과 매우 유사합니다. 패턴을 사용하여 추상화, 재사용 등에 대해 이야기합니다. 다른 말로, 패턴은 구현이 특정 유형의 문제를 해결하고 확장/재사용 될 수있는 무언가를 만드는 방법입니다. ADT는 알고리즘을 통해 조작 할 수 있지만 정확히 확장 할 수없는 개체를 작성하는 방법입니다.

Answer 6

가장 엄격한 용어로, 일반적으로 데이터에서 작동하는 멤버 함수가있는 일종의 번들로 구성된 하나 이상의 기본 유형의 추상화는 추상 데이터 유형입니다.

회색 영역은 주로 사용하는 언어에 따라 다릅니다. 예를 들어, Python에서 일부 코더는 목록을 원시 유형으로 간주하므로 ADT가 아닙니다. 그러나 C++에서는 STL 목록이 확실히 ADT입니다. 많은 사람들이 STL 문자열을 ADT로 간주 할 것이지만 C#에서는 원시적입니다.

직접적으로 질문에 답하십시오 : 데이터 구조를 정의 할 때마다 구조체 또는 클래스이거나 메소드가 있거나 없으면 원시 데이터 형식을 추상화하여 ADT가됩니다. 당신에게는 또 다른 목적이 있습니다.

Answer 7

당신의 질문에 C + +, nodes, 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.,