배열을 사용하여 그래프 구현하기

Question

"Tape"라는 데이터 구조에 메모리가 할당 될 그래프를 생성하는 툴을 구현하고 싶습니다. 테이프는 요소의 배열로 생각할 수 있습니다. 각 요소는 "노드 ID"를 보유하고 "부모 노드"및 "자식 노드"에 대한 링크로 간주됩니다.

내가 찾고있는 것은 배열에서 사용 가능한 슬롯을 식별하는 것이 저렴하기 때문에 새로운 노드를 추가 할 때 빈 슬롯을 신속하게 식별 할 수 있습니다.

동적 배열을 사용하여 테이프를 구현하면 어떻게됩니까? 배열 크기를 조정해야하는 상황에서 새로 할당 된 배열에 전체 테이프를 복사하는 것을 피할 수 있습니까?

누구나 여기에 어떤 아이디어가 있습니까?

Answer 1

미리 예를 들어 큰 '테이프'를 할당하려고한다고 가정합니다. 수천 개의 노드.

• 먼저 가게 테이프에 마지막으로 사용 된 항목 :

  당신은이 개념을 결합한다. 다음 번에 새 항목이 필요할 때 마지막으로 사용한 항목 바로 뒤의 항목을 선택하십시오.

• 두 번째로 무료 목록을 유지합니다. 테이프 항목의 처음 4 바이트 (또는 64 비트의 8 바이트)를 다음 여유 항목에 대한 포인터로 사용하십시오. 테이프의 시작은 첫 번째 빈 항목을 가리켜 야합니다.

테이프의 항목이 해제 될 때마다 빈 목록에 추가하십시오. 새 항목이 테이프에 필요할 때마다

:

• 검사 여부를 무료로리스트의 요소가있다. 첫 번째 항목을 가져 와서 무료 목록에서 제거하는 경우
• 무료 목록이 비어 있으면 마지막으로 사용한 항목을 사용하고 바로 다음 항목을 사용하십시오.

또한 테이프의 총 할당 크기를 유지하고 마지막으로 사용한 항목이 테이프 끝에 도달하면 재 할당 구성표와 결합 할 수 있습니다.