数据结构 | 每日一练（61）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．L1 与 L2 分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。设计把 L1 中与L2 中数据相同的连续结点顺序完全倒置的算法。

例：

类似本题的另外叙述有：

(1) 知 L 为链表的头结点地址，表中共有 m(m>3)个结点，从表中第 i 个结点(1<i<m)起到第 m 个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。

正确答案

ps：||代表注释

1．[题目分析] 本题也是模式匹配问题，应先找出链表L2在链表L1中的出现，然后将L1中的L2倒置过来。设L2在L1中出现时第一个字母结点的前驱的指针为p，最后一个字母结点在L1中为q所指结点的前驱，则在保存p后继结点指针(s)的情况下，执行p->next=q。之后将s到q结点的前驱依次插入到p结点之后，实现了L2在L1中的倒置。

LinkedList PatternInvert（LinkedList L1，L2）

∥L1和L2均是带头结点的单链表，数据结点的数据域均为一个字符。本算法将L1中与L2中数据域相同的连续结点的顺序完全倒置过来。

{p=L1； ∥p是每趟匹配时L1中的起始结点前驱的指针。

q=L1->next； ∥q是L1中的工作指针。

s=L2->next； ∥s是L2中的工作指针。

while（p!=null && s!=null）

if（q->data==s->data）{q=q->next;s=s->next;} ∥对应字母相等，指针后移。

else {p=p->next；q=p->next；s=L2->next；} ∥失配时，L1起始结点后移，L2从首结点开始。

if（s==null）∥匹配成功，这时p为L1中与L2中首字母结点相同数据域结点的前驱，q为L1中与L2最后一个结点相同数据域结点的后继。

{r=p->next； ∥r为L1的工作指针，初始指向匹配的首字母结点。

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（“L2并未在L1中出现”）；

} ∥算法结束。

[算法讨论] 本算法只讨论了L2在L1至多出现一次（可能没出现），没考虑在L1中多次出现的情况。若考虑多次出现，可在上面算法找到第一次出现后的q结点作L1中下次比较的第一字母结点，读者可自行完善之。

类似本题的另外叙述题的解答：

（1）[题目分析] 本题应先查找第i个结点，记下第i个结点的指针。然后从第i+1个结点起，直至第m（1<i<m）个结点止，依次插入到第i-1个结点之后。最后将暂存的第i个结点的指针指向第m结点，形成新的循环链表，结束了倒置算法。

LinkedList PatternInvert1（LinkedList L， int i，m）

∥L是有m个结点的链表的头结点的指针。表中从第i（1<i<m）个结点到第m个结点构成循环部分链表，本算法将这部分循环链表倒置。

{ if（i<1|| i>=m || m<4）{printf（“%d,%d参数错误\n”,i，m）；exit（0）；}

p=L->next->next； ∥p是工作指针，初始指向第二结点（已假定i>1）。

pre=L->next； ∥pre是前驱结点指针，最终指向第i-1个结点。

j=1； ∥计数器

while（j<i-1） ∥查找第i个结点。

{j++；pre=p；p=p->next；}∥查找结束，p指向第i个结点。

q=p； ∥暂存第i个结点的指针。

p=p->next； ∥p指向第i+1个结点，准备逆置。

j+=2； ∥上面 while循环结束时，j=i-1，现从第i+1结点开始逆置。

while（j<=m）

{r=p->next； ∥暂存p的后继结点。

p->next=pre->next；∥逆置p结点。

pre->next=p；

p=r； ∥p恢复为当前待逆置结点。

j++； ∥计数器增1。

}

q->next=pre->next；∥将原第i个结点的后继指针指向原第m个结点。

[算法讨论] 算法中未深入讨论i，m，j的合法性，因题目的条件是m>3且1<i<m。因此控制循环并未用指针判断（如一般情况下的p!=null），结束循环也未用指针判断。注意最后一句q->next=pre->next，实现了从原第i个结点到原第m个结点的循环。最后pre->next正是指向原第m个结点，不可用p->next代替pre->next。

-end-