다중 레벨 데이터 구조 (링크 된 목록)

Question

다음과 같이 보이는 다중 레벨 데이터 구조를 구현하려고합니다.

object { 
    object A { 
      child { 
       myChild; 
      }; 
      child 1 { 
       mychild; 
      }; 
    }; 
    object B { 
     child { 
     }; 
    }; 
}; 

내 접근 방식은 아래와 같이 링크 된 목록을 사용하여 구현하는 것입니다. 연결리스트보다이 다른 구현하거나 연결리스트를 사용하는 다른 더 좋은 방법이 있는지

typedef struct node_s { 
    char *text; 
    ....; 
} node_t; 

typedef struct list_s { 
    STAILQ_ENTRY(list_s) link; 
    node_t *first_child; 
    node_t *parent; 
    node_t *next; 
    int level; 
} list_t; 

typedef STAILQ_HEAD(list_head_s, list_s) list_head_t; 

제안하시기 바랍니다 될 것입니다 STAILQ (SYS/queue.h 리눅스)에 대한 목록 위의 변환

typedef struct node_s { 
    struct node_s *next; 
    struct node_s *first_child; 
    struct node_s *parent; 
    char *text; 
} node_t; 

?

Answer 1

구조는 연결된 목록보다 많은 나무입니다. 각 노드가 0 개 이상의 자식을 가질 수있는 노드 모음이며 루트를 제외한 모든 노드는 정확히 하나의 부모를 갖습니다.

사용중인 표현 체계를 일반적으로 left-child, right-sibling 트리 표현이라고합니다. 각 노드에 명시 적으로 자식 목록을 저장하는 대신 자식 노드 중 하나에 대한 포인터를 저장하고 자식을 연결된 목록을 통해 서로 연결합니다. 링크 된 질의 응답에서 언급했듯이, 메모리가 부족할 때 이점이 있지만 주어진 노드의 특정 하위를 검색하는 데 필요한 시간이 길어집니다.

이 구조체를 나타낼 수있는 다른 많은 방법이 있으며 실제로 수행하는 방법을 결정할 때 결정됩니다. 하나의 옵션은 자식 이름 (예 : 해시 테이블 또는 균형 이진 검색 트리)으로 키가 지정된 일종의 연관 배열 구조에 자식을 저장하는 것입니다. 이렇게하면 메모리 사용량이 조금 증가하지만 이름이 지정된 특정 아이를 찾기가 훨씬 더 빠릅니다. 또 다른 옵션은 각 노드의 자식을 통해 연결된 목록을 스레딩하는 대신 모든 자식을 명시 적으로 배열로 사용하는 것입니다. 할당량이 더 많이 필요하지만 주어진 노드에 자식을 더 쉽게 추가 할 수 있습니다.

희망이 도움이됩니다.