Cho một danh sách được liên kết đơn lẻ, nhiệm vụ là tìm kiếm một phần tử cụ thể trong danh sách được liên kết. Nếu phần tử được tìm thấy, sau đó in "có mặt" nếu không "Không có mặt". Ví dụ,
Đầu vào-1 -
1→ 2→ 3→ 4→ 5→ 6
Tìm kiếm ‘7’
Đầu ra -
Not Present
Giải thích - Trong danh sách liên kết đơn đã cho, phần tử ‘7’ không có mặt, do đó chúng tôi sẽ trả về kết quả là “Không có mặt”.
Đầu vào-2 -
1→ 2→ 3→ 4→ 5
Tìm kiếm ‘2’
Đầu ra -
Present
Giải thích - Vì trong danh sách liên kết Singly đã cho có phần tử ‘2’ nên chúng tôi sẽ trả về đầu ra là “Hiện tại”.
Phương pháp tiếp cận để giải quyết vấn đề này
Có hai cách tiếp cận để tìm kiếm một phần tử cụ thể trong danh sách được liên kết riêng lẻ đã cho; chúng ta phải kiểm tra đệ quy xem một phần tử có trong danh sách được liên kết hay không.
Nếu danh sách liên kết trống, chúng ta sẽ trả về false, ngược lại nếu nút hiện tại có giá trị dữ liệu bằng phần tử đầu vào thì chúng ta sẽ trả về true. Trong cách tiếp cận khác, chúng tôi kiểm tra lặp đi lặp lại phần tử xem nó có bằng với con trỏ tiêu đề hiện tại hay không và trả về true hoặc false tương ứng.
-
Lấy Đầu vào và Khởi tạo một danh sách được liên kết đơn lẻ bằng cách chèn các nút vào đó.
-
Một hàm đệ quy Boolean searhRecursive (nút * head, phần tử int) lấy con trỏ đầu của danh sách được liên kết và phần tử khóa làm tham số.
-
Ban đầu nếu phần đầu là NULL hoặc nếu danh sách liên kết trống thì trả về false.
-
Nếu phần tử được tìm kiếm bằng với phần đầu hiện tại của danh sách được liên kết thì trả về true.
Ví dụ
#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;
}
} Đầu ra
Chạy đoạn mã trên sẽ tạo ra kết quả là,
Not Present
Vì trong danh sách liên kết đã cho 1 → 2 → 3 → 4 → 5, phần tử ‘7’ không có mặt, do đó chúng tôi trả về “Không có mặt”.