- 算法设计与分析
- 家
- 算法基础知识
- DAA - 简介
- DAA - 算法分析
- DAA-分析方法
- 渐近符号和先验分析
- 时间复杂度
- 马斯特定理
- DAA - 空间复杂性
- 分而治之
- DAA-分而治之
- DAA - 最大最小问题
- DAA-归并排序
- DAA-二分查找
- 施特拉森矩阵乘法
- 唐叶算法
- 河内塔
- 贪心算法
- DAA-贪婪法
- 旅行商问题
- Prim 的最小生成树
- 克鲁斯卡尔的最小生成树
- Dijkstra 的最短路径算法
- 地图着色算法
- DAA-分数背包
- DAA - 带截止日期的作业排序
- DAA - 最佳合并模式
- 动态规划
- DAA-动态规划
- 矩阵链乘法
- 弗洛伊德·沃歇尔算法
- DAA - 0-1 背包
- 最长公共子序列
- 旅行商问题| 动态规划
- 随机算法
- 随机算法
- 随机快速排序
- 卡格的最低削减
- 费舍尔-耶茨洗牌
- 近似算法
- 近似算法
- 顶点覆盖问题
- 设置封面问题
- 旅行推销员近似算法
- 排序技巧
- DAA-快速排序
- DAA-冒泡排序
- DAA——插入排序
- DAA-选择排序
- DAA——希尔排序
- DAA-堆排序
- DAA——桶排序
- DAA——计数排序
- DAA - 基数排序
- 搜索技巧
- 搜索技术介绍
- DAA - 线性搜索
- DAA-二分查找
- DAA - 插值搜索
- DAA - 跳转搜索
- DAA - 指数搜索
- DAA - 斐波那契搜索
- DAA - 子列表搜索
- DAA-哈希表
- 图论
- DAA-最短路径
- DAA - 多级图
- 最优成本二叉搜索树
- 堆算法
- DAA-二叉堆
- DAA-插入法
- DAA-Heapify 方法
- DAA-提取方法
- 复杂性理论
- 确定性计算与非确定性计算
- DAA-最大派系
- DAA - 顶点覆盖
- DAA - P 级和 NP 级
- DAA-库克定理
- NP 硬课程和 NP 完全课程
- DAA - 爬山算法
- DAA 有用资源
- DAA - 快速指南
- DAA - 有用的资源
- DAA - 讨论
设计与分析 - 子列表搜索
到目前为止,在本教程中,我们只了解了如何按元素的连续顺序搜索一个元素。但是子列表搜索算法提供了在另一个链表中搜索一个链表的过程。它的工作原理与任何简单的模式匹配算法类似,其目的是确定一个列表是否存在于另一个列表中。
该算法遍历链表,其中一个列表的第一个元素与第二个列表的第一个元素进行比较;如果未找到匹配项,则将第一个列表的第二个元素与第二个列表的第一个元素进行比较。此过程将持续进行,直到找到匹配项或到达列表末尾。
例如,考虑两个值为 {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 是第二个链表中存在的元素数量。
例子
假设我们有两个链表,其元素如下 -
List 1 = {2, 5, 3, 3, 6, 7, 0} List 2 = {6, 7, 0}
使用子列表搜索,我们需要找出列表 2 是否存在于列表 1 中。
步骤1
将 List 2 的第一个元素与 List 1 的第一个元素进行比较。不匹配,因此 List 1 中的指针移动到其中的下一个内存地址。
第2步
在此步骤中,将列表 1 的第二个元素与列表 2 的第一个元素进行比较。不匹配,因此列表 1 中的指针移动到下一个内存地址。
步骤3
现在将列表 1 中的第三个元素与列表 2 中的第一个元素进行比较。由于不匹配,因此列表 1 中的指针向前移动。
步骤4
现在,将列表 1 中的第四个元素与列表 2 中的第一个元素进行比较。由于不匹配,因此列表 1 中的指针向前移动。
步骤5
现在,将 List 1 中的第五个元素与 List 2 中的第一个元素进行比较。由于匹配,因此 List 1 和 List 2 中的指针都向前移动。
步骤6
将 List 1 中的第六个元素与 List 2 中的第二个元素进行比较。由于它也是匹配的,因此 List 1 和 List 2 中的指针都向前移动。
步骤7
将List 1中的第七个元素与List 2中的第三个元素进行比较。由于也匹配,因此证明List 2是List 1的子列表。
输出返回 TRUE。
执行
在子列表搜索实现中,在C语言中首先使用struct关键字创建链表,在C++、JAVA和Python语言中作为对象创建。检查这些链表是否不为空;然后对元素进行逐一线性比较以找到匹配项。如果第二个链表以相同的顺序出现在第一个链表中,则输出返回TRUE;否则输出将被打印FALSE。
在本教程中,子列表搜索以四种不同的编程语言执行: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); if (sublist_search(list, sub_list)) printf("TRUE"); else printf("FALSE"); return 0; }
输出
TRUE
#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); if (sublist_search(list, sub_list)) cout << "TRUE"; else cout << "FALSE"; return 0; }
输出
TRUE
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); if (sublist_search(list, sub_list)) System.out.println("TRUE"); else System.out.println("FALSE"); } }
输出
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) if sublist_search(node_sublist, node_list): print("TRUE") else: print("FALSE")
输出
TRUE