Data Structures Algorithms 简明教程

Sublist Search Algorithm

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

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

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

sublist search

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

Sublist Search Algorithm

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

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

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

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

  1. 如果两个链表都为空,则输出返回 true。

  2. 如果第二个列表不为空,但第一个列表为空,则我们返回 false。

  3. 如果第一个列表不为空,但第二个列表为空,则我们返回 false。

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

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

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

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

*步骤 7 *− 如果找到输出,则返回 TRUE,否则返回 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 是第二个链表中存在的元素数量。

Example

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

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

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

sublist search diagram

Step 1

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

compare lists

Step 2

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

moves next memory address

Step 3

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

List 1 moves forward

Step 4

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

pointer moved forward

Step 5

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

List1 List2 move forward

Step 6

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

sixth element compare

Step 7

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

seventh element compare

输出返回真。

Implementation

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

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