子列表搜索算法

更新于 2025/10/16 16:21:06

子列表搜索算法
实现

到目前为止，在本教程中，我们只了解了如何按元素的顺序搜索单个元素。但子列表搜索算法提供了一种在一个链表中搜索另一个链表的方法。它的工作原理与任何简单的模式匹配算法类似，其目的是确定一个列表是否存在于另一个列表中。

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

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

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

子列表搜索算法

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

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

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

步骤 2 − 检查链表的起始条件 −

如果两个链表均为空，则输出 true。
如果第二个列表不为空但第一个列表为空，则返回 false。
如果第一个列表不为空但第二个列表为空，则返回 false。

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

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

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

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

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

伪代码

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

分析

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

示例

假设我们有两个链表，元素个数为 −

列表 1 = {2, 5, 3, 3, 6, 7, 0}
列表 2 = {6, 7, 0}

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

步骤 1

比较列表的第一个元素比较 List 2 中的第一个元素与 List 1 中的第一个元素。由于不匹配，List 1 中的指针移动到下一个内存地址。

步骤 2

在此步骤中，将 List 1 的第二个元素与 List 2 的第一个元素进行比较。由于不匹配，因此 List 1 中的指针移动到下一个内存地址。

步骤 3

现在将 List 1 中的第三个元素与 List 2 中的第一个元素进行比较。由于不匹配，List 1 中的指针移动到下一个内存地址。向前移动。

步骤 4

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

步骤 5

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

步骤 6

将列表 1 中的第六个元素与列表 2 中的第二个元素进行比较。由于它也匹配，因此列表 1 和列表 2 中的指针都向前移动。

步骤 7

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

输出结果为 TRUE。

实现

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

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

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct Node {
   int data;
   struct Node* next;
};
struct Node *newNode(int key){
   struct Node *val = (struct Node*)malloc(sizeof(struct Node));;
   val-> data= key;
   val->next = NULL;
   return val;
}
bool sublist_search(struct Node* list_ptr, struct Node* sub_ptr){
   struct Node* ptr1 = list_ptr, *ptr2 = sub_ptr;
   if (list_ptr == NULL && sub_ptr == NULL)
      return true;
   if ( sub_ptr == NULL || (sub_ptr != NULL && list_ptr == NULL))
      return false;
   while (list_ptr != NULL) {
      ptr1 = list_ptr;
      while (ptr2 != NULL) {
         if (ptr1 == NULL)
            return false;
         else if (ptr2->data == ptr1->data) {
            ptr2 = ptr2->next;
            ptr1 = ptr1->next;
         } else
            break;
      }
      if (ptr2 == NULL)
         return true;
      ptr2 = sub_ptr;
      list_ptr = list_ptr->next;
   }
   return false;
}
int main(){
   struct Node *list = newNode(2);
   list->next = newNode(5);
   list->next->next = newNode(3);
   list->next->next->next = newNode(3);
   list->next->next->next->next = newNode(6);
   list->next->next->next->next->next = newNode(7);
   list->next->next->next->next->next->next = newNode(0);
   struct Node *sub_list = newNode(3);
   sub_list->next = newNode(6);
   sub_list->next->next = newNode(7);
   bool res = sublist_search(list, sub_list);
   if (res)
      printf("Is the sublist present in the list? %d" , res);
}

输出

Is the sublist present in the list? 1

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   Node* next;
};
Node *newNode(int key){
   Node *val = new Node;
   val-> data= key;
   val->next = NULL;
   return val;
}
bool sublist_search(Node* list_ptr, Node* sub_ptr){
   Node* ptr1 = list_ptr, *ptr2 = sub_ptr;
   if (list_ptr == NULL && sub_ptr == NULL)
      return true;
   if ( sub_ptr == NULL || (sub_ptr != NULL && list_ptr == NULL))
      return false;
   while (list_ptr != NULL) {
      ptr1 = list_ptr;
      while (ptr2 != NULL) {
         if (ptr1 == NULL)
            return false;
         else if (ptr2->data == ptr1->data) {
            ptr2 = ptr2->next;
            ptr1 = ptr1->next;
         } else
            break;
      }
      if (ptr2 == NULL)
         return true;
      ptr2 = sub_ptr;
      list_ptr = list_ptr->next;
   }
   return false;
}
int main(){
   Node *list = newNode(2);
   list->next = newNode(5);
   list->next->next = newNode(3);
   list->next->next->next = newNode(3);
   list->next->next->next->next = newNode(6);
   list->next->next->next->next->next = newNode(7);
   list->next->next->next->next->next->next = newNode(0);
   Node *sub_list = newNode(3);
   sub_list->next = newNode(6);
   sub_list->next->next = newNode(7);
   bool res = sublist_search(list, sub_list);
   if (res)
      cout << "Is the sublist present in the list? "<<res;
}

输出

Is the sublist present in the list? 1

import java.io.*;
public class SublistSearch {
   public static class Node {
      int data;
      Node next;
   }
   public static Node newNode(int key) {
      Node val = new Node();
      val.data= key;
      val.next = null;
      return val;
   }
   public static boolean sublist_search(Node list_ptr, Node sub_ptr) {
      Node ptr1 = list_ptr, ptr2 = sub_ptr;
      if (list_ptr == null && sub_ptr == null)
         return true;
      if ( sub_ptr == null || (sub_ptr != null && list_ptr == null))
         return false;
      while (list_ptr != null) {
         ptr1 = list_ptr;
         while (ptr2 != null) {
            if (ptr1 == null)
               return false;
            else if (ptr2.data == ptr1.data) {
               ptr2 = ptr2.next;
               ptr1 = ptr1.next;
            } else
               break;
         }
         if (ptr2 == null)
            return true;
         ptr2 = sub_ptr;
         list_ptr = list_ptr.next;
      }
      return false;
   }
   public static void main(String args[]) {
      Node list = newNode(2);
      list.next = newNode(5);
      list.next.next = newNode(3);
      list.next.next.next = newNode(3);
      list.next.next.next.next = newNode(6);
      list.next.next.next.next.next = newNode(7);
      list.next.next.next.next.next.next = newNode(0);
      Node sub_list = newNode(3);
      sub_list.next = newNode(6);
      sub_list.next.next = newNode(7);
	  boolean res = sublist_search(list, sub_list);
      if (res){
	     System.out.print("Is the sublist present in the list? " + res);
	  } 
   }
}

输出

Is the sublist present in the list? true

class Node:
   def __init__(self, val = 0):
      self.val = val
      self.next = None
def sublist_search(sub_ptr, list_ptr):
   if not sub_ptr and not list_ptr:
      return True
   if not sub_ptr or not list_ptr:
      return False
   ptr1 = sub_ptr
   ptr2 = list_ptr
   while ptr2:
      ptr2 = list_ptr
      while ptr1:
         if not ptr2:
            return False
         elif ptr1.val == ptr2.val:
            ptr1 = ptr1.next
            ptr2 = ptr2.next
         else:
            break
      if not ptr1:
         return True
      ptr1 = sub_ptr
      list_ptr = list_ptr.next
   return False
node_sublist = Node(3)
node_sublist.next = Node(3)
node_sublist.next.next = Node(6)
node_list = Node(2)
node_list.next = Node(5)
node_list.next.next = Node(3)
node_list.next.next.next = Node(3)
node_list.next.next.next.next = Node(6)
node_list.next.next.next.next.next = Node(7)
node_list.next.next.next.next.next.next = Node(0)
res = sublist_search(node_sublist, node_list)
if res == True:
   print("Is the sublist present in the list? ", res)

输出

Is the sublist present in the list?  True

数据结构和算法

数据结构

链接列表

堆栈 &队列

搜索算法

排序算法

图形数据结构

树数据结构

递归

分而治之

贪婪算法

动态规划

近似算法

随机算法

DSA 有用资源

子列表搜索算法

子列表搜索算法

伪代码

分析

示例

实现

输出

输出

输出

输出

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！