用有序单链表表示集合，实现集合的交、并、差运算c++

下面是用有序单链表表示集合，并实现了集合的交、并、差运算的 C++ 代码：

#include <iostream>
using namespace std;

// 定义有序单链表节点的结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 定义集合的结构体
struct Set {
    ListNode* head;
    Set() : head(NULL) {}

    // 添加元素
    void add(int val) {
        if (!head || head->val > val) {
            ListNode* newNode = new ListNode(val);
            newNode->next = head;
            head = newNode;
            return;
        }

        ListNode* cur = head;
        while (cur->next && cur->next->val <= val) {
            cur = cur->next;
        }

        if (cur->val == val) {
            return;
        }

        ListNode* newNode = new ListNode(val);
        newNode->next = cur->next;
        cur->next = newNode;
    }

    // 求集合的交
    Set intersection(Set& s) {
        Set res;
        ListNode* cur = head;
        ListNode* cur2 = s.head;

        while (cur && cur2) {
            if (cur->val == cur2->val) {
                res.add(cur->val);
                cur = cur->next;
                cur2 = cur2->next;
            }
            else if (cur->val < cur2->val) {
                cur = cur->next;
            }
            else {
                cur2 = cur2->next;
            }
        }

        return res;
    }

    // 求集合的并
    Set Union(Set& s) {
        Set res;
        ListNode* cur = head;
        ListNode* cur2 = s.head;

        while (cur || cur2) {
            if (!cur) {
                res.add(cur2->val);
                cur2 = cur2->next;
            }
            else if (!cur2) {
                res.add(cur->val);
                cur = cur->next;
            }
            else if (cur->val == cur2->val) {
                res.add(cur->val);
                cur = cur->next;
                cur2 = cur2->next;
            }
            else if (cur->val < cur2->val) {
                res.add(cur->val);
                cur = cur->next;
            }
            else {
                res.add(cur2->val);
                cur2 = cur2->next;
            }
        }

        return res;
    }

    // 求集合的差
    Set difference(Set& s) {
        Set res;
        ListNode* cur = head;
        ListNode* cur2 = s.head;

        while (cur && cur2) {
            if (cur->val == cur2->val) {
                cur = cur->next;
                cur2 = cur2->next;
            }
            else if (cur->val < cur2->val) {
                res.add(cur->val);
                cur = cur->next;
            }
            else {
                cur2 = cur2->next;
            }
        }

        while (cur) {
            res.add(cur->val);
            cur = cur->next;
        }

        return res;
    }

    // 输出集合
    void print() {
        ListNode* cur = head;
        while (cur) {
            cout << cur->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
};

int main() {
    // 创建集合s1
    Set s1;
    s1.add(1);
    s1.add(3);
    s1.add(5);

    // 创建集合s2
    Set s2;
    s2.add(2);
    s2.add(3);
    s2.add(4);

    // 求交集
    Set res1 = s1.intersection(s2);
    cout << "intersection: ";
    res1.print(); // 输出 3

    // 求并集
    Set res2 = s1.Union(s2);
    cout << "Union: ";
    res2.print(); // 输出 1 2 3 4 5

    // 求差集
    Set res3 = s1.difference(s2);
    cout << "difference: ";
    res3.print(); // 输出 1 5

    return 0;
}

这里用到了链表的基本操作，包括添加节点、遍历节点等。同时，为了方便实现集合的交、并、差运算，我们定义了一个 Set 结构体，并在其中实现了相应的方法。