Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· openaiHugging Face Suzhen/CodeChat

У меня есть класс персистентного массива. Помоги, пожалуйста, написать метод, который бы…

  1. User

    У меня есть класс персистентного массива. Помоги, пожалуйста, написать метод, который бы возвращал в виде int* одну из версий class PersistentArray { private: int* base; int size; std::vector<Node*> versions;

    void buildTree(Node* node, int* arr, int l, int r)
    {
        if (l == r)
        {
            node->val = base[l - 1];
        }
        else
        {
            int m = (l + r) / 2; //std::cout << "m = " << m << "\n";
            node->lchild = new Node();//std::cout << "\nmaking left child";
            buildTree(node->lchild, arr, l, m);
            node->rchild = new  Node();//std::cout << "\nmaking right child";
            buildTree(node->rchild, arr, m + 1, r);
        }
    }
    
    void add(Node* to, Node* from, int l, int r, int npos, int nv)
    {
        if (l == r)
        {
            to->val = nv;
        }
        else
        {
            int m = (l + r) / 2; //std::cout << "m = " << m << "\n";
    
            if (npos <= m)
            {
                to->rchild = from->rchild;
                Node* left = new Node();
                add(left, from->lchild, l, m, npos, nv);
                to->lchild = left;
            }
            else
            {
                to->lchild = from->lchild;
                Node* right = new Node();
                add(right, from->rchild, m + 1, r, npos, nv);
                to->rchild = right;
            }
        }
    }
    
    int get(Node* node, int l, int r, int pos)
    {
        if (l == r)
        {
            return node->val;
        }
    
        else
        {
            int m = (l + r) / 2;
            if (pos <= m)
            {
                return get(node->lchild, l, m, pos);
            }
            else
            {
                return get(node->rchild, m + 1, r, pos);
            }
        }
    }
    

    public: PersistentArray(int _size) { this->base = new int[_size]; this->size = _size;

        versions.push_back(new Node());
    
        int l = 1;
        int r = _size;
    
        buildTree(versions.at(0), base, l, r);
    }
    
    PersistentArray(int* _arr, int _size)
    {
        this->base = new int[_size];
        this->size = _size;
    
        for (int i = 0; i < _size; i++)
        {
            this->base[i] = _arr[i];
        }
    
        int l = 1;
        int r = _size;
    
        versions.push_back(new Node());
        buildTree(versions.at(0), base, l, r);
    }
    
    ~PersistentArray()
    {
        delete[] base;
    }
    
    void changeVersion(int number_of_version, int newPos, int newVal)
    {
        int l = 1;
        int r = size;
    
        add(versions[number_of_version - 1], versions.at(number_of_version - 1), l, r, newPos, newVal);
    }
    
    void addVersion(int rootPos, int newPos, int newVal)
    {
        int l = 1;
        int r = size;
    
        versions.push_back(new Node());
        add(versions.back(), versions.at(rootPos - 1), l, r, newPos, newVal);
    }
    
    int* getStart()
    {
        return this->base;
    }
    
    
    
    
    
    int* getArray(int number_of_version)
    {    
        //
    }
    

    };

  2. Assistant

    Для того чтобы написать метод, который бы возвращал в виде int* одну из версий массива, можно воспользоваться методом get из класса PersistentArray. В этом методе, мы будем искать элемент массива на заданной позиции в соответствующей версии массива и возвращать его значение.

    Ниже приведен код реализации метода getArray:

    int* getArray(int number_of_version)
    {
        Node* root = versions[number_of_version - 1];
        int* result = new int[size];
    
        for (int i = 1; i <= size; i++)
        {
            result[i - 1] = get(root, 1, size, i);
        }
    
        return result;
    }
    

    В этом методе мы создаем новый массив result размером size и заполняем его значениями из версии массива с номером number_of_version. Для этого мы последовательно вызываем метод get для каждой позиции массива и сохраняем полученные значения в result.

    Обратите внимание, что возвращаемый массив result выделяется динамически с помощью оператора new, поэтому не забудьте освободить память, вызвав delete[] для этого массива, когда он будет больше не нужен.