编写程序exp2-8.cpp,采用单链表表示集合(假设同一个集合中不存在重复的元素),将其按递增方式排列,构成有序单链表,求这样两个集合的并集。
时间: 2024-12-19 12:28:47 浏览: 6
exp2-1.cpp
编写一个名为 `exp2-8.cpp` 的程序,首先需要创建一个单链表节点结构体 `ListNode` 和相关的链表操作函数,例如插入、删除和比较等。然后我们可以设计一个 `Set` 类来表示集合,其中包含一个单链表用于存储元素,并提供添加、删除元素以及合并两个集合的功能。
```cpp
#include <iostream>
// 定义链表节点结构
struct ListNode {
int value;
ListNode* next;
ListNode(int val = 0) : value(val), next(nullptr) {}
};
class Set {
private:
ListNode* head; // 链表头指针
public:
// 添加元素到集合
void add(int value) {
ListNode* newNode = new ListNode(value);
if (!head) {
head = newNode;
} else {
ListNode* current = head;
while (current->next && current->next->value < value) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
// 合并两个集合
void unionWith(const Set& other) {
ListNode* tempHead = head;
while (tempHead && other.head) {
if (tempHead->value < other.head->value) {
tempHead = tempHead->next;
} else {
add(other.head->value); // 将其他集合的较小值添加到当前集合
other.head = other.head->next;
}
}
// 如果other还有剩余元素,直接添加
while (other.head) {
add(other.head->value);
other.head = other.head->next;
}
}
// 打印链表
void print() const {
ListNode* current = head;
while (current) {
std::cout << current->value << " -> ";
current = current->next;
}
std::cout << "nullptr" << std::endl;
}
};
int main() {
Set set1, set2;
// 初始化第一个集合
set1.add(5);
set1.add(1);
set1.add(4);
// 初始化第二个集合
set2.add(6);
set2.add(7);
set2.add(3);
// 合并两个集合
set1.unionWith(set2);
// 输出结果
std::cout << "Sorted Set 1 after union:" << std::endl;
set1.print();
return 0;
}
```
阅读全文