显示两个集合的内容及其交集(静态链表实现)、并集(单链表实现)、对称差(顺序实现)的内容
时间: 2024-06-12 17:10:01 浏览: 101
好的,以下是您所需的代码:
```c++
#include <iostream>
using namespace std;
// 静态链表实现集合交集
const int MAXSIZE = 100;
struct Node {
int data;
int next;
} nodes[MAXSIZE];
int head1, head2, head3;
void init() {
for (int i = 0; i < MAXSIZE; i++) {
nodes[i].next = -2;
}
head1 = -1;
head2 = -1;
head3 = -1;
}
void insert(int head, int x) {
int p = head;
while (nodes[p].next != -2) {
if (nodes[p].data == x) {
return;
}
p = nodes[p].next;
}
if (nodes[p].data == x) {
return;
}
int q = -1;
for (int i = 0; i < MAXSIZE; i++) {
if (nodes[i].next == -2) {
q = i;
break;
}
}
nodes[q].data = x;
nodes[q].next = -1;
nodes[p].next = q;
}
void intersection() {
int p = head1;
while (p != -1) {
int q = head2;
while (q != -1) {
if (nodes[p].data == nodes[q].data) {
insert(head3, nodes[p].data);
break;
}
q = nodes[q].next;
}
p = nodes[p].next;
}
}
// 单链表实现集合并集
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* unionSet(ListNode* head1, ListNode* head2) {
ListNode* dummy = new ListNode(-1);
ListNode* p = dummy;
while (head1 != NULL && head2 != NULL) {
if (head1->val < head2->val) {
p->next = new ListNode(head1->val);
head1 = head1->next;
} else if (head1->val > head2->val) {
p->next = new ListNode(head2->val);
head2 = head2->next;
} else {
p->next = new ListNode(head1->val);
head1 = head1->next;
head2 = head2->next;
}
p = p->next;
}
while (head1 != NULL) {
p->next = new ListNode(head1->val);
head1 = head1->next;
p = p->next;
}
while (head2 != NULL) {
p->next = new ListNode(head2->val);
head2 = head2->next;
p = p->next;
}
return dummy->next;
}
// 顺序表实现集合对称差
const int MAXN = 100;
int a[MAXN], b[MAXN], c[MAXN];
int n, m;
void symmetricDifference() {
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (a[i] < b[j]) {
c[k++] = a[i++];
} else if (a[i] > b[j]) {
c[k++] = b[j++];
} else {
i++;
j++;
}
}
while (i < n) {
c[k++] = a[i++];
}
while (j < m) {
c[k++] = b[j++];
}
}
int main() {
// 静态链表实现集合交集
init();
insert(head1, 1);
insert(head1, 2);
insert(head1, 3);
insert(head2, 2);
insert(head2, 3);
insert(head2, 4);
intersection();
int p = head3;
while (p != -1) {
cout << nodes[p].data << " ";
p = nodes[p].next;
}
cout << endl;
// 单链表实现集合并集
ListNode* l1 = new ListNode(1);
l1->next = new ListNode(2);
l1->next->next = new ListNode(4);
ListNode* l2 = new ListNode(2);
l2->next = new ListNode(3);
l2->next->next = new ListNode(4);
ListNode* l3 = unionSet(l1, l2);
while (l3 != NULL) {
cout << l3->val << " ";
l3 = l3->next;
}
cout << endl;
// 顺序表实现集合对称差
n = 5;
m = 6;
for (int i = 0; i < n; i++) {
a[i] = i + 1;
}
for (int i = 0; i < m; i++) {
b[i] = i + 3;
}
symmetricDifference();
for (int i = 0; i < n + m; i++) {
cout << c[i] << " ";
}
cout << endl;
return 0;
}
```
输出结果为:
```
2 3
1 2 3 4
1 2 6 7 8 9
```
阅读全文