小贝子编程

在类内部操作指针



我一直在研究如何解决C++中类内部指针的问题。基本上，所发生的事情不是操纵指向类的指针，而是操纵您的实例。代码：

#include <iostream>
using namespace std;

const char BLACK = 'B';
const char RED = 'R';
template <class T>
class Node{
    public:
        Node *left;
        Node *right;
        Node *parent;
        char color;
        T key;
        Node(T x){
            this->left = NULL;
            this->right = NULL;
            this->parent = NULL;
            this->key = x;
            this->color = RED;
        };
        virtual ~Node(){};
};
template <class T>
class RBTree{
    private:
        int ammount;
        Node<T> *root;
        void destroy_node(Node<T> *&node);      
        void rotateLeft(Node<T> *&x);
        void rotateRight(Node<T> *&y);
        void insertFixUp(Node<T> *&x);
        void printInfo(Node<T> *&x);
    public:
        Node<T> *NIL;
        RBTree();
        virtual ~RBTree();
        void destroy();
        void insert(T x);
};

template <class T>
RBTree<T>::RBTree(){
    this->ammount = 0;
    this->NIL = new Node<T>(-1);
    this->NIL->color = BLACK;
    this->NIL->left = this->NIL->right = this->NIL->parent = this->NIL;

    this->root = this->NIL;
    this->root->color = BLACK;
    this->root->left = this->root->right = this->root->parent = this->NIL;
}

template <class T>
RBTree<T>::~RBTree(){
    this->destroy();
}

template <class T>
void RBTree<T>::destroy_node(Node<T> *&node){
    if(node != this->NIL){
        this->destroy_node(node->left);
        this->destroy_node(node->right);
        delete node;
    }
}
template <class T>
void RBTree<T>::destroy(){
    this->destroy_node(this->root);
}

template <class T>
void RBTree<T>::rotateLeft(Node<T> *&x){
    Node<T> *y = x->right;
    x->right = y->left;
    if(y->left != this->NIL)
        y->left->parent = x;
    y->parent = x->parent;
    if(x->parent == this->NIL)
        this->root = y;
    else if(x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x;
    x->parent = y;
}

template <class T>
void RBTree<T>::rotateRight(Node<T> *&y){
    Node<T> *x = y->left;
    y->left = x->right;
    if(x->right != this->NIL)
        x->right->parent = y;
    cout << "x:"; this->printInfo(x);
    cout << "y:"; this->printInfo(y);
    cout << endl;
    x->parent = y->parent;
    cout << "x:"; this->printInfo(x);
    cout << "y:"; this->printInfo(y);
    cout << endl;
    if(y->parent == this->NIL)
        this->root = x;
    else if(y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x;

    x->right = y;
    y->parent = x;
}

template <class T>
void RBTree<T>::insertFixUp(Node<T> *&z){

    Node<T> *y;
    while(z != this->root and z->parent->color == RED){
        if(z->parent == z->parent->parent->left){
            y = z->parent->parent->right;
            if(y->color == RED){
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            }
            else{
                if(z == z->parent->right){
                    z = z->parent;
                    this->rotateLeft(z);
                }

                z->parent->color = RED;
                z->parent->parent->color = BLACK;
                this->rotateRight(z->parent->parent);
            }
        }
        else{
            y = z->parent->parent->left;
            if(y->color == RED){
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            }
            else{
                if(z == z->parent->left){
                    z = z->parent;
                    this->rotateRight(z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                this->rotateLeft(z->parent->parent);
            }
        }
    }

    this->root->color = BLACK;
}

template <class T>
void RBTree<T>::insert(T val){
    Node<T> *z = new Node<T>(val);
    Node<T> *x = this->root;
    Node<T> *y = this->NIL;
    while(x != this->NIL){
        y = x;
        if(z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    z->parent = y;
    if(y == this->NIL)
        this->root = z;
    else if(z->key < y->key)
        y->left = z;
    else
        y->right = z;

    z->left = this->NIL;
    z->right = this->NIL;
    z->color = RED;
    this->insertFixUp(z);
    this->ammount++;
}

template <class T>
void RBTree<T>::printInfo(Node<T> *&x){
    cout << "  key=";
    cout << x->key;
    cout << "  l->key=";
    if(x->left == this->NIL) 
        cout << "N";
    else 
        cout << x->left->key;
    cout << "  r->key=";
    if(x->right == this->NIL) 
        cout << "N";
    else 
        cout << x->right->key;
    cout << "  p->key=";
    if(x->parent == this->NIL) 
        cout << "N";
    else 
        cout << x->parent->key;
    cout << "  color=" << x->color << endl;
}

int main(){
    srand(time(NULL));
    RBTree<int> *bt = new RBTree<int>();
    int x = 0;
    int vet[9] = {11, 2, 14, 1, 7, 15, 5, 8, 4};
    for(int i=0; i<9; i++){
        x = vet[i];
        bt->insert(x);
    }
    delete bt;
    return 0;
}

好的，当调用rotateRight方法时，printInfos之间的行正在更改y的值，而不仅仅是更改父x指针。

程序给出的结果：

x:  key=7  l->key=2  r->key=8  p->key=11  color=R
y:  key=11  l->key=8  r->key=14  p->key=N  color=B
x:  key=7  l->key=2  r->key=8  p->key=N  color=R
y:  key=-1  l->key=N  r->key=N  p->key=N  color=B

正确的应该是：

x:  key=7  l->key=2  r->key=8  p->key=11  color=R
y:  key=11  l->key=8  r->key=14  p->key=N  color=B
x:  key=7  l->key=2  r->key=8  p->key=N  color=R
y:  key=11  l->key=8  r->key=14  p->key=N  color=B

那么，是什么原因造成的呢？说真的，这很奇怪O.O

基于添加的新代码：您应该将方法签名更改为使用Node<T> *y而不是Node<T> *&y。

例如：void rotateRight(Node<T> *y);

当您使用*&y时，您指的是指向传递给该方法的Node的指针的引用。由于您有它的引用，您可以修改指针指向的位置。当你执行这一行时：

x->parent = y->parent;

x->parent是y（因为x初始化为y->left），y->parent为NIL。所以这条线实际上把y设置为指向零。执行此行后，您将：x->父项=y=NIL

如果不使用*&y，而是使用*y，则会获得y指针引用的副本。所以当你打电话x->parent=y->parent；您不是在修改y，而是在修改复制的引用，从而获得所需的结果。

了解您的代码：

首先，似乎可以将方法签名更改为仅使用指针，因为您不会在方法内部修改它：

void MyClass::myMethod(Node *y){

在这一行中，y->parent被设置为NULL。因此，y的父指针被更改：

y->parent = NULL;

如果y为NULL，这一行可能会出现问题，因为您将取消引用NULL指针。所以最好检查一下。

在这一行中，您声明了一个节点指针x，并将y节点的左指针分配给它。

Node *x = y->left;

最后，将y父节点（由于在第一行设置了它，因此为NULL）分配给x父节点。

x->parent = y->parent;

如果上面一行的y->left为NULL，您可能会遇到问题，因为您将取消引用NULL指针。所以最好检查一下。如果x不为NULL，那么这一行的效果与：x->parent=NULL；

但是，由于不再使用x，因此当方法返回时，它将丢失。话虽如此，你的方法也有同样的效果：

void MyClass::myMethod(Node *y){
    y->parent = NULL;
}

但我建议先检查y：

void MyClass::myMethod(Node *y){
    if (y != NULL){
        y->parent = NULL;
    }
}

我看不出你怎么会进一步更改y，除非你错过了一些代码。

相关内容

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium