前言
用链表实现一个集合，并实现集合的交并运算，测试数据在最后。
提示：以下是本篇文章正文内容，下面案例可供参考
一、需求分析
二、模块设计
定义集合
首先需要定义一个节点类和链表类，节点类里面存储着成员变量数据域和next指针，同时将链表类声明为友元类。链表类里面存放着成员变量头结点指针，和集合的元素个数，以及与集合功能相关的成员函数。
这样就能够通过一个链表类来表示一个集合。
建立集合
通过默认构造函数建立一个空集合，然后通过
void
create_gather()
函数向集合中输入元素，
在输入过程中，使用
int
find_element(
int
a
)
函数检查输入元素与集合元素是否重复，完成去重操作，用0结束输入。
求交集
使用
LinkList
intersection(
LinkList
&
a
,
LinkList
&
b
)
函数进行求交集，实现的逻辑是将集合a和一个空集合b传入函数，然后对当前链表表示集合与集合a进行求交集，将相交的元素通过
void
insert_element(
int
a
)
函数插入到空集合b中，最后所求交集即为集合b。
求并集
使用
LinkList
sum(
LinkList
&
a
,
LinkList
&
b
)
函数进行求并集，实现的逻辑同样是将集合a和一个空集合b传入函数，然后通过
LinkList
&
operator=
(
const
LinkList
&
other
)
函数将集合a赋值给集合b,然后再将当前链表表示集合中的每一个元素通过
void
insert_element(
int
a
)
插入到集合b中，插入函数也通过
int
find_element(
int
a
)
函数完成去重，最后所求并集即为集合b.
排序
使用
void
sort_gather()
函数进行排序，实现的逻辑是冒泡排序。
输出元素
使用
void
show_gather()
函数对集合进行输出，实现逻辑是将集合遍历一遍，然后输入节点中的数据。
三、具体实现
完整代码：
#include<iostream>
using namespace std;
class Node {
int data;
Node* next;
friend class LinkList;
};
class LinkList {
Node* head;
int size;
public:
LinkList() { head = NULL; size = 0; } //默认构造
LinkList& operator=(const LinkList& other);// 赋值构造函数
void create_gather();//创建集合
int find_element(int a); //查找元素
void insert_element(int a); //插入元素
LinkList intersection(LinkList& a, LinkList& b); //求交集
LinkList sum(LinkList& a, LinkList& b); //求并集
void show_gather();//显示集合元素
void sort_gather();//排序
bool is_empty(); //判空
};
void LinkList::create_gather() { //创建
head = new Node;
head->next = NULL;
int data;
Node* q = head;
cin >> data;
while (data!=0) {
if(find_element(data)==-100){
Node* p = new Node;
p->data = data;
p->next = NULL;
q->next = p;
q = p;
size++;
}
cin >> data;
}
}
int LinkList::find_element(int a) { //查找
if (is_empty()) return -100;
Node* p = head->next;
while (p) {
if (a == p->data) return a;
p = p->next;
}
return -100;
}
void LinkList::insert_element(int a) { //插入
if (is_empty()) {
head = new Node;
head->next = NULL;
Node* p = new Node;
p->data = a;
p->next = NULL;
head->next = p;
size++;
}
else {
if (find_element(a) == -100) {
Node* p = new Node;
p->data = a;
p->next = NULL;
p->next = head->next;
head->next = p;
size++;
}
}
}
bool LinkList::is_empty() { //判空
if (size == 0) return true;
return false;
}
LinkList& LinkList:: operator=(const LinkList& other) { //赋值构造
if (this == &other) return *this;
size = other.size;
head = new Node;
head = other.head;
Node* p = other.head;
Node* q = head;
while(p){
q = new Node;
q->next =p->next;
q = p;
p = p->next;
}
return *this;
}
LinkList LinkList::intersection(LinkList& a, LinkList& b) { //交集
Node* p = head->next;
while (p) {
Node* q = a.head->next;
while (q) {
if (p->data == q->data) {
b.insert_element(p->data);
b.size++;
}
q = q->next;
}
p = p->next;
}
return b;
}
LinkList LinkList::sum(LinkList& a, LinkList& b) { //并集
b = a; Node* p = head->next;
for (int i = 0; i < size; i++) {
b.insert_element(p->data);
b.size++;
p = p->next;
}
return b;
}
void LinkList::sort_gather() { //排序
Node* p = head->next;
while (p) {
Node* q = p->next;
while (q) {
int temp;
if (p->data > q->data) {
temp = p->data;
p->data = q->data;
q->data = temp;
}
q = q->next;
}
p = p->next;
}
}
void LinkList::show_gather() { //显示
if (is_empty()) { cout << endl; return; }
sort_gather();
Node* p = head->next;
while (p) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
int main() {
LinkList a, b, c;
cout << "请输入集合a元素：" << endl;
a.create_gather();
cout << "请输入集合b元素：" << endl;
b.create_gather();
cout << "a集合元素为：";
a.show_gather();
cout << "b集合元素为：";
b.show_gather();
c = a.intersection(b, c);
cout << "交集为：";
c.show_gather();
c = a.sum(b, c);
cout << "并集为：";
c.show_gather();
}测试数据：
实际输出：
逗号格式我就没改了，这里使用0结束输入。