Data Structures Algorithms 简明教程

Sublist Search Algorithm

在目前为止的教程中，我们只看到如何按元素的顺序搜索一个元素。但是，子列表搜索算法提供了一个用于在另一个链表中搜索链表的过程。它就像任何简单的模式匹配算法一样，目的是确定一个列表是否存在于另一个列表中。

Until now, in this tutorial, we have only seen how to search for one element in a sequential order of elements. But the sublist search algorithm provides a procedure to search for a linked list in another linked list. It works like any simple pattern matching algorithm where the aim is to determine whether one list is present in the other list or not.

该算法遍历链表，其中一个列表的第一个元素与第二个列表的第一个元素进行比较；如果找不到匹配项，则将第一个列表的第二个元素与第二个列表的第一个元素进行比较。此过程一直持续到找到匹配项或到达列表的末尾。

The algorithm walks through the linked list where the first element of one list is compared with the first element of the second list; if a match is not found, the second element of the first list is compared with the first element of the second list. This process continues until a match is found or it reaches the end of a list.

例如，考虑两个链表，其值分别为 {4, 6, 7, 3, 8, 2, 6} 和 {3, 8, 2}。子列表搜索检查第二个列表的值是否存在于第一个链表中。输出以布尔值 {True, False} 获取。它无法返回子列表的位置，因为链表不是有序的数据结构。

For example, consider two linked lists with values {4, 6, 7, 3, 8, 2, 6} and {3, 8, 2}. Sublist search checks whether the values of second list are present in the first linked list. The output is obtained in Boolean values {True, False}. It cannot return the position of the sub-list as the linked list is not an ordered data structure.

Note − 仅当第二个链表按完全相同的顺序出现在第一个列表中时，才会返回 true 输出。

Note − The output is returned true only if the second linked list is present in the exact same order in the first list.

Sublist Search Algorithm

此算法的主要目的是证明一个链表是另一个列表的子列表。此过程中的搜索以线性方式完成，逐个检查链表的每个元素；如果输出返回 true，则证明第二个列表是第一个链表的子列表。

The main aim of this algorithm is to prove that one linked list is a sub-list of another list. Searching in this process is done linearly, checking each element of the linked list one by one; if the output returns true, then it is proven that the second list is a sub-list of the first linked list.

子列表搜索算法的过程如下 −

Procedure for the sublist search algorithm is as follows −

*步骤 1 *− 维护两个指针，每个指针指向一个列表。这些指针用于遍历链表。

*Step 1 *− Maintain two pointers, each pointing to one list. These pointers are used to traverse through the linked lists.

*步骤 2 *− 检查链表的基本情况 -

*Step 2 *− Check for the base cases of the linked lists −

If both linked lists are empty, the output returns true.
If the second list is not empty but the first list is empty, we return false.
If the first list is not empty but the second list is empty, we return false.

*步骤 3 *− 一旦确定两个列表都不为空，则使用指针按元素遍历列表。

*Step 3 *− Once it is established that both the lists are not empty, use the pointers to traverse through the lists element by element.

*步骤 4 *− 比较第一个链表的第一个元素和第二个链表的第一个元素；如果匹配，则两个指针分别指向两个列表中的下一个值。

*Step 4 *− Compare the first element of the first linked list and the first element of the second linked list; if it is a match both the pointers are pointed to the next values in both lists respectively.

*步骤 5 *− 如果不匹配，请将第二个列表中的指针保持在第一个元素，但向前移动第一个列表中的指针。再次比较元素。

*Step 5 *− If it is not a match, keep the pointer in second list at the first element but move the pointer in first list forward. Compare the elements again.

*步骤 6 *− 重复步骤 4 和 5，直到到达列表的末尾。

*Step 6 *− Repeat Steps 4 and 5 until we reach the end of the lists.

*步骤 7 *− 如果找到输出，则返回 TRUE，否则返回 FALSE。

*Step 7 *− If the output is found, TRUE is returned and if not, FALSE.

Pseudocode

Begin Sublist Search
   list_ptr -> points to the first list
   sub_ptr -> points to the second list
   ptr1 = list_ptr
   ptr2 = sub_ptr
   if list_ptr := NULL and sub_ptr := NULL then:
      return TRUE
   end
   else if sub_ptr := NULL or sub_ptr != NULL and list_ptr := NULL then:
      return FALSE
   end
   while list_ptr != NULL do:
      ptr1 = list_ptr
      while ptr2 != NULL do:
         if ptr1 := NULL then:
            return false
         else if ptr2->data := ptr1->data then:
            ptr2 = ptr2->next
            ptr1 = ptr1->next
         else break
      done
      if ptr2 := NULL
         return TRUE
         ptr2 := sub_ptr
         list_ptr := list.ptr->next
   done
   return FALSE
end

Analysis

子列表搜索的时间复杂度取决于涉及的两个链表中存在的元素数量。算法执行所需的最坏时间为 O(m*n) ，其中 m 是第一个链表中存在的元素数量，n 是第二个链表中存在的元素数量。

The time complexity of the sublist search depends on the number of elements present in both linked lists involved. The worst case time taken by the algorithm to be executed is O(m*n) where m is the number of elements present in the first linked list and n is the number of elements present in the second linked list.

Example

假设我们有两个链表，其元素如下 -

Suppose we have two linked lists with elements given as −

List 1 = {2, 5, 3, 3, 6, 7, 0}
List 2 = {6, 7, 0}

使用子列表搜索，我们需要找出列表 2 是否存在于列表 1 中。

Using sublist search, we need to find out if List 2 is present in List 1.

Step 1

将表 2 的第一个元素与表 1 的第一个元素进行比较。不是匹配，因此表 1 中的指针移至它的下一个内存地址。

Compare the first element of the List 2 with the first element of List 1. It is not a match, so the pointer in List 1 moves to the next memory address in it.

Step 2

在此步骤中，表 1 的第二个元素与表 2 的第一个元素进行比较。不是匹配，因此表 1 中的指针移至下一个内存地址。

In this step, the second element of the List 1 is compared with the first element of the List 2. It is not a match so the pointer in List 1 moves to next memory address.

Step 3

现在将表 1 中的第三个元素与表 2 中的第一个元素进行比较。由于不是匹配，所以表 1 中的指针向前移动。

Now the third element in List 1 is compared with the first element in the List 2. Since it is not a match, the pointer in List 1 moves forward.

Step 4

现在将表 1 中的第四个元素与表 2 中的第一个元素进行比较。由于不是匹配，所以表 1 中的指针向前移动。

Now the fourth element in List 1 is compared with the first element in the List 2. Since it is not a match, the pointer in List 1 moves forward.

Step 5

现在将表 1 中的第五个元素与表 2 中的第一个元素进行比较。由于是匹配，所以表 1 和表 2 中的指针向前移动。

Now the fifth element in List 1 is compared with the first element in the List 2. Since it is a match, the pointers in both List 1 and List 2 move forward.

Step 6

将表 1 中的第六个元素与表 2 中的第二个元素进行比较。由于也是匹配，所以表 1 和表 2 中的指针向前移动。

The sixth element in List 1 is compared with the second element in the List 2. Since it is also a match, the pointers in both List 1 and List 2 move forward.

Step 7

将表 1 中的第七个元素与表 2 中的第三个元素进行比较。由于也是匹配，所以证明表 2 是表 1 的子表。

The seventh element in List 1 is compared with the third element in the List 2. Since it is also a match, it is proven that List 2 is a sub-list of List 1.

输出返回真。

The output is returned TRUE.

Implementation

在子表搜索实现中，首先使用 C 语言中的 struct 关键字和作为 C++、JAVA 和 Python 语言中的对象创建链表。检查这些链表是否非空；然后逐个线性比较元素以找到匹配项。如果第二个链表以相同的顺序存在于第一个链表中，则输出返回 TRUE ；否则输出打印 FALSE 。

In the sublist search implementation, linked lists are created first using struct keyword in the C language and as an object in C++, JAVA and Python languages. These linked lists are checked whether they are not empty; and then the elements are compared one by one linearly to find a match. If the second linked list is present in the first linked list in the same order, then the output is returned TRUE; otherwise the output is printed FALSE.

本教程使用了四种不同的编程语言（C、C++、JAVA 和 Python）执行子表搜索。

The sublist search is executed in four different programming languages in this tutorial – C, C++, JAVA and Python.