．[題目分析] 本題實質上是一個模式匹配問題這裡匹配的元素是整數而不是字符因兩整數序列已存入兩個鏈表中操作從兩鏈表的第一個結點開始若對應數據相等則後移指針;若對應數據不等則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的子序列
}∥算法結束
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23329.html
