جستجوی زیر لیست (Sublist Search) — راهنمای کاربردی

در این مطلب، جستجوی زیر لیست (Sublist Search | جستجوی ساب لیست) مورد بررسی قرار گرفته و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java) و #C انجام شده است. دو لیست لینک شده به یکدیگر، ارائه شده است. هدف، بررسی این است که آیا لیست اول در لیست دوم وجود دارد یا خیر. برای درک بهتر این مطلب، مثال زیر قابل توجه است.

Input  : list1 =  10->20
         list2  = 5->10->20
Output : LIST FOUND

Input  : list1 =  1->2->3->4
         list2  = 1->2->1->2->3->4
Output : LIST FOUND

Input  : list1 =  1->2->3->4
         list2  = 1->2->2->1->2->3
Output : LIST NOT FOUND

جستجوی زیر لیست (Sublist Search)

الگوریتم جستجوی زیر لیست (Sublist Search | جستجوی ساب لیست) در ادامه ارائه شده است.

فیلم آموزش ساختمان داده ها در فرادرس

کلیک کنید

1. اولین گره از دومین لیست را دریافت کن.
2. تطبیق دادن اولین لیست را از این گره ابتدایی آغاز کن.
3. اگر کل لیست مطابقت دارد، مقدار True را بازگردان.
4. در غیر این صورت، break کن و اولین لیست را به اولین گره ببر.
5. و دومین لیست را به دومین گره ببر.
6. این مراحل را تا هنگامی که هر یک از لیست‌های پیوندی خالی باشد، تکرار کن.
7. اگر لیست اول خالی شد، بنابراین لیست پیدا شده است، در غیر این صورت، لیست پیدا نشده است.

در ادامه، پیاده‌سازی الگوریتم بالا ارائه شده است.

جستجوی زیر لیست در ++C

// C++ program to find a list in second list 
#include <bits/stdc++.h> 
using namespace std; 
  
// A Linked List node 
struct Node 
{ 
    int data; 
    Node* next; 
}; 
  
// Returns true if first list is present in second 
// list 
bool findList(Node* first, Node* second) 
{ 
    Node* ptr1 = first, *ptr2 = second; 
  
    // If both linked lists are empty, return true 
    if (first == NULL && second == NULL) 
        return true; 
  
    // Else If one is empty and other is not return 
    // false 
    if ( first == NULL || 
        (first != NULL && second == NULL)) 
        return false; 
  
    // Traverse the second list by picking nodes 
    // one by one 
    while (second != NULL) 
    { 
        // Initialize ptr2 with current node of second 
        ptr2 = second; 
  
        // Start matching first list with second list 
        while (ptr1 != NULL) 
        { 
            // If second list becomes empty and first 
            // not then return false 
            if (ptr2 == NULL) 
                return false; 
  
            // If data part is same, go to next 
            // of both lists 
            else if (ptr1->data == ptr2->data) 
            { 
                ptr1 = ptr1->next; 
                ptr2 = ptr2->next; 
            } 
  
            // If not equal then  break the loop 
            else break; 
        } 
  
        // Return true if first list gets traversed 
        // completely that means it is matched. 
        if (ptr1 == NULL) 
            return true; 
  
        // Initialize ptr1 with first again 
        ptr1 = first; 
  
        // And go to next node of second list 
        second = second->next; 
    } 
  
    return false; 
} 
  
/* Function to print nodes in a given linked list */
void printList(Node* node) 
{ 
    while (node != NULL) 
    { 
        printf("%d ", node->data); 
        node = node->next; 
    } 
} 
  
// Function to add new node to linked lists 
Node *newNode(int key) 
{ 
    Node *temp = new Node; 
    temp-> data= key; 
    temp->next = NULL; 
    return temp; 
} 
  
/* Driver program to test above functions*/
int main() 
{ 
    /* Let us create two linked lists to test 
    the above functions. Created lists shall be 
        a: 1->2->3->4 
        b: 1->2->1->2->3->4*/
    Node *a = newNode(1); 
    a->next = newNode(2); 
    a->next->next = newNode(3); 
    a->next->next->next = newNode(4); 
  
    Node *b = newNode(1); 
    b->next = newNode(2); 
    b->next->next = newNode(1); 
    b->next->next->next = newNode(2); 
    b->next->next->next->next = newNode(3); 
    b->next->next->next->next->next = newNode(4); 
  
    findList(a,b) ? cout << "LIST FOUND" : 
                    cout << "LIST NOT FOUND"; 
  
    return 0; 
}

جستجوی زیر لیست در جاوا

// Java program to find a list in second list 
import java.util.*; 
class GFG  
{  
  
// A Linked List node 
static class Node  
{ 
    int data; 
    Node next; 
}; 
  
// Returns true if first list is  
// present in second list 
static boolean findList(Node first, 
                        Node second) 
{ 
    Node ptr1 = first, ptr2 = second; 
  
    // If both linked lists are empty, 
    // return true 
    if (first == null && second == null) 
        return true; 
  
    // Else If one is empty and  
    // other is not, return false 
    if (first == null || 
       (first != null && second == null)) 
        return false; 
  
    // Traverse the second list by  
    // picking nodes one by one 
    while (second != null) 
    { 
        // Initialize ptr2 with  
        // current node of second 
        ptr2 = second; 
  
        // Start matching first list  
        // with second list 
        while (ptr1 != null) 
        { 
            // If second list becomes empty and  
            // first not then return false 
            if (ptr2 == null) 
                return false; 
  
            // If data part is same, go to next 
            // of both lists 
            else if (ptr1.data == ptr2.data) 
            { 
                ptr1 = ptr1.next; 
                ptr2 = ptr2.next; 
            } 
  
            // If not equal then break the loop 
            else break; 
        } 
  
        // Return true if first list gets traversed 
        // completely that means it is matched. 
        if (ptr1 == null) 
            return true; 
  
        // Initialize ptr1 with first again 
        ptr1 = first; 
  
        // And go to next node of second list 
        second = second.next; 
    } 
    return false; 
} 
  
/* Function to print nodes in a given linked list */
static void printList(Node node) 
{ 
    while (node != null) 
    { 
        System.out.printf("%d ", node.data); 
        node = node.next; 
    } 
} 
  
// Function to add new node to linked lists 
static Node newNode(int key) 
{ 
    Node temp = new Node(); 
    temp.data= key; 
    temp.next = null; 
    return temp; 
} 
  
// Driver Code 
public static void main(String[] args)  
{ 
    /* Let us create two linked lists to test 
    the above functions. Created lists shall be 
        a: 1->2->3->4 
        b: 1->2->1->2->3->4*/
    Node a = newNode(1); 
    a.next = newNode(2); 
    a.next.next = newNode(3); 
    a.next.next.next = newNode(4); 
  
    Node b = newNode(1); 
    b.next = newNode(2); 
    b.next.next = newNode(1); 
    b.next.next.next = newNode(2); 
    b.next.next.next.next = newNode(3); 
    b.next.next.next.next.next = newNode(4); 
  
    if(findList(a, b) == true)  
        System.out.println("LIST FOUND"); 
    else
        System.out.println("LIST NOT FOUND"); 
} 
} 
  
// This code is contributed by Princi Singh 

جستجوی زیر لیست در #C

// C# program to find a list in second list 
using System; 
  
class GFG  
{  
  
// A Linked List node 
class Node  
{ 
    public int data; 
    public Node next; 
}; 
  
// Returns true if first list is  
// present in second list 
static Boolean findList(Node first, 
                        Node second) 
{ 
    Node ptr1 = first, ptr2 = second; 
  
    // If both linked lists are empty, 
    // return true 
    if (first == null && second == null) 
        return true; 
  
    // Else If one is empty and  
    // other is not, return false 
    if (first == null || 
       (first != null && second == null)) 
        return false; 
  
    // Traverse the second list by  
    // picking nodes one by one 
    while (second != null) 
    { 
        // Initialize ptr2 with  
        // current node of second 
        ptr2 = second; 
  
        // Start matching first list  
        // with second list 
        while (ptr1 != null) 
        { 
            // If second list becomes empty and  
            // first not then return false 
            if (ptr2 == null) 
                return false; 
  
            // If data part is same, go to next 
            // of both lists 
            else if (ptr1.data == ptr2.data) 
            { 
                ptr1 = ptr1.next; 
                ptr2 = ptr2.next; 
            } 
  
            // If not equal then break the loop 
            else break; 
        } 
  
        // Return true if first list gets traversed 
        // completely that means it is matched. 
        if (ptr1 == null) 
            return true; 
  
        // Initialize ptr1 with first again 
        ptr1 = first; 
  
        // And go to next node of second list 
        second = second.next; 
    } 
    return false; 
} 
  
/* Function to print nodes 
in a given linked list */
static void printList(Node node) 
{ 
    while (node != null) 
    { 
        Console.Write("{0} ", node.data); 
        node = node.next; 
    } 
} 
  
// Function to add new node to linked lists 
static Node newNode(int key) 
{ 
    Node temp = new Node(); 
    temp.data= key; 
    temp.next = null; 
    return temp; 
} 
  
// Driver Code 
public static void Main(String[] args)  
{ 
    /* Let us create two linked lists to test 
    the above functions. Created lists shall be 
        a: 1->2->3->4 
        b: 1->2->1->2->3->4*/
    Node a = newNode(1); 
    a.next = newNode(2); 
    a.next.next = newNode(3); 
    a.next.next.next = newNode(4); 
  
    Node b = newNode(1); 
    b.next = newNode(2); 
    b.next.next = newNode(1); 
    b.next.next.next = newNode(2); 
    b.next.next.next.next = newNode(3); 
    b.next.next.next.next.next = newNode(4); 
  
    if(findList(a, b) == true)  
        Console.Write("LIST FOUND"); 
    else
        Console.Write("LIST NOT FOUND"); 
} 
} 
  
// This code is contributed by Rajput-Ji 

خروجی قطعه کدهای بالا، به صورت زیر است.

LIST FOUND

پیچیدگی زمانی از درجه O(m*n)‎ است که در آن، m تعداد گره‌ها در دومین لیست و n در اولین لیست است.

فیلم مجموعه آموزش ساختمان داده و طراحی الگوریتم در فرادرس

کلیک کنید

بهینه‌سازی روش ارائه شده در بالا

کد بالا را می‌توان با استفاده از فضای اضافی که لیست را در دو رشته ذخیره و الگوریتم KMP را اعمال می‌کند، بهینه‌سازی کرد.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده
• الگوریتم جست و جوی دودویی در جاوا اسکریپت — به زبان ساده

^^