원형 연결 리스트 예제
동적 배열과 연결된 목록을 사용하는 장단점을 강조하는 좋은 예는 Josephus 문제를 해결하는 프로그램을 구현하는 것입니다. 요세푸스 문제는 한 무리의 사람들이 원을 그리게 함으로써 작동하는 선거 방법입니다. 미리 정해진 사람부터 시작하여 원 n 번 을 계산합니다. 9번째 사람에게 도달하면, 그들을 원에서 꺼내서 회원들이 원을 닫게 한다. 그런 다음 같은 n 번 원을 세고 한 사람만 남을 때까지 과정을 반복합니다. 그 사람은 선거에서 이긴다. 이것은 연결된 목록과 동적 배열의 강점과 약점을 보여 주며, 이는 사람들을 순환 링크 된 목록에서 연결된 노드로 보는 경우 연결된 목록이 노드를 얼마나 쉽게 삭제할 수 있는지 보여 주므로 (다른 링크에 대한 링크를 다시 정렬해야하기 때문에) 노드)를 제공합니다. 그러나 링크된 목록은 제거할 다음 사람을 찾는 데 좋지 않으며 해당 사람을 찾을 때까지 목록을 검색해야 합니다. 반면 동적 배열은 모든 요소를 목록 위로 개별적으로 이동하지 않고는 하나의 노드를 제거할 수 없으므로 노드(또는 요소)를 삭제할 수 없습니다. 그러나 배열의 위치에 따라 직접 참조하여 원에서 9 번째 사람을 찾는 것은 매우 쉽습니다. 위에 나열된 대안은 거의 모든 면에서 임의로 결합 될 수 있으므로 파수꾼없이 원형 이중 으로 연결된 목록, 파수꾼이있는 원형 으로 연결된 목록 등이있을 수 있습니다. 없음이 아닌 경우 n_lines 최강 연결(강도=abs(con))만 그려집니다. `이중으로 연결된 목록`에서 각 노드에는 다음 노드 링크 외에 시퀀스의 `이전` 노드를 가리키는 두 번째 링크 필드가 포함됩니다.
두 링크를 `앞으로(`들)`와 `뒤로`, `다음`과 `이전`이라고 할 수 있습니다. 순환적으로 연결된 목록은 다각형의 모서리, FIFO(“선입선”) 순서로 사용되고 해제되는 버퍼 풀 또는 시간 공유해야 하는 프로세스 집합과 같은 자연스럽게 원형배열을 나타내는 자연스러운 옵션일 수 있습니다. 라운드 로빈 순서. 이러한 응용 프로그램에서 모든 노드에 대한 포인터는 전체 목록에 대한 핸들 역할을 합니다. 추상 데이터 형식 또는 템플릿을 지원하는 언어에서는 연결된 목록 ADT 또는 템플릿을 사용하여 연결된 목록을 작성할 수 있습니다.
記事を見てくれてありがとうございます!