재귀적 방법을 사용하여 C++의 마지막 연결 리스트에서 n번째 노드를 찾습니다.

단일 연결된 목록과 양의 정수 N이 입력으로 제공됩니다. 목표는 재귀를 사용하여 주어진 목록의 끝에서 N번째 노드를 찾는 것입니다. 입력 목록에 노드 a → b → c → d → e → f가 있고 N이 4인 경우 마지막에서 네 번째 노드는 c가 됩니다.

먼저 목록의 마지막 노드까지 순회하고 재귀(역추적) 증분 카운트에서 돌아올 때입니다. count가 N과 같으면 현재 노드에 대한 포인터가 결과로 반환됩니다.

이에 대한 다양한 입력 및 출력 시나리오를 살펴보겠습니다. -

Input- 목록: - 1 → 5 → 7 → 12 → 2 → 96 → 33 N=3

Output− 밑에서 N번째 노드

− 세 번째 노드는 2입니다.

Input− 목록: - 12 → 53 → 8 → 19 → 20 →96 → 33 N=8 p>

Output- 노드가 존재하지 않습니다.

설명- 목록에는 노드가 7개만 있으므로 아래에서 8번째 노드는 있을 수 없습니다.

아래 프로그램에서 사용한 방법은 다음과 같습니다

이 방법에서는 먼저 노드의 끝에 도달합니다. 재귀를 사용하여 목록을 작성하고 역추적하는 동안 정적 카운트 변수를 증가시킵니다. 개수가 입력 N과 같으면 현재 노드 포인터가 반환됩니다.

• int 데이터 부분이 있는 구조체 노드를 선택하고 노드를 다음 포인터로 사용합니다.

  • 구조 노드와 int 데이터 부분을 사용합니다. p>

  • addtohead(Node** head, int data) 함수는 헤드에 노드를 추가하고 단방향 연결 목록을 만드는 데 사용됩니다.

  • 위 함수를 사용하여 헤드가 첫 번째 노드에 대한 포인터인 단방향 연결 목록을 만듭니다.

  • display(노드* 헤드) 함수는 연결된 목록을 처음부터 인쇄하는 데 사용됩니다.

  • N을 양의 정수로 사용합니다.

  • findNode(Node* head, int n1) 함수는 head와 n1에 대한 포인터를 가져오고 마지막 노드에서 n1번째 노드를 찾으면 결과를 인쇄합니다.

  • 마지막부터 n1번째 노드에 대한 포인터로 blast를 가져옵니다.

  • 노드를 찾으려면 searchNthLast(head, n1, &nlast)를 호출하세요.

  • 함수 searchNthLast(Node* head, int n1, Node** nlast)는 연결된 목록의 끝에서 n1번째 마지막 노드에 대한 포인터를 반환하며, 헤드가 첫 번째 노드입니다.

  • 정적 카운트 변수를 사용하세요.

  • head가 NULL이면 아무것도 반환되지 않습니다.

  • tmp=head->next를 선택하세요.

  • 마지막 노드까지 재귀적으로 순회하려면 searchNthLast(tmp, n1, nlast)를 호출하세요.

  • 이후 개수가 1씩 증가합니다.

  • count가 n1과 같아지면 *nlast=head를 설정하세요.

  • 마지막으로 nlast가 가리키는 노드의 값을 결과로 출력합니다.

  예

  #include  using namespace std; struct Node { int data; Node* next; }; void addtohead(Node** head, int data){ Node* nodex = new Node; nodex->data = data; nodex->next = (*head); (*head) = nodex; } void searchNthLast(Node* head, int n1, Node** nlast){ static int count=0; if (head==NULL){ return; } Node* tmp=head->next; searchNthLast(tmp, n1, nlast); count = count + 1; if (count == n1){ *nlast = head; } } void findNode(Node* head, int n1){ Node* nlast = NULL; searchNthLast(head, n1, &nlast); if (nlast == NULL){ cout << "Node does not exists"; } else{ cout << "Nth Node from the last is: "<< nlast->data; } } void display(Node* head){ Node* curr = head; if (curr != NULL){ cout<data<<" "; display(curr->next); } } int main(){ Node* head = NULL; addtohead(&head, 20); addtohead(&head, 12); addtohead(&head, 15); addtohead(&head, 8); addtohead(&head, 10); addtohead(&head, 4); addtohead(&head, 5); int N = 2; cout<<"Linked list is :"<
            
  
             로그인 후 복사
            
           

  Output

  위 코드를 실행하면 다음과 같은 출력이 생성됩니다

  Linked list is : 5 4 10 8 15 12 20 Nth Node from the last is: 12

  로그인 후 복사

위 내용은 재귀적 방법을 사용하여 C++의 마지막 연결 리스트에서 n번째 노드를 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!