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

数据结构

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

——老子

1

每日一练

1．已知三个带头结点的线性链表 A、B 和 C 中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对 A 表进行如下操作：使操作后的链表 A 中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为 O（m+n+p），其中 m、n

和 p 分别为三个表的长度。

正确答案

PS：||代表注释

1．[题目分析] 留下三个链表中公共数据，首先查找两表A和B中公共数据，再去C中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度O（m+n+p），在查找每个链表时，指针不能回溯。

LinkedList Common（LinkedList A，B，C）∥A，B和C是三个带头结点且结点元素值非递减排列的有序表。本算法使A表仅留下三个表均包含的结点，且结点值不重复，释放所有结点。

{pa=A->next；pb=B->next；pc=C->next；∥pa,pb和pc分别是A,B和C三个表的工作指针。

pre=A；∥pre是A表中当前结点的前驱结点的指针。

while（pa && pb && pc）∥当A,B和C表均不空时，查找三表共同元素

{ while（pa && pb）

if（pa->data<pb->data）{u=pa；pa=pa->next；free（u）；}∥结点元素值小时，后移指针。

else if（pa->data> pb->data）pb=pb->next；

else if (pa && pb) ∥处理A和B表元素值相等的结点

{ while（pc && pc->data<pa->data）pc=pc->next；

if(pc)

{ if（pc->data>pa->data）∥pc当前结点值与pa当前结点值不等,pa后移指针。

{u=pa；pa=pa->next；free（u）；}

else ∥pc，pa和pb对应结点元素值相等。

{ if(pre==A){ pre->next=pa；pre=pa；pa=pa->next} ∥结果表中第一个结点。

else if(pre->data==pa->data) ∥（处理）重复结点不链入A表

{u=pa；pa=pa->next；free（u）；}

else {pre->next=pa；pre=pa；pa=pa->next；}∥将新结点链入A表。

pb=pb->next；pc=pc->next；∥链表的工作指针后移。

} }∥ else pc，pa和pb对应结点元素值相等

if（pa==null）pre->next=null；∥原A表已到尾,置新A表表尾

else ∥处理原A表未到尾而B或C到尾的情况

{pre->next=null； ∥置A表表尾标记

while（pa!=null） ∥删除原A表剩余元素。

{u=pa；pa=pa->next；free（u）；}

[算法讨论] 算法中A表、B表和C表均从头到尾（严格说B、C中最多一个到尾）遍历一遍，算法时间复杂度符合O（m+n+p）。算法主要由 while（pa && pb && pc）控制。三表有一个到尾则结束循环。算法中查到A表与B表和C表的公共元素后，又分三种情况处理：一是三表中第一个公共元素值相等的结点；第二种情况是，尽管不是第一结点，但与前驱结点元素值相同，不能成为结果表中的结点；第三种情况是新结点与前驱结点元素值不同，应链入结果表中，前驱指针也移至当前结点，以便与以后元素值相同的公共结点进行比较。算法最后要给新A表置结尾标记，同时若原A表没到尾，还应释放剩余结点所占的存储空间。