目录😋
任务描述
本关任务：编写一个程序求两个集合的并、交、差。
相关知识
为了完成本关任务，你需要掌握：
- 单链表表示集合
- 求两个集合的并集
- 求两个集合的交集
- 求两个集合的差集
一、单链表表示集合
- 单链表的基本结构
单链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储集合中的元素，指针域则指向下一个节点，通过指针将各个节点依次串联起来，最后一个节点的指针指向NULL，表示链表的结尾。
以下是用 C++ 语言定义单链表节点结构体的示例代码：
template <typename T> struct ListNode { T data; ListNode<T> *next; ListNode(T x) : data(x), next(NULL) {} };
- 用单链表表示集合的方式
把集合中的元素依次存储在单链表的各个节点的数据域中，由于集合中的元素具有无序性和互异性（即同一个元素不会重复出现），在构建单链表表示集合时，需要保证插入元素时遵循这两个特性。例如，当向单链表插入一个元素时，先遍历链表查看是否已存在该元素，如果不存在再将其插入到合适位置（通常是表头或表尾插入，以方便实现后续集合运算）。二、求两个集合的并集
- 并集的概念
对于两个集合 A 和 B，它们的并集是包含所有属于 A 或者属于 B 的元素所组成的集合，记作 A ∪ B。- 基于单链表求并集的算法思路
- 首先，创建一个新的空单链表来存储并集结果。
- 遍历表示集合 A 的单链表，将其中的元素依次插入到结果链表中（插入时要保证元素的互异性，需先判断是否已存在该元素）。
- 接着，遍历表示集合 B 的单链表，同样将其元素插入到结果链表中，在插入过程中，如果遇到已经存在于结果链表中的元素，则跳过该元素，只插入新的元素，确保最终结果链表中的元素满足集合的特性。
以下是用 C++ 实现求两个单链表表示的集合的并集的示例代码：
template <typename T> ListNode<T> *unionSets(ListNode<T> *listA, ListNode<T> *listB) { ListNode<T> *result = NULL; ListNode<T> **lastPtr = &result; // 先处理集合A ListNode<T> *p = listA; while (p!= NULL) { bool exists = false; ListNode<T> *q = result; while (q!= NULL) { if (q->data == p->data) { exists = true; break; } q = q->next; } if (!exists) { *lastPtr = new ListNode<T>(p->data); lastPtr = &((*lastPtr)->next); } p = p->next; } // 再处理集合B p = listB; while (p!= NULL) { bool exists = false; ListNode<T> *q = result; while (q!= NULL) { if (q->data == p->data) { exists = true; break; } q = q->next; } if (!exists) { *lastPtr = new ListNode<T>(p->data); lastPtr = &((*lastPtr)->next); } p = p->next; } return result; }
三、求两个集合的交集
- 交集的概念
对于两个集合 A 和 B，它们的交集是包含所有既属于 A 又属于 B 的元素所组成的集合，记作 A ∩ B。- 基于单链表求交集的算法思路
- 创建一个新的空单链表用于存储交集结果。
- 遍历表示集合 A 的单链表，对于 A 中的每个元素，再去遍历表示集合 B 的单链表，查看该元素是否也在 B 中存在，如果存在，则将这个元素插入到结果链表中，这样最终结果链表中的元素就是两个集合的公共元素，即交集。
以下是用 C++ 实现求两个单链表表示的集合的交集的示例代码：
template <typename T> ListNode<T> *intersectionSets(ListNode<T> *listA, ListNode<T> *listB) { ListNode<T> *result = NULL; ListNode<T> **lastPtr = &result; ListNode<T> *p = listA; while (p!= NULL) { ListNode<T> *q = listB; while (q!= NULL) { if (q->data == p->data) { bool exists = false; ListNode<T> *r = result; while (r!= NULL) { if (r->data == p->data) { exists = true; break; } r = r->next; } if (!exists) { *lastPtr = new ListNode<T>(p->data); lastPtr = &((*lastPtr)->next); } break; } q = q->next; } p = p->next; } return result; }
四、求两个集合的差集
- 差集的概念
对于两个集合 A 和 B，集合 A 与集合 B 的差集是由所有属于 A 但不属于 B 的元素组成的集合，记作 A - B。- 基于单链表求差集的算法思路
- 创建一个新的空单链表来存放差集结果。
- 遍历表示集合 A 的单链表，对于 A 中的每个元素，去遍历表示集合 B 的单链表，查看该元素是否在 B 中出现，如果没有出现在 B 中，则将该元素插入到结果链表中，这样最终结果链表中的元素就是属于 A 但不属于 B 的元素，即 A - B 的差集。
以下是用 C++ 实现求两个单链表表示的集合的差集（以 A - B 为例）的示例代码：
template <typename T> ListNode<T> *differenceSets(ListNode<T> *listA, ListNode<T> *listB) { ListNode<T> *result = NULL; ListNode<T> **lastPtr = &result; ListNode<T> *p = listA; while (p!= NULL) { bool exists = false; ListNode<T> *q = listB; while (q!= NULL) { if (q->data == p->data) { exists = true; break; } q = q->next; } if (!exists) { *lastPtr = new ListNode<T>(p->data); lastPtr = &((*lastPtr)->next); } p = p->next; } return result; }
测试说明
平台会对你编写的代码进行测试：
测试输入：
a c e f
a b d e h i
预期输出：
有序集合A:a c e f
有序集合B:a b d e h i
集合的并集:a b c d e f h i
集合的交集:a e
集合的差集:c f
开始你的任务吧，祝你成功！
通关代码
using namespace std; struct Node { char data; Node *next; }; class LinkedList { public: Node *head; LinkedList() { head = nullptr; } void add_sorted(char value) { Node *newNode = new Node(); newNode->data = value; newNode->next = nullptr; if (head == nullptr || head->data > value) { newNode->next = head; head = newNode; } else { Node *current = head; while (current->next != nullptr && current->next->data < value) { current = current->next; } if (current->next == nullptr || current->next->data > value) { newNode->next = current->next; current->next = newNode; } } } void print_list() { Node *current = head; while (current != nullptr) { cout << current->data << " "; current = current->next; } cout << endl; } set<char> to_set() { set<char> result; Node *current = head; while (current != nullptr) { result.insert(current->data); current = current->next; } return result; } }; set<char> union_sets(const set<char> &set_a, const set<char> &set_b) { set<char> result = set_a; result.insert(set_b.begin(), set_b.end()); return result; } set<char> intersection_sets(const set<char> &set_a, const set<char> &set_b) { set<char> result; for (char elem : set_a) { if (set_b.find(elem) != set_b.end()) { result.insert(elem); } } return result; } set<char> difference_sets(const set<char> &set_a, const set<char> &set_b) { set<char> result; for (char elem : set_a) { if (set_b.find(elem) == set_b.end()) { result.insert(elem); } } return result; } int main() { LinkedList list_a, list_b; string input; cout << "有序集合A:"; getline(cin, input); for (char c : input) { if (c != ' ') { list_a.add_sorted(c); } } getline(cin, input); for (char c : input) { if (c != ' ') { list_b.add_sorted(c); } } list_a.print_list(); cout << "有序集合B:"; list_b.print_list(); set<char> set_a = list_a.to_set(); set<char> set_b = list_b.to_set(); set<char> union_set = union_sets(set_a, set_b); set<char> intersection_set = intersection_sets(set_a, set_b); set<char> difference_set = difference_sets(set_a, set_b); cout << "集合的并集:"; for (char c : union_set) { cout << c << " "; } cout << endl; cout << "集合的交集:"; for (char c : intersection_set) { cout << c << " "; } cout << endl; cout << "集合的差集:"; for (char c : difference_set) { cout << c << " "; } cout << endl; return 0; }
测试结果
