ค้นหาองค์ประกอบใน Singly Linked List ที่กำหนดโดยใช้ C++

ได้รับ singly linked list งานคือค้นหาองค์ประกอบเฉพาะใน linked list หากพบองค์ประกอบ ให้พิมพ์ "present" มิฉะนั้น "Not present" ตัวอย่างเช่น

ตัวอย่างอินพุต 1

1 → 2 → 3 → 4 → 5 → 6

ค้นหา '7'

เอาต์พุต

Not Present

คำอธิบาย

ใน singly linked list ที่กำหนด องค์ประกอบ '7' ไม่มีอยู่ ดังนั้นเราจะคืนค่าเอาต์พุตเป็น "Not Present"

ตัวอย่างอินพุต 2

1 → 2 → 3 → 4 → 5

ค้นหา '2'

เอาต์พุต

Present

คำอธิบาย

เนื่องจากใน Singly linked list ที่กำหนด องค์ประกอบ '2' มีอยู่ ดังนั้นเราจะคืนค่าเอาต์พุตเป็น "Present"

วิธีการแก้ปัญหา

มีสองวิธีในการค้นหาองค์ประกอบเฉพาะใน singly linked list ที่กำหนด เราต้องตรวจสอบแบบ recursive ว่าองค์ประกอบหนึ่งมีอยู่ใน linked list หรือไม่

ถ้า linked list ว่าง เราจะคืนค่า false มิฉะนั้นถ้าค่าข้อมูลของโหนดปัจจุบันเท่ากับองค์ประกอบอินพุต เราจะคืนค่า true ในอีกวิธีหนึ่ง เราตรวจสอบองค์ประกอบแบบ iterative ว่าเท่ากับ current head pointer หรือไม่ และคืนค่า true หรือ false ตามลำดับ

• รับอินพุตและเริ่มต้น singly linked list โดยการแทรกโหนดเข้าไป
• ฟังก์ชัน Boolean recursive searchRecursive(node* head, int element) รับ head pointer ของ linked list และ key element เป็นพารามิเตอร์
• เริ่มต้นถ้า head เป็น NULL หรือ linked list ว่าง ให้คืนค่า false
• ถ้าองค์ประกอบที่จะค้นหาเท่ากับ head ปัจจุบันของ linked list ให้คืนค่า true

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int d) {
        data = d;
        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;
    }
    return 0;
}

ผลลัพธ์

การรันโค้ดด้านบนจะสร้างเอาต์พุตเป็น

Not Present

เนื่องจากใน linked list ที่กำหนด 1→2→3→4→5 องค์ประกอบ '7' ไม่มีอยู่ ดังนั้นเราคืนค่า "Not Present"