C++简单集合类的实现方法
什么是集合类?
集合类是数据结构中的一种,用来存储一组相同类型的数据项。集合类可以快速的对其中的数据进行添加、删除、查找、排序等操作。在C++中,STL中的集合类就是其中之一。
集合类实现原理
在实现一个集合类时,我们可以使用数组、链表、哈希表等数据结构。不过,在这里我们使用了一个常用的数据结构:红黑树。
红黑树是一种自平衡二叉搜索树,常用于实现Map和Set等集合类。它保证了每个节点的左右子树高度相差不超过1,从而使得树的深度不会过深,查询的效率高。同时,红黑树的插入和删除操作比较简单,保证了代码的可维护性。
集合类实现步骤
- 定义集合类
```cpp
template
class SimpleSet;
template
class SimpleSetIterator;
template
class SimpleSet {
private:
struct Node {
T key;
Node left;
Node right;
bool color; // 记录节点颜色,0为黑色,1为红色
};
Node* root;
int count;
public:
SimpleSet();
~SimpleSet();
bool insert(const T& key);
bool remove(const T& key);
bool contains(const T& key);
int size() const;
void clear();
SimpleSetIterator<T>* iterator();
};
``
SimpleSet
其中,是集合类的主要实现,
SimpleSetIterator`是集合类的迭代器,用来遍历集合中的所有元素。
- 实现构造函数和析构函数
```cpp
template
SimpleSet::SimpleSet() : root(nullptr), count(0) {}
template
SimpleSet
clear();
}
``
clear()`函数进行内存的释放。
构造函数和析构函数都比较简单,构造函数初始化了根节点和元素数量,析构函数调用了
- 实现插入和删除操作
```cpp
template
bool SimpleSet::insert(const T& key) {
bool flag = false; // flag表示是否插入成功
Node newNode = new Node {key, nullptr, nullptr, 1};
if (root == nullptr) { // 根节点为空
root = newNode;
root->color = 0; // 根节点为黑色
count++;
flag = true;
} else {
Node curr = root;
Node* parent = nullptr;
while (curr != nullptr && curr->key != key) {
parent = curr;
if (curr->key > key) curr = curr->left;
else curr = curr->right;
}if (curr == nullptr) { // 插入到叶子节点 if (parent->key > key) parent->left = newNode; else parent->right = newNode; newNode->color = 1; // 新节点为红色 count++; flag = true; }
}
return flag;
}
template
bool SimpleSet
bool flag = false;
Node curr = root;
Node parent = nullptr;
while (curr != nullptr && curr->key != key) {
parent = curr;
if (curr->key > key) curr = curr->left;
else curr = curr->right;
}
if (curr == nullptr) { // 未找到要删除的节点
return flag;
} else if (curr->left != nullptr && curr->right != nullptr) { // 被删除的节点同时具有左右孩子
Node* temp = curr->right;
while (temp->left != nullptr) temp = temp->left;
curr->key = temp->key; // 把右子树中的最小值替换为当前节点
curr = temp; // 记录当前节点,变为左子树中的情况
parent = curr;
}
Node* child;
if (curr->left != nullptr) child = curr->left;
else child = curr->right;
if (curr->color == 0 && child != nullptr) { // 黑色叶子节点,判断其孩子色是否为红
if (child->color == 1) {
child->color = 0; // 孩子节点变为黑色
flag = true;
} else {
flag = fixUp(child, parent); // 修正红黑树,返回是否删除节点
}
} else if (curr->color == 1 && child != nullptr) { // 带一个红色孩子节点的黑色节点
child->color = 0; // 把孩子节点变为黑色
flag = true;
} else if (curr->color == 0 && child == nullptr) { // 黑色叶子节点无孩子节点
flag = fixUp(curr, parent); // 修正红黑树,返回是否删除节点
} else { // 带一个空孩子节点的黑色节点
flag = true;
}
if (flag) { // 删除当前节点,更新元素数量和父节点指针
if (parent == nullptr) root = child;
else if (parent->left == curr) parent->left = child;
else parent->right = child;
if (child != nullptr) child->color = 0; // 处理删除节点的颜色和父节点指针
count--;
delete curr;
}
return flag;
}
```
插入操作先判断根节点是否为空,然后使用循环判断要插入的值在红黑树中的位置。如果找到,则不再插入;否则,将新节点插入到叶子节点上,并保证红黑树的性质。这里要注意:插入节点的颜色必须为红色,否则会破坏红黑树的平衡性。
删除操作则比较复杂。删除一个节点后,红黑树需要进行颜色调整和结构调整。具体的实现方式是:对于红色节点的删除操作会让树保持平衡,不需做其他调整;而对于黑色节点的删除则可能导致红黑树的平衡被破坏,需要进行一些复杂调整。
-
实现查找和遍历操作
```cpp
template
bool SimpleSet::contains(const T& key) {
Node* curr = root;
while (curr != nullptr && curr->key != key) {
if (curr->key > key) curr = curr->left;
else curr = curr->right;
}if (curr == nullptr) return false;
else return true;
}
template
int SimpleSet
return count;
}
template
void SimpleSet
while (root != nullptr) {
remove(root->key);
}
}
template
SimpleSetIterator
SimpleSetIterator
return iter;
}
``
true
查找操作使用循环遍历查找要查找的节点,如果找到就返回;如果遍历到末尾都未能找到,则说明该节点不存在,返回
false`。
遍历操作需要使用迭代器来进行实现,这里使用了前序遍历方式,包含了元素的递增排序。
示例说明
示例一:插入操作
SimpleSet<int> mySet;
mySet.insert(1);
mySet.insert(5);
mySet.insert(3);
mySet.insert(4);
以上代码演示了如何插入4个数字到集合中。插入操作会将数字逐个插入到集合中,如果在集合中已经有相同的数字,则不再重复插入。插入操作被设计成bool类型,如果插入成功则返回true
,否则返回false
。
示例二:遍历操作
SimpleSetIterator<int>* iter = mySet.iterator();
while (iter->hasNext()) {
cout << iter->next() << " ";
}
以上代码演示了如何遍历集合中的所有数字。需要先创建一个迭代器,然后调用hasNext()
函数检查是否还有下一个元素,如果有则调用next()
函数取出下一个元素。遍历的顺序是按数字大小递增排序的。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++简单集合类的实现方法 - Python技术站