不使用 C++ STL 容器实现集合

28 Aug 2024 | 5 分钟阅读

集合定义为元素的集合，其中每个元素都是唯一的。它与数组不同，因为集合可以有可变长度。一旦添加到集合中的元素不能更改。如果我们要添加相同的修改后的数字，请删除该数字并在集合中添加修改后的数字。

以下是对集合可以执行的操作：

add(value) - 此函数在集合中添加一个元素
intersectionSet(S) - 返回集合 S 中两个集合的交集
toArray() - 将集合转换为元素数组
contains(s) - 如果要搜索的元素存在于集合中，则返回该集合
displaySet() - 从头到尾打印集合
getSize() - 获取集合的大小
unionSet(s) - 显示两个集合与集合 s 的并集

使用 BST 实现集合

集合数据结构内部实现 BST（二叉搜索树）数据结构。因此，我们将在树中添加元素，并使用此树模板来实现集合。

创建 BST 模板

在树中，我们有三个成员 - 节点的数据以及指向节点的左指针和右指针。如下所示 -

template <typename T>
struct Node { // Create a node of BST
    T data; // Node value
    Node* left; // Pointer to the left child
    Node* right; // Pointer to the right child
		};

创建树后，我们使用 insert() 函数将节点插入树中。在 BST 中，小于根的数据位于树的左侧，而大于根的数据位于树的右侧。

containsNode() 函数用于检查节点是否存在于树中。

inorder() 函数用于打印 BST 的中序遍历。

在 Set 类中实现 BST 模板

在为集合的内部工作创建 BST 后，将创建一个集合模板来实现 BST。它有一个根指针节点来存储数据，并且 size 变量返回集合的大小。

Set 类有一个默认构造函数将 BST 的根初始化为 NULL，还有一个复制构造函数将一个集合复制到另一个集合。

// create a class template for implementing a set in BST
template <typename T> 
class Set { // Create class set
    Node<T>* root; // Root to store the data
    int size; // It indicates the size of the set
	      };

add() 函数用于向集合中添加值。它通过调用 containsNode() 函数不向集合中添加重复数据。如果有新元素，则将其添加到集合中。

contains() 函数检查特定元素是否存在于集合中。它在内部调用 BST 中的 containsNode()。

displaySet() 函数用于打印集合元素。它在内部调用 BST 的 inorder() 函数。

getSize() 函数返回集合的大小。

编码

#include <algorithm>
#include <iostream>
#include <math.h>
#include <stack>
#include <string>
using namespace std;

template <typename T>
struct Node { // Create a node of BST

    T data; // Node value

    Node* left; // Pointer to the left child

    Node* right; // Pointer to the right child

public:
    // this function prints inorder traversal of BST
    void inorder(Node* r)
    {
        if (r == NULL) { // If we  reach last level
            return;
        }
        inorder(r->left); // print left child
        cout << r->data << " "; // print the node value
        inorder(r->right); // print the right child
    }

    /*
		Function to check if BST contains a node
		with the given data
		
		r pointer to the root node
		 d the data to search in the BST
		The function returns 1 if the node is present in the BST else 0
	*/
    int containsNode(Node* r, T d)
    {
        if (r == NULL) { // If we reach last level or tree is empty
            return 0;
        }
        int x = r->data == d ? 1 : 0; // Check for duplicacy
        // Traverse in right and left subtree
        return x | containsNode(r->left, d) | containsNode(r->right, d);
    }

    /*
		Function to insert a node with
		given data into the BST
		
		r pointer to the root node in the BST 
		d the data to insert in the BST
		return pointer to the root of the resultant BST
	*/
    Node* insert(Node* r, T d)
    {

        if (r == NULL) { // Add where NULL is encountered which means space is present
            Node<T>* tmp = new Node<T>; // Create a new node in BST
            tmp->data = d; // insert the data in the BST
            tmp->left = tmp->right = NULL; // Allocate left and right pointers a NULL
            return tmp; // return current node
        }

        //    Insert the node in the left subtree if data is less than current node data
        if (d < r->data) {
            r->left = insert(r->left, d);
            return r;
        }

        //   Insert the node in the right subtree if data is greater than current node data
        else if (d > r->data) {
            r->right = insert(r->right, d);
            return r;
        }
        else
            return r;
    }
};

template <typename T> // create a class template for implementing a set in BST
class Set { // Create class set

    Node<T>* root; // Root to store the data

    int size; // It indicates the size of the set

public:
    Set() // If no value passed
    {
        root = NULL; // It points to NULL
        size = 0; // size becomes zero
    }

    Set(const Set& s) // Copy constructor
    {
        root = s.root;
        size = s.size;
    }

    void add(const T data) // It add an element to the set
    {
        if (!root->containsNode(root, data)) { // Check if it is the first element
            root = root->insert(root, data); // Insert  the data into the set
            size++; // Increment the size of the set
        }
    }

    bool contains(T data)
    {
        return root->containsNode(root, data) ? true : false;
    }

    void displaySet()
    {
        cout << "{ ";
        root->inorder(root);
        cout << "}" << endl;
    }

    /*
        Function to return the current size of the Set
         
        @return size of set
    */
    int getSize()
    {
        return size;
    }
};

int main()
{

    // Create Set A
    Set<int> A;

    // Add elements to Set A
    A.add(1);
    A.add(2);
    A.add(3);
    A.add(2);

    // Display the contents of Set A
    cout << "A = ";
    A.displaySet();

    // Check if Set A contains some elements
    cout << "A " << (A.contains(3) ? "contains"
                                   : "does not contain")
         << " 3" << endl;
    cout << "A " << (A.contains(4) ? "contains"
                                   : "does not contain")
         << " 4" << endl;
    cout << endl;

    return 0;
}

输出

A = { 1 2 3 }
A contains 3
A does not contain 4

下一个主题C++ 中的作用域解析运算符

不使用 C++ STL 容器实现集合

使用 BST 实现集合

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

不使用 C++ STL 容器实现集合

使用 BST 实现集合

相关帖子

C++ 计时器实现

C++ 输出运算符

C++ 对象指针

C++ 11 尾随返回类型

C++ Shell 排序

在 C++ 中添加两个数字

C++ 奇偶数程序

C++ auto_ptr

C++ 可见性模式

C++ 查找闰年

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器