数据结构 | 每日一练（60）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．两个整数序列 A=a1,a2,a3,…,am 和 B=b1,b2,b3,…,bn 已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的子序列。

正确答案

ps：||代表注释

1．[题目分析] 本题实质上是一个模式匹配问题，这里匹配的元素是整数而不是字符。因两整数序列已存入两个链表中，操作从两链表的第一个结点开始，若对应数据相等，则后移指针；若对应数据不等，则A链表从上次开始比较结点的后继开始，B链表仍从第一结点开始比较，直到B链表到尾表示匹配成功。A链表到尾B链表未到尾表示失败。操作中应记住A链表每次的开始结点，以便下趟匹配时好从其后继开始。

int Pattern（LinkedList A，B）∥A和B分别是数据域为整数的单链表，本算法判断B是否是A的子序列。如是，返回1；否则，返回0表示失败。

{p=A； ∥p为A链表的工作指针，本题假定A和B均无头结点。

pre=p； ∥pre记住每趟比较中A链表的开始结点。

q=B； ∥q是B链表的工作指针。

while（p && q）

if（p->data==q->data） {p=p->next；q=q->next；}

else{pre=pre->next；p=pre； ∥A链表新的开始比较结点。

q=B；} ∥q从B链表第一结点开始。

if（q==null） return（1）； ∥B是A的子序列。

else return（0）； ∥B不是A的子序列。

}∥算法结束。