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

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

LinkedList union(LinkedList ABC)∥AB和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;}∥ BC公共元素为结果表第一元素

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

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中小于BC公共元素部分链入

{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中已有BC公共元素则不再存入结果表

}

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

if(pa) pre>next=pa;∥当BC无公共元素(即一个表已空)将A中剩余链入

}∥算法Union结束

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