【数据结构——线性表】求集合的并、交和差运算（头歌实践教学平台习题）【合集】

Rossy Yan

修改于 2024-12-26 10:19:09

13700

代码可运行

文章被收录于专栏：C++C++【Educoder实训】头歌实践教学平台

运行总次数：0

代码可运行

任务描述

本关任务：编写一个程序求两个集合的并、交、差。

相关知识

为了完成本关任务，你需要掌握：

要求采用单链表表示集合，要求输入的每个集合元素都按递增方式排序，且同一个集合中不存在重复的元素。
求两个集合的并、交、差。

输入集合元素

要求同一个集合中不存在重复的元素，且元素按递增排序。 例如：

ElemType a[4],b[6];
//为数组a输入4个字符，按顺序递增输入
//为数组b输入6个字符，按顺序递增输入
CreateListR(ha,a,4);//创建单链表ha，从数组a中读取元素
CreateListR(hb,b,6);//创建单链表hb，从数组b中读取元素

求两个集合的并、交、差
并集

对于两个给定集合A、B，由两个集合所有元素构成的集合，叫做A和B的并集。记作：AUB 读作“A并B” 例： {3,5}U{2,3,4,6}= {2,3,4,5,6}

交集

对于两个给定集合A、B，由属于A又属于B的所有元素构成的集合，叫做A和B的交集。记作： A∩B 读作“A交B” 例： A={1,2,3,4,5}，B={3,4,5,6,8}，A∩B={3,4,5}

差集

记A，B是两个集合，则所有属于A且不属于B的元素构成的集合，叫做集合A减集合B(或集合A与集合B之差)，类似地，对于集合A、B，把集合{x∣x∈A,且x∉B}叫做A与B的差集。记作：A-B 例： A={1,2,3,4,5}，B={3,4,5,6,8}，A-B={1,2}

测试说明

平台会对你编写的代码进行测试：
测试输入： 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

开始你的任务吧，祝你成功！

我的通关代码:

#include <iostream>
#include <set>
#include <string>
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;
}