2.5.2 集合运算的实现

例题 例2-13 假设以两个有序表分别表示集合A和B，试求集合C=A∩B。

算法 算法2.27
　　void Intersection (OrderLinkList A,
　　　　　　　　　　　　OrderLinkList B, OrderLinkList &C)
　{
　　// 已知有序链表 A 和 B 分别表示两个集合，
　　// 本算法求得有序链表 C 中所含元素是 A 和 B 的交集
　　if ( InitList(C) )　　　　　　　　　　// 初始化建空表
　　{
　　　m = ListLength(A); n = Listlength(B); // 分别求得表长
　　　i = 1; j = 1; 		 

　解题分析：
　　集合求"交"和集合求"并"的解法几乎是完全相同的，只是在求交时只需要将A和B中相同的元素插入C表即可。

例如：假设
　　 A = {3, 5, 6, 8, 9}
　　 B = {2, 4, 5, 8, 10}
　则 C = { 5, 8 }		  
  　　　while ( i <= m && j <= n )　　　 　// 顺序考察表中元素
　　　{
　　　　if ( GetPos(A,i) && GetPos(B,j) )
　　　　{　　　　　　　　　　　　　　　　// 两个表中都还有元素未曾考察
　　　　　GetCurElem( A,ea ); GetCurElem( B,eb );
　　　　　if ( ea < eb ) ++i;
　　　　　else if ( ea > eb ) ++j;
　　　　　else
　　　　　{　　　　 　　　　　　　　　　　　// 插入和 相同的元素
　　　　　　if ( !MakeNode( s,ea ) ) exit(1);
　　　　　　++i;++j;
　　　　　　InsAfter(C,s);
　　　　　} // else
　　　　} // if
　　　} // while
　　} // if
　} // Intersection

　　算法时间复杂度为：O (Listlength(A)+ListLength(B))。		   　　显然，对集合求交的运算而言，只要有一个表已经没有元素可查时就不需要继续进行了。在此，这个条件自然满足。