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

．[题目分析] 本题也是模式匹配问题应先找出链表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中下次比较的第一字母结点读者可自行完善之

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