．[題目分析] 本題也是模式匹配問題應先找出鏈表L在鏈表L中的出現然後將L中的L倒置過來設L在L中出現時第一個字母結點的前驅的指針為p最後一個字母結點在L中為q所指結點的前驅則在保存p後繼結點指針(s)的情況下執行p>next=q之後將s到q結點的前驅依次插入到p結點之後實現了L在L中的倒置
LinkedList PatternInvert(LinkedList LL)∥L和L均是帶頭結點的單鏈表數據結點的數據域均為一個字符本算法將L中與L中數據域相同的連續結點的順序完全倒置過來
{p=L;∥p是每趟匹配時L中的起始結點前驅的指針
q=L>next;∥q是L中的工作指針
s=L>next;∥s是L中的工作指針
while(p!=null && s!=null)
if(q>data==s>data){q=q>next;s=s>next;}∥對應字母相等指針後移
else {p=p>next;q=p>next;s=L>next;}∥失配時L起始結點後移L從首結點開始
if(s==null)∥匹配成功這時p為L中與L中首字母結點相同數據域結點的前驅q為L中與L最後一個結點相同數據域結點的後繼
{r=p>next;∥r為L的工作指針初始指向匹配的首字母結點
p>next=q;∥將p與q結點的鏈接
while(r!=q);∥逐結點倒置
{s=r>next;∥暫存r的後繼
r>next=p>next;∥將r所指結點倒置
p>next=r;
r=s;∥恢復r為當前結點
}
}
else printf(L並未在L中出現);
}∥算法結束
[算法討論] 本算法只討論了L在L至多出現一次(可能沒出現)沒考慮在L中多次出現的情況若考慮多次出現可在上面算法找到第一次出現後的q結點作L中下次比較的第一字母結點讀者可自行完善之
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23330.html
