C++ : 연결된 목록을 재귀 적으로 추가

Question

이 코드는 두 개의 링크 된 목록을 추가하기로되어 있습니다. 두 번째 매개 변수에 아무런 조작도 일어나지 않으므로이 코드가 인수로 전달 된 두 개의 Cell Structs를 어떻게 추가하는지 완전히 알 수 없습니다. 첫 번째 셀에서 다음 노드를 묻습니다. 어떻게 작동할까요?

void Append(Cell *& first, Cell* second) 
{ 
    if (first == NULL) 
    { 
    first = second; 
    } 
else { 
    Append(first->next, second); 
    } 
} 

Answer 1

함수의 else 블록은 해당 목록의 끝까지 first의 next 포인터를 계속 유지합니다. 즉, first->next이 NULL이고 else이 실행되지 않을 때까지입니다.

이제 기본 케이스가 if 블록에 있습니다. first->next이 NULL 일 때 포인터는 second을 가리키며 다른 목록의 첫 번째 요소 일 것입니다.

어떤 이유가있는 이유는 first->next 포인터가 참조로 전달되기 때문입니다. 포인터를 수정하면 사본을 수정하는 것이 아니라 목록 끝에있는 실제 포인터가 수정됩니다.

Answer 2

first 그것이 제의 제 Cell를 가리 키도록 설정하는 제 목록의 마지막 Cell의 next 포인터에 대한 참조 때까지 재귀. second (단독 연결 목록이라고 가정)을 조작 할 필요가 없습니다.

Answer 3

첫 번째 목록 (else 분기)이 끝날 때까지 걸리는 재귀 알고리즘입니다. 일단 끝이 발견되면 (first==NULL) 두 번째 목록의 첫 번째 요소는 첫 번째 요소의 마지막 요소에 연결되어 두 개의 원래 목록을 연결 한 목록을 얻습니다.

Answer 4

두 번째 목록은 수정할 필요가 없습니다. 코드는 첫 번째 목록의 마지막 요소에 도달 할 때까지 첫 번째 목록을 재귀 적으로 가로 지르고 두 번째 목록의 시작 부분에 해당 요소의 다음 포인터를 설정합니다. 두 번째 목록의 요소는 두 목록에서 공유됩니다.

전에 :

 
first → a → b → c 

second → d → e → f 

후 :

 
first → a → b → c 
       ↓ 
second →  d → e → f