0

私は現在、Red Black Tree の単純なバージョンを実装する課題に取り組んでいます。私は現在Xcodeで作業しており、現在エラーが発生していますGDB: Program received signal: EXC_BAD_ACCESS...これはメモリリークであると想定しています...しかし、なぜこれが起こっているのかについての理由を見つけることができないようです. デバッガーは、問題が私のRedBlackTree::treeInsert(char *data)関数にあることを示しました....具体的には、 while ループの本体にある if ステートメントを使用していますif (strcmp(data, x->data) < 0)。

デバッガーは、char (文字 A) を格納していることthis = 0x7fff5fc01052を示します。data = 0x100001a61ただしx = 0x4810c48348ec8948、すべてのプロパティ (親、左、右、データ) がすべて空であることを示しています。

次に試したことは、これらの変数をコンストラクターのようNilに初期化することでした。node()しかし、これによりエラーが発生しました：'Nil' was not declared in this scope...現在、それらをコメントアウトしています。ここで何が起こっているのかわからない..？どんな助けでも大歓迎です。

class node
{
public:
char         *data;         // Data containing one character
node         *parent;       // pointer to this node's parent
node         *left;          // pointer to this node's left child
node         *right;          // pointer to this node's right child
bool         isRed;         // bool value to specify color of node
node();
};

node::node(){
this->data = new char[1];
isRed = true;
//this->parent = Nil;
//this->left = Nil;
//this->right = Nil;
}

赤黒木クラスとメソッド

class RedBlackTree {
public: 
/*constructor*/
RedBlackTree();

node* getRoot(){
    return this->Root;
}

/*RB-INSERT*/
void rbInsert(char *data);
node treeInsert(char *data);
void rbInsertFixup(node *z);

/*ROTATE*/
void leftRotate(node *z);
void rightRotate(node *z);

/*INORDER TRAVERSAL*/
void inOrderPrint(node *root);



private:
node    *Root;    /*root*/
node    *Nil;    /*leaf*/

};



RedBlackTree::RedBlackTree() 
{
this->Nil = new node();
this->Root = Nil;
}

void RedBlackTree::rbInsert(char *data){
node z = treeInsert(data);
rbInsertFixup(&z);  

} // end rbInsert()

node RedBlackTree::treeInsert(char *data){

node *x;
node *y;
node *z;

y = Nil;
x = Root;
while (x!= Nil) {
    y = x;
    if (strcmp(data, x->data) < 0) {
        x = x->left;
    } else {
        x = x->right;
    }
}
z = new node(); // create a new node
z->data = data;
z->parent = y;
z->isRed = true; // set  new node as red 
z->left = Nil;
z->right = Nil;

if (y == Nil) {
    Root = z;
} else {
    if (strcmp(data, y->data)<= 0) {
        y->left = z;
    } else {
        y->right = z;
    }

}
return *z;
}

ここに私の主な機能があります

int main(){


RedBlackTree *RBT;
node* root = RBT->getRoot();
RBT->rbInsert((char *)"A");
RBT->inOrderPrint(root);
return 0;

}
4

2 に答える 2

1

あちこちでバッファオーバーフローが発生しています! 1 文字を含む文字列は、特殊な終了文字も持っているため、実際には2文字です。データの 1 文字にメモリを割り当てますが、文字列を使用するとこれらのバッファがオーバーフローします。

于 2013-06-17T01:26:06.843 に答える
0

主に、RBT でツリーへのポインターを初期化せずに持っているだけで、未定義の動作ランドを呼び出します。

（そしてコードには他にもたくさんの疑わしい点があります）

于 2013-06-17T01:24:53.660 に答える