BB2-判断链表B是否是链表A的连续子序列
代码实现
| C |
|---|
| /**
* 判断链表B是否是链表A的连续子序列
* @param A 链表A（母链表）
* @param B 链表B（子链表）
* @return B是A的连续子序列返回true，否则返回false
*/
bool find(LinkList A, LinkList B) {
// 边界条件检查
if (A == NULL || B == NULL) {
return false;
}
// 空链表处理：空链表被认为是任何链表的子序列
if (B->next == NULL) {
return true;
}
// 如果A为空但B不为空，则B不可能是A的子序列
if (A->next == NULL) {
return false;
}
// pos指向A中当前尝试匹配的起始位置
LinkList pos = A->next;
// 在A的每个可能起始位置尝试匹配B
while (pos != NULL) {
LinkList p1 = pos; // A的当前比较位置
LinkList p2 = B->next; // B的当前比较位置
// 在当前位置尝试匹配整个B链表
while (p1 != NULL && p2 != NULL) {
if (p1->data == p2->data) {
// 数据匹配，继续比较下一个结点
p1 = p1->next;
p2 = p2->next;
} else {
// 数据不匹配，跳出内层循环
break;
}
}
// 检查是否完全匹配B
if (p2 == NULL) {
// B已完全匹配，说明B是A的连续子序列
return true;
}
// 当前位置匹配失败，尝试A的下一个起始位置
pos = pos->next;
}
// 遍历完A的所有可能位置都未找到匹配
return false;
}
/**
* 优化版本：添加长度预检查
* @param A 链表A
* @param B 链表B
* @return B是A的连续子序列返回true，否则返回false
*/
bool find_optimized(LinkList A, LinkList B) {
if (A == NULL || B == NULL) {
return false;
}
if (B->next == NULL) {
return true; // 空链表是任何链表的子序列
}
if (A->next == NULL) {
return false; // A为空但B不为空
}
// 计算两个链表的长度
int lenA = 0, lenB = 0;
LinkList temp;
// 计算A的长度
for (temp = A->next; temp != NULL; temp = temp->next) {
lenA++;
}
// 计算B的长度
for (temp = B->next; temp != NULL; temp = temp->next) {
lenB++;
}
// 如果B比A长，不可能是子序列
if (lenB > lenA) {
return false;
}
// 在A中尝试匹配B
LinkList pos = A->next;
int max_start_pos = lenA - lenB; // 最大起始位置
for (int start_pos = 0; start_pos <= max_start_pos && pos != NULL; start_pos++) {
LinkList p1 = pos;
LinkList p2 = B->next;
// 尝试匹配
while (p1 != NULL && p2 != NULL && p1->data == p2->data) {
p1 = p1->next;
p2 = p2->next;
}
// 检查是否完全匹配
if (p2 == NULL) {
return true;
}
pos = pos->next;
}
return false;
}
/**
* 获取链表长度
* @param L 链表头指针
* @return 链表长度
*/
int get_length(LinkList L) {
if (L == NULL) return 0;
int length = 0;
LinkList p = L->next;
while (p != NULL) {
length++;
p = p->next;
}
return length;
}
/**
* 打印链表内容
* @param L 链表头指针
*/
void print_list(LinkList L) {
if (L == NULL || L->next == NULL) {
printf("空链表\n");
return;
}
LinkList p = L->next;
printf("链表内容：");
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
|
算法执行流程图解
匹配成功示例：
| Text Only |
|---|
| 链表A：[ ]→[1]→[2]→[3]→[4]→[5]→NULL
链表B：[ ]→[2]→[3]→[4]→NULL
执行过程：
pos=[1]: p1=[1], p2=[2] → 1≠2，匹配失败
pos=[2]
pos=[2]: p1=[2], p2=[2] → 匹配，p1=[3], p2=[3]
p1=[3], p2=[3] → 匹配，p1=[4], p2=[4]
p1=[4], p2=[4] → 匹配，p1=[5], p2=NULL
p2==NULL → 完全匹配，返回true
|
匹配失败示例：
| Text Only |
|---|
| 链表A：[ ]→[1]→[2]→[3]→[4]→[5]→NULL
链表B：[ ]→[2]→[4]→[3]→NULL
执行过程：
pos=[1]: p1=[1], p2=[2] → 1≠2，匹配失败
pos=[2]
pos=[2]: p1=[2], p2=[2] → 匹配，p1=[3], p2=[4]
p1=[3], p2=[4] → 3≠4，匹配失败
pos=[3]
pos=[3]: p1=[3], p2=[2] → 3≠2，匹配失败
pos=[4]
...以此类推，最终返回false
|
算法状态变化图解
| Text Only |
|---|
| 链表A：[ ]→[a]→[b]→[c]→[d]→[e]→NULL
链表B：[ ]→[b]→[c]→[d]→NULL
匹配过程：
起始位置1：[a] vs [b] → 失败
起始位置2：[b] vs [b] → 继续
[c] vs [c] → 继续
[d] vs [d] → 继续
NULL vs NULL → 成功
|
复杂度分析
时间复杂度：O(m×n)
- 最坏情况：O(m×n)，其中m是链表A的长度，n是链表B的长度
- 最好情况：O(m)，第一个位置就匹配失败
- 平均情况：O(m×n)，但在实际应用中通常表现较好
- 举例：A长度1000，B长度10，最坏情况下需要比较10000次
空间复杂度：O(1)
- 辅助变量：只使用常数个指针变量（pos, p1, p2等）
- 无额外存储：不需要额外的数据结构
- 总体空间复杂度：O(1)
算法优化版本
| C |
|---|
| /**
* KMP算法在链表中的应用（理论）
*/
typedef struct {
LinkList pattern;
int* next; // 部分匹配表
} KMP_LinkList;
bool kmp_find(LinkList text, LinkList pattern) {
// 实现较为复杂，需要将KMP算法适配到链表结构
// 这里给出基本思路
if (text == NULL || pattern == NULL) return false;
if (pattern->next == NULL) return true;
if (text->next == NULL) return false;
// 1. 计算pattern的next数组
// 2. 在text中进行KMP匹配
// 3. 利用next数组避免重复比较
return false; // 简化版本
}
/**
* 带位置信息的匹配函数
* @param A 链表A
* @param B 链表B
* @param position 匹配位置（输出参数）
* @return 是否匹配成功
*/
bool find_with_position(LinkList A, LinkList B, int* position) {
if (A == NULL || B == NULL || position == NULL) {
return false;
}
if (B->next == NULL) {
*position = 0;
return true;
}
if (A->next == NULL) {
return false;
}
int pos_index = 0;
LinkList pos = A->next;
while (pos != NULL) {
LinkList p1 = pos;
LinkList p2 = B->next;
while (p1 != NULL && p2 != NULL && p1->data == p2->data) {
p1 = p1->next;
p2 = p2->next;
}
if (p2 == NULL) {
*position = pos_index;
return true;
}
pos = pos->next;
pos_index++;
}
return false;
}
|
错误处理完善版本
| C |
|---|
| /**
* 安全版本：添加完整的错误处理
*/
bool find_safe(LinkList A, LinkList B) {
// 参数验证
if (A == NULL) {
printf("错误：链表A为空指针\n");
return false;
}
if (B == NULL) {
printf("错误：链表B为空指针\n");
return false;
}
// 空链表处理
if (B->next == NULL) {
printf("链表B为空，认为是任何链表的子序列\n");
return true;
}
if (A->next == NULL) {
printf("链表A为空，非空链表B不可能是其子序列\n");
return false;
}
// 匹配过程
LinkList pos = A->next;
int start_pos = 0;
while (pos != NULL) {
LinkList p1 = pos;
LinkList p2 = B->next;
int match_length = 0;
// 尝试匹配
while (p1 != NULL && p2 != NULL) {
if (p1->data == p2->data) {
p1 = p1->next;
p2 = p2->next;
match_length++;
} else {
break;
}
}
// 检查是否完全匹配
if (p2 == NULL) {
printf("在链表A的第%d个位置找到匹配\n", start_pos);
return true;
} else if (match_length > 0) {
printf("在位置%d部分匹配了%d个元素\n", start_pos, match_length);
}
pos = pos->next;
start_pos++;
}
printf("未找到匹配的子序列\n");
return false;
}
|
性能测试对比
| C |
|---|
| /**
* 性能测试函数
*/
void performance_test() {
// 创建测试链表
LinkList A = create_test_list(1000); // 长度1000的链表
LinkList B = create_test_sublist(10); // 长度10的子链表
clock_t start = clock();
for (int i = 0; i < 1000; i++) {
find(A, B);
}
clock_t naive_time = clock() - start;
start = clock();
for (int i = 0; i < 1000; i++) {
find_optimized(A, B);
}
clock_t optimized_time = clock() - start;
printf("朴素算法耗时: %ld\n", naive_time);
printf("优化算法耗时: %ld\n", optimized_time);
// 释放内存
destroy_list(A);
destroy_list(B);
}
|
实际应用示例
| C |
|---|
| /**
* 实用函数：在链表序列中查找模式
*/
typedef struct {
int id;
char name[50];
} Student;
typedef struct StudentNode {
Student data;
struct StudentNode* next;
} StudentNode, *StudentList;
bool find_student_sequence(StudentList students, Student pattern[], int pattern_len) {
if (students == NULL || pattern_len <= 0) return false;
StudentNode* pos = students->next;
while (pos != NULL) {
StudentNode* p1 = pos;
int i = 0;
while (p1 != NULL && i < pattern_len) {
if (p1->data.id == pattern[i].id) {
p1 = p1->next;
i++;
} else {
break;
}
}
if (i == pattern_len) {
return true;
}
pos = pos->next;
}
return false;
}
/**
* 多个子序列搜索
*/
int find_multiple_subsequences(LinkList A, LinkList patterns[], int pattern_count) {
for (int i = 0; i < pattern_count; i++) {
if (find(A, patterns[i])) {
printf("找到第%d个子序列\n", i + 1);
return i;
}
}
return -1;
}
|
算法特点
核心思想：
在链表A的每个可能起始位置尝试匹配整个链表B，一旦发现不匹配就移动到下一个位置重新开始。
关键技术：
1. 双重遍历：外层遍历A的起始位置，内层进行链表匹配
2. 提前终止：发现不匹配立即跳出内层循环
3. 指针操作：正确处理链表指针的移动和比较
优势：
- 实现简单：逻辑清晰，易于理解和实现
- 正确性高：算法简单，不容易出错
- 适用广泛：适用于各种数据类型的链表
局限性：
- 效率较低：最坏情况下时间复杂度为O(m×n)
- 重复比较：可能对同一结点进行多次比较
- 不适用于大型链表：对于很长的链表效率较差
应用场景：
- 链表数据的模式匹配
- 生物信息学中的序列匹配（DNA、蛋白质序列）
- 日志分析中的模式查找
- 网络数据包序列分析
- 游戏开发中的行为序列检测
算法改进方向：
1. KMP算法适配：避免重复比较
2. 哈希优化：使用滚动哈希快速筛选
3. 并行处理：对大型链表进行并行匹配
这种链表子序列匹配算法是链表操作中的经典问题，在实际应用中具有重要的实用价值。