2.5.2 集合运算的实现

例2-14 假设以两个有序表分别表示集合A和B,试求集合C=A�DB。
 解题分析:
  算法框架和以上两例相同,在此只要单纯考虑集合运算的要求即可,显然只要将那些"在A中有而B中没有"的元素插入到C中,循环控制条件应该和例2-13相同,具体算法在此不再给出,请读者自行补充。

  显然,你写出的算法时间复杂度也应该是O (Listlength(A)+ListLength(B)) 的。

  如果在某个应用问题中需要用到只作并、交、差等的集合运算,则可在上述三个算法的基础上实现一个集合的抽象数据类型。请参考《数据结构题集》中实习一给出的例子。

 


例如:假设
   A = {3, 5, 6, 8, 9}
   B = {2, 4, 5, 8, 10}
 则 C = { 3, 6, 9}