1230: 集合union

喜欢ヅ旅行 2021-09-22 12:28 274阅读 0赞

## Description ##

假设利用两个线性表LA和LB分别表示两个集合A和B（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合A=A∪B。这就要求对线性表做如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。只要从线性表LB中依次取得每个元素，并依值在线性表LA中进行查访，若不存在，则插入之。上述操作过程可用下列算法描述之。

上图算法中，在第8行取得集合B中的元素，然后再在第10行插入到集合A中。你的任务是先输出集合A和集合B中的元素，每个集合在一行中输出。然后每次在将集合B中的元素取出插入到集合A尾部后输出集合A中的元素。当然你的代码可以和上面的代码不一样，只要有相同的输出即可。

## Input ##

有多组测试数据，每组测试数据占两行。第一行是集合A，第一个整数m（0<m<=100）代表集合A起始有m个元素，后面有m个整数，代表A中的元素。第二行是集合B，第一个整数n(0<n<=100)代表集合B起始有n个元素，后面有n个整数，代表B中的元素。每行中整数之间用一个空格隔开。

## Output ##

每组测试数据输出n+2行：前两行分别输出集合A、集合B中的数据，后面n行是每次从B中取出元素插入到A尾部后的集合A。每行整数之间用一个空格隔开，每组测试数据之间用一行空行隔开。

## Sample Input ##

5 1 5 2 6 3
    3 1 7 9
    1 3
    2 2 7
    4 2 5 1 4
    4 1 2 4 5

## Sample Output ##

1 5 2 6 3
    1 7 9
    1 5 2 6 3
    1 5 2 6 3 7
    1 5 2 6 3 7 9
    
    3
    2 7
    3 2
    3 2 7
    
    2 5 1 4
    1 2 4 5
    2 5 1 4
    2 5 1 4
    2 5 1 4
    2 5 1 4

上述操作过程可用下列算法描述之。

![70][]

**示例代码：**

#include <iostream>
    using namespace std;
    typedef struct List{  
        int L[200];  
        int length;  
    }List;  
    List La,Lb;  
    bool LocateElem(List &La,int e){  
        for(int i=0;i<La.length;i++){  
            if(La.L[i]==e)  
                return true;  
        }  
        return false;  
    }  
    void show(List &L){  
        cout<<L.L[0];  
        for(int i=1;i<L.length;i++)  
            cout<<" "<<L.L[i];  
        cout<<endl;  
    }  
    void Union(List &La,List &Lb){  
        int e;  
        for(int i=0;i<Lb.length;i++){  
            e=Lb.L[i];  
            if(!LocateElem(La,e)){  
                La.L[La.length]=e;  
                La.length++;              
            }  
            show(La);  
        }  
    }  
    int main(){  
        int n1,n2;  
        while(cin>>n1&&n1!=EOF){   
            for(int i=0;i<n1;i++)  
                cin>>La.L[i];  
            La.length=n1;  
            cin>>n2;  
            for(int i=0;i<n2;i++)      
                cin>>Lb.L[i];  
            Lb.length=n2;  
            show(La);  
            show(Lb);  
            Union(La,Lb);  
            cout<<endl;  
        }   
         return 1;  
    }

注意事项：  
1、使用数组时，给集合 A 分配的空间不小于200。因为将 B 中的元素添加到 A 中时，可能会超过 100 了。  
2、一个细节问题就是题目要求输出的格式是每行中元素之间用一个空格隔开，每组输出间用一个空行隔开。也就是说4个元素间只有3个空格，2组输出间只有1个空行。处理方法都一样。两种方法：一是除了第一个元素，后面的每个元素之前输出个空格；二是除了最后一个元素，前面的每个元素之后都输出一个空格。我往往采用第一种方式，因为许多编程语言中的数组都是从0开始的，而0正是判断语句中的“假”（当然Java中不是这样的）。

[70]: /images/20210920/514b24c0a4594b51b2f91361fd2ef607.png