C++简单集合类的实现方法

C++简单集合类的实现方法

什么是集合类?

集合类是数据结构中的一种,用来存储一组相同类型的数据项。集合类可以快速的对其中的数据进行添加、删除、查找、排序等操作。在C++中,STL中的集合类就是其中之一。

集合类实现原理

在实现一个集合类时,我们可以使用数组、链表、哈希表等数据结构。不过,在这里我们使用了一个常用的数据结构:红黑树。

红黑树是一种自平衡二叉搜索树,常用于实现Map和Set等集合类。它保证了每个节点的左右子树高度相差不超过1,从而使得树的深度不会过深,查询的效率高。同时,红黑树的插入和删除操作比较简单,保证了代码的可维护性。

集合类实现步骤

  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`是集合类的迭代器,用来遍历集合中的所有元素。

  1. 实现构造函数和析构函数
    ```cpp
    template
    SimpleSet::SimpleSet() : root(nullptr), count(0) {}

template
SimpleSet::~SimpleSet() {
clear();
}
``
构造函数和析构函数都比较简单,构造函数初始化了根节点和元素数量,析构函数调用了
clear()`函数进行内存的释放。

  1. 实现插入和删除操作
    ```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::remove(const T& key) {
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;

}
```
插入操作先判断根节点是否为空,然后使用循环判断要插入的值在红黑树中的位置。如果找到,则不再插入;否则,将新节点插入到叶子节点上,并保证红黑树的性质。这里要注意:插入节点的颜色必须为红色,否则会破坏红黑树的平衡性。

删除操作则比较复杂。删除一个节点后,红黑树需要进行颜色调整和结构调整。具体的实现方式是:对于红色节点的删除操作会让树保持平衡,不需做其他调整;而对于黑色节点的删除则可能导致红黑树的平衡被破坏,需要进行一些复杂调整。

  1. 实现查找和遍历操作
    ```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::size() const {
return count;
}

template
void SimpleSet::clear() {
while (root != nullptr) {
remove(root->key);
}
}

template
SimpleSetIterator SimpleSet::iterator() {
SimpleSetIterator
iter = new SimpleSetIterator(root);
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技术站

(0)
上一篇 2023年5月23日
下一篇 2023年5月23日

相关文章

  • 一文详解Qt中的对象树机制

    一文详解Qt中的对象树机制 什么是对象树机制? 在 Qt 中,每一个对象都有其父对象,这些对象之间形成了一种树形结构,我们称之为 对象树。当一个对象被创建时,可以设置它的父对象,然后它就会成为父对象的子对象,加入到对象树中。 Qt 中的对象树机制,可以实现对象之间的自动管理,并沿着树形结构进行自动的构建、销毁和内存管理。 对象树的作用 对象树机制的主要作用:…

    C 2023年5月22日
    00
  • C语言字符串字面量池

    C语言字符串字面量池是一个常量池,其中存储在程序中出现的所有字符串字面量。使用字符串字面量池是一种优化技术,因为它允许多个字符串变量共享相同的内存地址,这样可以减少内存消耗。 在C语言中,无论字符串以何种方式定义,它都是一个字符数组,其中最后一个字符必须是空字符(\0)。将字符串字面量赋值给字符数组实际上是将字符串字面量的地址赋给字符数组指针。这个地址是指向…

    C 2023年5月9日
    00
  • C++实现简单通讯录管理系统

    C++实现简单通讯录管理系统攻略 目标 实现一个简单的通讯录管理系统,可以进行添加联系人、删除联系人、修改联系人和显示联系人等操作。程序的主要功能如下: 添加联系人:输入姓名、性别、年龄、电话及地址信息,添加一个联系人信息到通讯录中。 显示联系人:显示通讯录中的所有联系人信息。 删除联系人:输入要删除联系人的姓名,从通讯录中删除该联系人的信息。 查找联系人:…

    C 2023年5月23日
    00
  • C#正则表达式判断输入日期格式是否正确

    为了使用正则表达式判断输入日期格式是否正确,我们需要编写一个匹配日期格式的正则表达式,然后将要检查的日期与该正则表达式进行匹配。以下是一个完整的攻略: 1. 编写匹配日期格式的正则表达式 正则表达式是一个由一系列字符和操作符组成的模式。它可以用来匹配文本中的特定模式。要编写匹配日期格式的正则表达式,我们可以根据日期格式的规则来构建。以下是一个匹配 “yyyy…

    C 2023年5月23日
    00
  • java 异常之手动抛出与自动抛出的实例讲解

    Java 异常之手动抛出与自动抛出的实例讲解 在 Java 语言中,异常是一个重要的特性,用于处理运行时的错误或异常情况。Java 异常是一个对象,表示在程序执行期间发生的异常情况。在 Java 中,异常通常分为检查异常和非检查异常两种。 异常类型 检查异常:是指在编写程序时必须进行捕获或者在方法中进行抛出声明的异常,例如 IOException、Inter…

    C 2023年5月23日
    00
  • C语言如何计算一个整数的位数

    计算一个整数的位数可以分为两个步骤:首先判断其是几位数,然后将其位数输出。以下是这个过程的完整攻略: 判断整数的位数 要判断一个整数有几位,需要用到循环。以下是代码示例: int digitCount(int num) { int count = 0; while (num != 0) { count++; num /= 10; } return count…

    C 2023年5月23日
    00
  • C# Newtonsoft.Json 解析多嵌套json 进行反序列化的实例

    下面是我对这个主题的详细讲解: 标题 “C# Newtonsoft.Json 解析多嵌套json 进行反序列化的实例” 介绍 在现代的Web编程中,JSON是一个非常流行的数据格式,而C#作为一种非常强大的Web编程语言,其处理JSON数据的能力也是非常优秀的。而在C#中,Newtonsoft.Json这个库是一个非常流行和实用的JSON库。它提供了丰富的A…

    C 2023年5月23日
    00
  • C 程序 检查字母是元音还是辅音

    下面是关于“C 程序 检查字母是元音还是辅音”的完整使用攻略。该程序的主要思路是通过判断用户输入的字符是否为元音字母,来确定其为元音还是辅音。下面我们来逐步介绍该程序的使用步骤。 步骤一:复制代码 首先,在开始之前,需要复制如下的 C 语言代码: #include <stdio.h> #include <ctype.h> int ma…

    C 2023年5月9日
    00
合作推广
合作推广
分享本页
返回顶部