C++의 재귀 삽입 및 순회 연결 목록

연결된 목록을 구성하는 데 사용할 정수 값이 제공됩니다. 작업은 먼저 재귀 접근 방식을 사용하여 단일 연결 목록을 삽입한 다음 순회하는 것입니다.

마지막에 노드를 재귀적으로 추가

• 헤드가 NULL인 경우 → 헤드에 노드 추가

• 그렇지 않으면 헤드에 추가( 헤드 → 다음 )

노드의 재귀 순회

• 헤드가 NULL인 경우 → 종료

• 그렇지 않으면 인쇄( 헤드 → 다음 )

예시

입력 − 1 - 2 - 7 - 9 - 10

출력 − 연결 리스트 :1 → 2 → 7 → 9 → 10 → NULL

입력 − 12 - 21 - 17 - 94 - 18

출력 − 연결 리스트 :12 → 21 → 17 → 94 → 18 → NULL

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

이 접근 방식에서는 함수를 사용하여 노드를 추가하고 단일 연결 목록을 탐색하고 다음 입력을 위해 재귀적으로 호출합니다.

• 정수가 있는 구조 SLLNode를 사용하고 다음 포인터 SLLNode*를 사용합니다.

• addtoEnd(SLLNode* head, int data) 함수는 리스트의 헤드에 대한 포인터와 데이터 부분에 대한 정수를 취하고 연결 리스트의 끝에 노드를 추가합니다.

• 헤드 포인터가 NULL이면 목록이 비어 있습니다. 이제 새 노드를 추가하고 헤드로 설정합니다. head → next를 NULL로 추가합니다. 이 노드에 대한 포인터 반환

• head가 null이 아닌 경우 head->next =addtoEnd(head->next, data)를 사용하여 head → next에 노드를 추가합니다.

• 함수 traverseList(SLLNode* head)는 헤드에서 순회를 시작하고 각 값을 인쇄합니다.

• head가 NULL이면 NULL을 출력하고 리턴합니다.

• 그렇지 않으면 traverseList(head->next)를 사용하여 데이터 값을 인쇄하고 다음을 탐색합니다.

• main 내부에서 addtoEnd()를 사용하여 목록을 만들고 traverseList()를 사용하여 목록을 인쇄합니다.

예시

#include <bits/stdc++.h>
using namespace std;
struct SLLNode {
   int data;
   SLLNode* next;
};
SLLNode* addtoEnd(SLLNode* head, int data){
   if (head == NULL){
      SLLNode *nodex = new SLLNode;
      nodex->data = data;
      nodex->next = NULL;
      return nodex;
   }
   else{
      head->next = addtoEnd(head->next, data);
    }
   return head;
}
void traverseList(SLLNode* head){
   if (head == NULL){
      cout <<"NULL";
      return;
   }
   cout << head->data << " -> ";
   traverseList(head->next);
}
int main(){
   SLLNode* head1 = NULL;
   head1 = addtoEnd(head1, 1);
   head1 = addtoEnd(head1, 8);
   head1 = addtoEnd(head1, 56);
   head1 = addtoEnd(head1, 12);
   head1 = addtoEnd(head1, 34);
   cout<<"Linked List is :"<<endl;
   traverseList(head1);
   return 0;
}

출력

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

Linked List is :
1 -> 8 -> 56 -> 12 -> 34 -> NULL