数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
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-