用C语言 有序单链表 求集合的并交差运算 有没有大佬教一下我啊(╥ω╥`) 【问题描述】 编

Question

用C语言 有序单链表 求集合的并交差运算 有没有大佬教一下我啊(╥ω╥`) 【问题描述】   编制一个能演示执行集合的并、交和差运算的程序。  【基本要求】   ⑴ 对集合中的元素，用有序单链表进行存储； ⑵ 实现交、并、差运算时，不另外申请存储空间； ⑶ 充分利用单链表的有序性，算法有较好的时间性能。 【测试数据】  (1)Set1="magazine"，Set2="paper"，   Set1∪Set2="aegimnprz"，Setl ∩Set2="ae"，Set1-Set2="gimnz"。  (2)Set1= " 012oper4a6tion89"，Set2="error data"，    Set1∪Set2="adeinoprt"，Setl ∩Set2="aeort"，Set1-Set2="inp"。  【实现提示】  用有序单链表表示集合，实现集合的交、并和差运算。 【选作内容】  (1) 集合的元素判定和子集判定运算。  (2) 求集合的补集。  (3) 集合的混合运算表达式求值。  (4) 集合的元素类型推广到其他类型 ， 甚至任意类型。

Answer 1

以下是一种 C++ 实现方案，利用有序单链表存储集合，实现交、并和差运算：

#include <iostream>
using namespace std;

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

// 两个有序链表的交集
Node* intersect(Node *first, Node *second) {
    Node *head = new Node();
    Node *cur = head;
    while (first != nullptr && second != nullptr) {
        if (first->data < second->data) {
            first = first->next;
        } else if (first->data > second->data) {
            second = second->next;
        } else {
            cur->next = new Node();
            cur = cur->next;
            cur->data = first->data;
            first = first->next;
            second = second->next;
        }
    }
    cur->next = nullptr;
    return head->next;
}

// 两个有序链表的并集
Node* unionSet(Node *first, Node *second) {
    Node *head = new Node();
    Node *cur = head;
    while (first != nullptr || second != nullptr) {
        if (second == nullptr || (first != nullptr && first->data < second->data)) {
            cur->next = new Node();
            cur = cur->next;
            cur->data = first->data;
            first = first->next;
        } else if (first == nullptr || second->data < first->data) {
            cur->next = new Node();
            cur = cur->next;
            cur->data = second->data;
            second = second->next;
        } else {
            cur->next = new Node();
            cur = cur->next;
            cur->data = first->data;
            first = first->next;
            second = second->next;
        }
    }
    cur->next = nullptr;
    return head->next;
}

// 两个有序链表的差集
Node* difference(Node *first, Node *second) {
    Node *head = new Node();
    Node *cur = head;
    while (first != nullptr && second != nullptr) {
        if (first->data < second->data) {
            cur->next = new Node();
            cur = cur->next;
            cur->data = first->data;
            first = first->next;
        } else if (first->data > second->data) {
            second = second->next;
        } else {
            first = first->next;
            second = second->next;
        }
    }
    while (first != nullptr) {
        cur->next = new Node();
        cur = cur->next;
        cur->data = first->data;
        first = first->next;
    }
    cur->next = nullptr;
    return head->next;
}