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

集合被定义为每个元素都是唯一的元素集合，与数组不同，集合的长度可以变化。添加到集合中的元素一旦添加就不能更改。如果我们想添加相同的修改过的数字，我们需要先删除这个数字，然后在集合中添加修改后的数字。

下面是可以在集合上执行的操作：

• add(value) – 将一个元素添加到集合中
• intersectionSet(S) – 返回两个集合的交集，并将结果存储在集合S中
• toArray() – 将一个集合转换为元素数组
• contains(s) – 检查要搜索的元素是否在集合中，并返回结果
• displaySet() – 从头到尾打印集合中的元素
• getSize() – 获取集合的大小
• unionSet(s) – 返回两个集合的并集，并用集合s存储结果

使用二叉搜索树实现集合

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

• 创建BST的模板

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

template 
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() 函数将节点插入树中。在二叉搜索树中，小于根节点的数据在树的左侧，大于根节点的数据在树的右侧。

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

inorder() 函数用于打印二叉搜索树的中序遍历。

• 在Set类中实现BST模板

当我们为集合内部的工作创建了BST之后，使用模板创建了一个实现BST的Set类。它有一个根指针节点来存储数据，大小变量返回集合的大小。

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

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

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

函数 contains() 检查集合中是否存在特定元素。它在二叉搜索树中内部调用 containsNode() 。

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

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

代码

#include 
#include 
#include 
#include 
#include 
using namespace std;

template 
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* tmp = new Node; // 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  // create a class template for implementing a set in BST
class Set { // Create class set

    Node* 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 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