() [題目分析]本題首先求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結束
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23352.html
