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

数据结构

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

——老子

1

每日一练

1． 带头结点且头指针为 ha 和 hb 的两线性表 A 和 B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法求 A 和 B 的并集 AUB。要求该并集中的元素仍保持递增有序。且要利用 A 和 B 的原有结点空间。

类似本题的另外叙述有：

(1) 已知递增有序的两个单链表 A，B 分别存储了一个集合。设计算法实现求两个集合的并集的运算 A:=A∪B

（2）已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。编一函数，求 A 与 B 的交集，并存放于A 链表中。

（3）设有两个从小到大排序的带头结点的有序链表。试编写求这两个链表交运算的算法（即 L1∩L2）。要求结果链表仍是从小到大排序，但无重复元素。

（4）己知两个线性表 A ，B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出 A 与 B 的交集 C，要求 C 另开辟存储空间，要求 C 同样以元素值的递增序的单链表形式存贮。

（5）已知递增有序的单链表 A,B 和 C 分别存储了一个集合，设计算法实现 A：=A∪（B∩C），并使求解结构 A 仍保持递增。要求算法的时间复杂度为 O(|A|+|B|+|C|)。其中,|A|为集合 A 的元素个数。

正确答案

ps：||代表注释

1．[题目分析]本组题有6个，本质上都是链表的合并操作，合并中有各种条件。与前组题不同的是，叙述上是用线性表代表集合，而操作则是求集合的并、交、差（A∪B，A∩B，A-B）等。本题与上面1．（2）基本相同，不同之处1．（2）中链表是“非递减有序”，（可能包含相等元素），本题是元素“递增有序”（不准有相同元素）。因此两表中合并时，如有元素值相等元素，则应删掉一个。

LinkedList Union(LinkedList ha,hb)∥线性表A和B代表两个集合，以链式存储结构存储，元素递增有序。ha和hb分别是其链表的头指针。本算法求A和B的并集A∪B，仍用线性表表示，结果链表元素也是递增有序。

{ pa=ha->next;pb=hb->next;∥设工作指针pa和pb。

pc=ha;∥pc为结果链表当前结点的前驱指针。

while(pa&&pb)

if(pa->data<pb->data)

{pc->next=pa;pc=pa;pa=pa->next;}

else if(pa->data>pb->data)

{pc->next=pb;pc=pb;pb=pb->next;}

else∥处理pa->data=pb->data.

{pc->next=pa;pc=pa;pa=pa->next;

u=pb;pb=pb->next;free(u);}

if(pa) pc->next=pa;∥ 若ha表未空，则链入结果表。

else pc->next=pb;∥若hb表未空，则链入结果表。

free(hb); ∥释放hb头结点

return(ha);

}∥算法Union结束。

与本题类似的其它几个题解答如下：

(1) 解答完全同上2。

(2) 本题是求交集，即只有同时出现在两集合中的元素才出现在结果表中。其核心语句段如下：

pa=la->next;pb=lb->next;∥设工作指针pa和pb；

pc=la;∥结果表中当前合并结点的前驱的指针。

while(pa&&pb)

if(pa->data==pb->data)∥交集并入结果表中。

{ pc->next=pa;pc=pa;pa=pa->next;

u=pb;pb=pb->next;free(u);}

else if(pa->data<pb->data) {u=pa;pa=pa->next;free(u);}

else {u=pb; pb=pb->next; free(u);}

while(pa){ u=pa; pa=pa->next; free(u);}∥ 释放结点空间

while(pb) {u=pb; pb=pb->next; free(u);}∥释放结点空间

pc->next=null;∥置链表尾标记。

free(lb); ∥注： 本算法中也可对B表不作释放空间的处理

（3）本题基本与（2）相同，但要求无重复元素，故在算法中，待合并结点数据要与其前驱比较，只有在与

前驱数据不同时才并入链表。其核心语句段如下。

pa=L1->next;pb=L2->next;∥pa、pb是两链表的工作指针。

pc=L1;∥L1作结果链表的头指针。

while(pa&&pb)

if(pa->data<pb->data) {u=pa;pa=pa->next;free(u);}∥删除L1表多余元素

else if (pa->data>pb->data) pb=pb->next; ∥pb指针后移

else ∥处理交集元素

{ if(pc==L1) {pc->next=pa;pc=pa;pa=pa->next;} ∥处理第一个相等的元素。

else if(pc->data==pa->data){ u=pa;pa=pa->next;free(u);} ∥重复元素不进入L1表。

else{ pc->next=pa;pc=pa;pa=pa->next;} ∥交集元素并入结果表。

} ∥ while

while(pa) {u=pa;pa=pa->next;free(u);} ∥ 删L1表剩余元素

pc->next=null; ∥置结果链表尾。

注： 本算法中对L2表未作释放空间的处理。

（4） 本题与上面（3）算法相同，只是结果表要另辟空间。

（5） [题目分析]本题首先求B和C的交集，即求B和C中共有元素，再与A求并集，同时删除重复元素，以保持结果A递增。

LinkedList union(LinkedList A,B,C)

∥A,B和C均是带头结点的递增有序的单链表，本算法实现A= A∪（B∩C），使求解结构保持递增有序。

{pa=A->next;pb=B->next;pc=C->next;∥设置三个工作指针。

pre=A; ∥pre指向结果链表中当前待合并结点的前驱。

if(pa->data<pb->data||pa->data<pc->data)∥A中第一个元素为结果表的第一元素。

{pre->next=pa;pre=pa;pa=pa->next;}

else{ while(pb&&pc) ∥找B表和C表中第一个公共元素。

if(pb->data<pc->data)pb=pb->next;

else if(pb->data>pc->data)pc=pc->next;

else break; ∥找到B表和C表的共同元素就退出 while循环。

if(pb&&pc)∥ 因共同元素而非B表或C表空而退出上面 while循环。

if(pa->data>pb->data)∥A表当前元素值大于B表和C表的公共元素，先将B表元素链入。

{pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;}∥ B，C公共元素为结果表第一元素。

}∥结束了结果表中第一元素的确定

while(pa&&pb&&pc)

{ while(pb&&pc)

if(pb->data<pc->data) pb=pb->next;

else if(pb->data>pc->data) pc=pc->next;

else break; ∥B表和C表有公共元素。

if(pb&&pc)

{ while(pa&&pa->data<pb->data) ∥先将A中小于B，C公共元素部分链入。

{pre->next=pa;pre=pa;pa=pa->next;}

if(pre->data!=pb->data){pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;}

else{pb=pb->next;pc=pc->next;}∥ 若A中已有B，C公共元素，则不再存入结果表。

}

}∥ while(pa&&pb&&pc)

if(pa) pre->next=pa; ∥当B，C无公共元素（即一个表已空），将A中剩余链入。

}∥算法Union结束

[算法讨论]本算法先找结果链表的第一个元素，这是因为题目要求结果表要递增有序（即删除重复元素）。这就要求当前待合并到结果表的元素要与其前驱比较。由于初始pre=A（头结点的头指针），这时的data域无意义，不能与后继比较元素大小，因此就需要确定第一个元素。当然，不要这样作，而直接进入下面循环也可以，但在链入结点时，必须先判断pre是否等于A，这占用了过多的时间。因此先将第一结点链入是可取的。算法中的第二个问题是要求时间复杂度为O（|A|+|B|+|C|）。这就要求各个表的工作指针只能后移（即不能每次都从头指针开始查找）。本算法满足这一要求。

最后一个问题是，当B，C有一表为空（即B和C已无公共元素时），要将A的剩余部分链入结果表。

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

-end-