数据结构考研分类复习真题 第二章 答案[38]

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

int Pattern(LinkedList AB)∥A和B分别是数据域为整数的单链表本算法判断B是否是A的子序列如是返回;否则返回表示失败

{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();∥B是A的子序列

else return();∥B不是A的子序列

}∥算法结束

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []