动态单链表实现集合的并、交和差运算

首先，定义动态单链表中的节点结构体，包括数据域和指向下一个节点的指针：

struct Node {
    int data;
    Node* next;
};

然后，定义动态单链表类，包括节点的增删改查等基本操作：

class LinkedList {
private:
    Node* head; // 头节点指针
public:
    LinkedList() { // 构造函数
        head = new Node();
        head->next = NULL;
    }
    ~LinkedList() { // 析构函数
        Node* p = head;
        while (p) {
            Node* q = p->next;
            delete p;
            p = q;
        }
    }
    void insert(int x) { // 插入节点
        Node* p = new Node();
        p->data = x;
        p->next = head->next;
        head->next = p;
    }
    void remove(int x) { // 删除节点
        Node* p = head->next;
        Node* q = head;
        while (p) {
            if (p->data == x) {
                q->next = p->next;
                delete p;
                p = q->next;
            } else {
                q = p;
                p = p->next;
            }
        }
    }
    bool has(int x) { // 查找节点
        Node* p = head->next;
        while (p) {
            if (p->data == x) {
                return true;
            }
            p = p->next;
        }
        return false;
    }
    void print() { // 打印链表
        Node* p = head->next;
        while (p) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }
};

接下来，定义集合类，包括并、交和差运算：

class Set {
private:
    LinkedList list; // 集合元素存储在动态单链表中
public:
    void insert(int x) { // 插入元素
        if (!list.has(x)) {
            list.insert(x);
        }
    }
    void remove(int x) { // 删除元素
        list.remove(x);
    }
    bool has(int x) { // 查找元素
        return list.has(x);
    }
    void print() { // 打印集合
        list.print();
    }
    Set operator+(const Set& other) const { // 集合并运算
        Set result;
        Node* p = list.head->next;
        while (p) {
            result.insert(p->data);
            p = p->next;
        }
        p = other.list.head->next;
        while (p) {
            result.insert(p->data);
            p = p->next;
        }
        return result;
    }
    Set operator*(const Set& other) const { // 集合交运算
        Set result;
        Node* p = list.head->next;
        while (p) {
            if (other.has(p->data)) {
                result.insert(p->data);
            }
            p = p->next;
        }
        return result;
    }
    Set operator-(const Set& other) const { // 集合差运算
        Set result;
        Node* p = list.head->next;
        while (p) {
            if (!other.has(p->data)) {
                result.insert(p->data);
            }
            p = p->next;
        }
        return result;
    }
};

使用示例：

int main() {
    Set a, b;
    a.insert(1);
    a.insert(2);
    a.insert(3);
    b.insert(2);
    b.insert(3);
    b.insert(4);
    Set c = a + b; // 并集
    c.print(); // 输出 4 3 2 1
    c = a * b; // 交集
    c.print(); // 输出 3 2
    c = a - b; // 差集
    c.print(); // 输出 1
    return 0;
}