C++를 사용하여 주어진 단일 연결 목록에서 요소 검색

단일 연결 목록이 주어지면 작업은 연결 목록에서 특정 요소를 검색하는 것입니다. 요소가 발견되면 "present"를 인쇄하고 그렇지 않으면 "Not present"를 인쇄합니다. 예를 들어,

입력-1 -

1→ 2→ 3→ 4→ 5→ 6

'7' 검색

출력 -

Not Present

설명 − 주어진 단일 연결 목록에서 요소 '7'이 존재하지 않으므로 출력을 "Not Present"로 반환합니다.

입력-2 -

1→ 2→ 3→ 4→ 5

'2' 검색

출력 -

Present

설명 − 주어진 Singly 연결 리스트에서 요소 '2'가 존재하므로 출력을 "Present"로 반환합니다.

이 문제를 해결하기 위한 접근 방식

주어진 단일 연결 목록에서 특정 요소를 검색하는 두 가지 접근 방식이 있습니다. 연결 리스트에 하나의 요소가 있는지 여부를 재귀적으로 확인해야 합니다.

연결 목록이 비어 있으면 false를 반환하고 데이터 값을 가진 현재 노드가 입력 요소와 같으면 true를 반환합니다. 다른 접근 방식에서는 요소가 현재 헤드 포인터와 같은지 여부를 반복적으로 확인하고 그에 따라 true 또는 false를 반환합니다.

• 입력을 받고 노드를 삽입하여 단일 연결 목록을 초기화합니다.

• 부울 재귀 함수 searhRecursive(node*head, int element)는 연결 목록의 헤드 포인터와 키 요소를 매개변수로 사용합니다.

• 처음에 헤드가 NULL이거나 연결 목록이 비어 있으면 false를 반환합니다.

• 검색할 요소가 연결 목록의 현재 헤드와 같으면 true를 반환합니다.

예시

#include<iostream>
using namespace std;
#include<iostream>
using namespace std;
class node{
public:
   int data;
   node*next;
   node(int d){
      data=d;
      node*next= NULL;
   }
};
void insertAt(node*&head, int data){
   node*n= new node(data);
   n->next= head;
   head= n;
}
bool searchRecursive(node*head,int key){
   if(head==NULL){
      return false;
   }
   if(head->data==key){
      return true;
   }
   else{
      return searchRecursive(head->next, key);
   }
}
void printNode(node*head){
   while(head!=NULL){
      cout<<head->data<<"->";
      head=head->next;
   }
   cout<<endl;
}
int main(){
   node*head= NULL;
   insertAt(head,5);
   insertAt(head,4);
   insertAt(head,3);
   insertAt(head,2);
   insertAt(head,1);
   printNode(head);
   if(searchRecursive(head,7)){
      cout<<"present"<<endl;
   }
   else{
      cout<<"Not Present"<<endl;
   }
}

출력

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

Not Present

주어진 연결 리스트 1→2→3→4→5에서 요소 '7'이 존재하지 않으므로 "Not Present"를 반환합니다.