数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
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的子序列。
}∥算法结束。