C++의 연결된 목록에서 루프 감지

루프가 있는 연결 목록의 끝 노드는 NULL이 아닌 같은 목록의 다른 노드를 참조합니다. 연결 목록에 다음 포인터를 따라 반복적으로 액세스할 수 있는 노드가 있는 경우 목록을 주기를 가진다.

일반적으로 연결된 목록의 마지막 노드는 목록의 결론을 나타내기 위해 NULL 참조를 참조합니다. 그러나 루프가 있는 연결 목록에서 목록의 끝 노드는 시작 노드, 내부 노드 또는 자신을 참조합니다. 따라서 이러한 상황에서는 다음 노드의 참조를 NULL로 설정하여 루프를 식별하고 종료해야 합니다. 연결 목록에서 루프의 감지 부분은 이 문서에서 설명합니다.

C++에는 연결된 목록에서 루프를 찾는 다양한 방법이 있습니다.

해시 테이블 기반 접근법 : 이 접근 방식은 방문한 노드의 주소를 해시 테이블에 저장합니다. 다시 방문했을 때 노드가 이미 해시 테이블에 있으면 연결 목록의 루프가 존재합니다.

플로이드의 주기 접근법 : 일반적으로 Floyd의 주기 찾기 알고리즘으로 알려진 '거북이와 토끼' 알고리즘: 이 기술은 두 개의 포인터를 사용합니다. 하나는 다른 하나보다 느리게 움직이고 다른 하나는 더 빠르게 움직입니다. 연결된 목록에 루프가 있으면 빠른 포인터가 느린 포인터를 추월하여 루프의 존재를 드러냅니다.

재귀 방법 : 이 메서드는 자신을 계속해서 호출하여 연결 목록을 통과합니다. 현재 노드가 이전에 방문한 경우 연결된 목록에는 루프가 포함됩니다.

스택 기반 접근 방식 : 이 접근 방식은 방문한 노드의 주소를 스택에 저장합니다. 노드를 다시 방문했을 때 노드가 이미 스택에 있으면 연결 목록의 루프가 존재합니다.

개념을 이해하기 위해 각 접근 방식을 자세히 설명하겠습니다.

접근법 1: HashSet 접근법

해싱을 활용하는 것이 가장 간단한 방법입니다. 여기서는 노드 주소가 있는 해시 테이블을 유지하면서 목록을 하나씩 살펴봅니다. 따라서 해시 테이블에 이미 포함된 현재 노드의 다음 주소를 가로질러 실행하는 경우 루프가 존재합니다. 그렇지 않으면 NULL에 도달하면(즉, 연결 목록의 끝에 도달하면) 연결 목록에 루프가 없습니다.

이 전략을 구현하는 것은 매우 쉬울 것입니다.

연결된 목록을 순회하는 동안 unordered_hashmap을 활용하고 노드를 계속 추가합니다.

이제 맵에 이미 표시된 노드를 만나면 루프의 시작 부분에 도달했음을 알 수 있습니다.

• • 또한 각 단계에서 두 개의 포인터를 유지했습니다. 헤드노드 현재 노드를 가리키고 마지막노드 반복하는 동안 현재 노드의 이전 노드를 가리킵니다.
  • 우리의 헤드노드 이제 루프의 시작 노드를 가리키고 있습니다. 마지막노드 head가 가리키는 노드를 가리키고 있었습니다(즉, 마지막노드 루프의), 우리 헤드노드 현재 루프의 시작 노드를 가리키고 있습니다.
  • l을 설정하면 루프가 끊어집니다. astNode->다음 == NULL .

이렇게 하면 루프의 초기 노드를 참조하는 대신 종료 루프 노드가 NULL을 가리키기 시작합니다.

해싱 방법의 평균 시간 및 공간 복잡도는 O(n)입니다. 독자는 프로그래밍 언어에 내장된 해싱 데이터 구조의 구현이 해싱 충돌 시 총 시간 복잡도를 결정한다는 점을 항상 인식해야 합니다.

위의 메서드(HashSet)에 대한 C++ 프로그램 구현:

산출:

코드의 단계별 설명은 다음과 같습니다.

1. 1. 일반적인 C++ 라이브러리를 모두 포함하는 bits/stdc++.h> 헤더 파일이 코드에 포함되어 있습니다.
   2. '노드'라는 구조가 구성되고 여기에는 목록의 다음 노드에 대한 참조와 '값'이라는 정수의 두 가지 멤버가 있습니다.
   3. 정수 값을 입력으로 사용하고 '다음' 포인터를 NULL로 설정하면 'newNode' 함수는 해당 값으로 새 노드를 만듭니다.
   4. 함수 ' 함수해시맵' 연결 목록의 헤드 노드에 대한 포인터를 입력으로 사용하는 것으로 정의됩니다.
   5. ' 안에 functionHashMap ' 함수를 사용하면 'hash_map'이라는 이름의 unordered_map이 생성되며, 이는 해시 맵 데이터 구조를 구현하는 데 사용됩니다.
   6. 목록의 마지막 노드에 대한 포인터는 NULL로 초기화됩니다.
   7. while 루프는 헤드 노드에서 시작하여 헤드 노드가 NULL이 될 때까지 계속되는 연결 목록을 순회하는 데 사용됩니다.
   8. lastNode 포인터는 현재 노드(headNode)가 해시 맵에 아직 없는 경우 while 루프 내부의 현재 노드로 업데이트됩니다.
   9. 현재 노드가 맵에서 발견되면 연결 목록에 루프가 있음을 의미합니다. 루프를 제거하려면 다음 포인터를 마지막노드 로 설정 없는 while 루프가 끊어졌습니다.
   10. 연결된 목록의 헤드 노드는 목록의 각 노드 값을 처음부터 끝까지 출력하는 '디스플레이'라는 함수의 입력으로 사용됩니다.
   11. 에서 기본 기능, 루프 생성.
   12. 함수 'functionHashMap'은 headNode 포인터를 입력으로 사용하여 호출되어 목록에서 루프를 제거합니다.
   13. 수정된 목록은 '표시' 기능을 사용하여 표시됩니다.

접근법 2: 플로이드의 사이클

종종 거북이와 토끼 알고리즘으로 알려진 Floyd의 주기 감지 알고리즘은 연결 목록에서 주기를 찾는 이 방법의 기반을 제공합니다. 다양한 속도로 목록을 이동하는 '느린' 포인터와 '빠른' 포인터가 이 기술에 사용되는 두 개의 포인터입니다. 빠른 포인터는 두 단계씩 진행하지만 느린 포인터는 매 반복마다 한 단계씩 진행합니다. 연결된 목록의 순환은 두 점이 마주하는 경우 존재합니다.

1. 연결된 목록의 헤드 노드를 사용하여 fast 및 slow라는 두 포인터를 초기화합니다.

2. 이제 연결된 목록을 통해 이동하는 루프를 실행합니다. 빠른 포인터는 각 반복 단계에서 느린 포인터 앞의 두 위치로 이동해야 합니다.

3. 빠른 포인터가 목록의 끝에 도달하면 연결 목록에 루프가 없습니다(fastPointer == NULL 또는 fastPointer->next == NULL). 그렇지 않으면 빠른 포인터와 느린 포인터가 결국 만나며 연결 목록에 루프가 있음을 의미합니다.

위 방법에 대한 C++ 프로그램 구현(Floyd's Cycle):

산출:

설명:

1. 1. 'bits/stdc++.h' 및 'std::cout'과 같은 관련 헤더가 먼저 포함됩니다.
   2. 그런 다음 연결된 목록의 노드를 나타내는 'Node' 구조체가 선언됩니다. 목록의 다음 노드로 연결되는 다음 포인터는 각 노드의 정수 데이터 필드와 함께 포함됩니다.
   3. 그런 다음 두 가지 기능인 'deleteLoop' 및 'detectAndDeleteLoop'를 정의합니다. 첫 번째 방법을 사용하여 연결된 목록에서 루프를 제거하고 두 번째 함수를 사용하여 목록에서 루프를 감지한 다음 첫 번째 프로시저를 호출하여 루프를 제거합니다.
   4. 5개의 노드가 있는 새로운 연결 목록이 main 함수에서 생성되고 마지막 노드의 다음 포인터를 세 번째 노드로 설정하여 루프가 설정됩니다.
   5. 그런 다음 연결 목록의 헤드 노드를 인수로 전달하면서 'detectAndDeleteLoop' 메서드를 호출합니다. 루프를 식별하기 위해 이 함수는 '느리고 빠른 포인터' 접근 방식을 사용합니다. 목록의 맨 위에서 시작하는 두 개의 포인터인 slowPTR과 fastPTR을 사용합니다. 빠른 포인터는 한 번에 두 노드를 이동하는 반면 느린 포인터는 한 번에 한 노드만 이동합니다. 빠른 포인터는 목록에 루프가 포함되어 있고 두 지점이 동일한 노드에서 충돌하는 경우 궁극적으로 느린 포인터를 추월합니다.
   6. 이 함수는 루프를 찾으면 'deleteLoop' 함수를 호출하여 목록의 헤드 노드와 느린 포인터와 빠른 포인터의 교차점을 입력으로 제공합니다. 이 절차는 목록의 헤드 노드에 대한 두 개의 포인터 ptr1 및 ptr2를 설정하고 루프의 노드 수를 계산합니다. 그런 다음 하나의 포인터 k 노드를 진행합니다. 여기서 k는 루프의 총 노드 수입니다. 그런 다음 루프의 시작 부분에서 만날 때까지 두 지점을 한 번에 한 노드씩 이동합니다. 그런 다음 루프의 끝에 있는 노드의 다음 포인터를 NULL로 설정하여 루프를 끊습니다.
   7. 루프를 제거한 후 마지막 단계로 연결된 목록을 표시합니다.

접근법 3: 재귀

재귀는 문제를 더 작고 쉬운 하위 문제로 분할하여 문제를 해결하는 기술입니다. 재귀는 목록의 끝에 도달할 때까지 목록의 다음 노드에 대한 함수를 계속 실행하여 루프가 발견된 경우 단일 연결 목록을 순회하는 데 사용할 수 있습니다.

단일 연결 목록에서 루프를 찾기 위해 재귀를 사용하는 기본 원칙은 목록의 맨 위에서 시작하여 각 단계에서 현재 노드를 방문한 것으로 표시한 다음 for 함수를 재귀적으로 호출하여 다음 노드로 이동하는 것입니다. 그 노드. 이 메서드는 재귀적으로 호출되기 때문에 전체 연결 목록을 반복합니다.

이전에 방문한 것으로 표시된 노드가 함수에 의해 발견되면 목록에 루프가 포함됩니다. 이 경우 함수는 true를 반환할 수 있습니다. 이 메서드는 방문한 노드를 거치지 않고 목록 끝에 도달하면 false를 반환할 수 있습니다. 이는 루프가 없음을 나타냅니다.

단일 연결 목록에서 루프를 찾기 위해 재귀를 사용하는 이 기술은 사용하고 이해하기가 간단하지만 시간 및 공간 복잡성 측면에서 가장 효과적이지 않을 수 있습니다.

위 방법에 대한 C++ 프로그램 구현(재귀):

산출:

설명:

1. 1. 함수 detectLoopLinkedList() 이 프로그램에서 연결 목록의 헤드를 입력으로 받아들입니다.
   2. 재귀는 연결된 목록을 반복하는 함수에서 사용됩니다. 재귀의 기본 사례로 현재 노드가 NULL인지 확인하는 것으로 시작합니다. 그렇다면 메서드는 루프가 존재하지 않음을 나타내는 false를 반환합니다.
   3. 그런 다음 현재 노드의 'visited' 속성 값을 확인하여 이전에 방문한 적이 있는지 확인합니다. 방문했다면 true를 반환하여 루프가 발견되었음을 나타냅니다.
   4. 이 함수는 'visited' 속성을 true로 변경하여 이미 방문한 적이 있는 현재 노드를 방문한 것으로 표시합니다.
   5. 그런 다음 방문한 변수의 값을 확인하여 현재 노드가 이전에 방문한 적이 있는지 확인합니다. 이전에 사용된 적이 있는 경우 루프가 존재해야 하며 함수는 true를 반환합니다.
   6. 마지막으로 함수는 목록의 다음 노드를 전달하여 자신을 호출합니다. headNode->다음 인수로. 재귀적으로 , 이것은 루프가 발견되거나 모든 노드가 방문될 때까지 수행됩니다. 즉, 연결된 목록의 다음 노드에 대해 자신을 재귀적으로 호출하기 전에 현재 노드를 방문한 적이 없는 경우 이 함수는 방문 변수를 참으로 설정합니다.
   7. 이 코드는 3개의 노드를 빌드하고 결합하여 주요 기능 . 방법 detectLoopLinkedList() 그런 다음 목록의 헤드 노드에서 호출됩니다. 이 프로그램은 ' 연결 리스트에서 차감된 루프 ' 만약에 detectLoopLinkedList() true를 반환합니다. 그렇지 않으면 ' 연결된 목록에서 루프가 감지되지 않음 '.
   8. 그런 다음 코드는 마지막 노드의 다음 포인터를 두 번째 노드로 설정하여 연결 목록에 루프를 삽입합니다. 그런 다음 함수의 결과에 따라 실행됩니다. detectLoopLinkedList() 다시 ' 연결 리스트에서 차감된 루프 ' 또는 ' 연결된 목록에서 루프가 감지되지 않음 .”

접근법 4: 스택 사용

연결된 목록의 루프는 스택과 '깊이 우선 검색'(DFS) 방법을 사용하여 찾을 수 있습니다. 기본 개념은 연결된 목록을 반복하여 각 노드를 아직 방문하지 않은 경우 스택에 푸시하는 것입니다. 이미 스택에 있는 노드를 다시 만나면 루프가 인식됩니다.

절차에 대한 간략한 설명은 다음과 같습니다.

1. 1. 방문한 노드를 기록할 빈 스택과 변수를 만듭니다.
   2. 연결된 목록을 맨 위에서 시작하여 스택에 푸시합니다. 헤드를 방문했음을 기록해 두십시오.
   3. 목록의 다음 노드를 스택으로 푸시합니다. 이 노드에 방문 표시를 추가합니다.
   4. 목록을 탐색할 때 각각의 새 노드를 스택에 푸시하여 방문했음을 나타냅니다.
   5. 이전에 방문한 노드가 스택의 맨 위에 있는지 확인하십시오. 그렇다면 루프가 발견되었으며 루프는 스택의 노드로 식별됩니다.
   6. 스택에서 노드를 꺼내고 루프가 없으면 목록을 계속 탐색합니다.

위 방법에 대한 C++ 프로그램 구현(Stack)

산출:

설명:

이 프로그램은 단일 연결 목록에 루프가 있는지 알아보기 위해 스택을 사용합니다.

• 1. 입력/출력 스트림 라이브러리와 스택 라이브러리는 모두 첫 번째 줄에 있습니다.

  2. 표준 네임스페이스는 두 번째 줄에 포함되어 'std::' 접두사를 사용하지 않고도 입력/출력 스트림 라이브러리의 함수에 액세스할 수 있습니다.

  3. 다음 줄은 'data'라는 정수와 'next'라는 다른 노드에 대한 포인터의 두 멤버로 구성된 struct Node를 정의합니다.

  4. 연결된 목록의 헤드는 다음 줄에 정의된 detectLoopLinkedList() 메서드의 입력입니다. 이 함수는 루프가 발견되었는지 여부를 나타내는 부울 값을 생성합니다.

  5. 'stack'이라는 노드 포인터의 스택과 headNode의 값으로 초기화되는 'tempNode'라는 이름의 노드에 대한 포인터가 모두 함수 내에서 생성됩니다.

  6. 그런 다음 tempNode가 널 포인터가 아닌 한 while 루프에 들어갑니다.

  (a) 비어 있지 않은지 확인하려면 스택의 맨 위 요소가 현재 노드와 일치해야 합니다. 루프가 발견되었기 때문에 이 경우 true를 반환합니다.

  (b) 위의 조건이 거짓이면 현재 노드 포인터가 스택으로 푸시되고 tempNode는 연결 목록에서 다음 노드로 설정됩니다.

  7. 루프가 관찰되지 않았기 때문에 while 루프 후에 false를 반환합니다.

  8. 3개의 Node 객체를 만들고 main() 함수에서 초기화합니다. 첫 번째 예에는 루프가 없으므로 각 노드의 '다음' 포인터를 적절하게 설정합니다.

결론:

결론적으로 연결 목록에서 루프를 감지하는 가장 좋은 방법은 특정 사용 사례와 문제의 제약 조건에 따라 다릅니다. Hash Table과 Floyd의 주기 찾기 알고리즘은 효율적인 방법이며 실제로 널리 사용됩니다. 스택과 재귀는 덜 효율적인 방법이지만 더 직관적입니다.