集合的交、并、差运算
【问题描述】
      编制一个能演示执行集合的交、并和差运算的程序。
【任务要求】
1)集合元素用小写英文字母,执行各种操作应以对话方式执行。
2)算法要点:利用单链表表示集合;理解好三种运算的含义
【测试数据】
自行设定,注意边界等特殊情况。
这道题目其实很简单的,只需要思路对了,实际操作都是比较基础的,其中集合的交集运算是将两个集合都有的元素拿到,并集是将两个集合的元素都拿到,并且不重复,所以我们可以先将第一个集合的元素拿到,再将第二个集合中与第一个集合的元素不同的元素拿到,差运算是将第一个集合中不含有第二个集合元素的元素拿到。这三个集合中都有一个共同点,就是要先找出两个集合中都含有的元素,所以可以将其单独封装。代码如下:
<code lang="c++">void select(Node *a, Node *b) { //挑出两个集合中都有的元素,并标记它
    init(a);
    init(b);
    Node *p, *q;
    for (p = a->next; p != NULL; p = p->next) {
        for (q = b->next; q != NULL; q = q->next) { 
            if (p->data == q->data&& p->tag == false && q->tag == false) { //用标记将a,b两个数组中的已经选过的筛掉
                p->tag = q->tag = true;
            }
        }
    }
}
</code>
还有就是要用单链表表示集合,所以要构建一个单链表,指针什么的太麻烦了....不过还好这个是简单的....
构建单链表的代码如下:
<code lang="c++">
void input(Node *x) {
    cout << "请输入数组长度" << endl;
    cin >> x->length;
    if (x->length > MAX) {
        cout << "数组长度输入错误请重新输入数组长度" << endl;
        input(x);
        return;
    }
    cout << "请输入数组的值" << endl;
    Node *p = x;
    for (int i = 0; i < x->length; i++) {
            Node *q = new Node();
            cin >> q->data; 
            p->next = q;
            q->next = NULL;
            p = p->next;
    }
}
</code>
接下来就是进行交集、并集、差的运算了,不过这三个运算很多代码都是差不多的,会写一个就能写三个的感觉,所以就只贴一个了。代码如下:
<code lang="c++">
void Cross(Node *a, Node *b, Node *c) { //交集运算
    cout << "开始进行集合的交集运算" << endl;
    select(a, b);
    Node *C = c;
    for (Node *p = a; p != NULL; p = p->next) {
        if (p->tag) {
            Node *q=new Node();
            q->data = p->data;
            q->next = NULL;
            C->next = q;
            C = C->next;
        }
    }
    C = c;
    while (C != NULL) {
        cout << C->data << " ";
        C = C->next;
    }
    cout << endl << "交集的交集运算执行完毕" << endl;
}
</code>
对了,上面的init函数只是将集合的标记重置一下,除此之外,并没有什么卵用。
以上就是比较简单的第一个集合的交、并、差运算了。