1

ツリーのノードに int を挿入しようとする関数を作成しています。私の知る限り、私の挿入機能は完璧に機能しますが、機能の外では決して起こらなかったようです。これが私のコードです：

lcrs.h:

using namespace std;
#include <cstdlib>
#include <iostream>

class node{
        public:
        int data;
        node *right;
        node *below;

        node()
        {
                right = NULL;
                below = NULL;
        }
};

class lcrs{
        public:
        node *root;
        bool search(int, node*);
        void print(node*);
        void insert(int, node*);
        int getHeight(node*);

        lcrs()
        {
                root = NULL;
        }
};

そしてlcrs.cpp:

using namespace std;
#include "lcrs.h"

bool lcrs::search(int x, node *b)
{
        if(b == NULL)
                return false;
        else
        {
                if(b->data == x)
                        return true;
                else
                {
                        return search(x, b->right) || search(x, b->below);
                }
        }
}

void lcrs::print(node *z)
{
        if(z->right == NULL && z->below == NULL)
        {
                cout << z->data << endl;
        }
        else if(z->below == NULL && z->right != NULL)
        {
                cout << z->data << ", ";
                print(z->right);
        }
        }
        else if(z->below != NULL && z->right == NULL)
        {
                cout << z->data << ", ";
                print(z->below);
        }
        else
        {
                print(z->right);
                print(z->below);
        }
}

void lcrs::insert(int x, node *a)
{
        if(a == NULL)
        {
                node *newnode;
                newnode = new node;
                newnode->data = x;
                a = newnode;
                cout << a->data << endl;
        }
        else if(a->data < x)
        {
                if(a->right != NULL)
                {
                        insert(x, a->right);
                }
                else
                        a->right->data = x;
        }
        else
        {
                if(a->below != NULL)
                {
                        insert(x, a->below);
                }
                else
                {
                        a->below->data = x;
                }
        }
}

int lcrs::getHeight(node *h)
{
        int height = 0;
        if(h->below != NULL)
        {
                height ++;
                return getHeight(h->below);
        }
        else
                return height;
}

そして最後に私のmain.cpp：

using namespace std;
#include <iostream>
#include <cstdlib>
#include <cstring>
#include "lcrs.h"

int main()
{
char *temp1;
char *temp2;
temp1 = new char;
temp2 = new char;

lcrs tree;

do{
        cout << "LCRS> ";
        cin >> temp1;
        if(strcmp(temp1, "quit") == 0)
        {
                return 0;
        }
        if(strcmp(temp1, "insert") == 0)
        {       cin >> temp2;
                bool error;
                for(int i=0; i<strlen(temp2)-1; i++)
                {
                        if(!isdigit(temp2[i]))
                        {
                                cout << "Error!" << endl;
                                error = true;
                        }
                }
                if(!error)
                {
                        tree.insert(atoi(temp2), tree.root);
                        if(tree.root == NULL)
                                cout << "Root is null." << endl;
                        else
                                cout << tree.root->data << endl;
                }
        }
        else if(strcmp(temp1, "height") == 0)
        {
                if(tree.root == NULL)
                        cout << "-1" << endl;
                else
                        cout << tree.getHeight(tree.root);
        }
        else if(strcmp(temp1, "preorder") == 0)
        {
                tree.print(tree.root);
        }
}while(strcmp(temp1, "quit") !=0);

return 0;
}

したがって、挿入関数が実際にtreeのルートを変更していないことは理解していますが、その理由はわかりません。

よろしくお願いいたします。

4

2 に答える 2

2

あなたのコード:

void lcrs::insert(int x, node *a)
{
        if(a == NULL)
        {
                node *newnode;
                newnode = new node;
                newnode->data = x;
                a = newnode;

↑ この代入は、値で渡されたため、実際の引数を更新しません。

                cout << a->data << endl;
        }
        else if(a->data < x)
        {
                if(a->right != NULL)
                {
                        insert(x, a->right);
                }
                else
                        a->right->data = x;

↑ これでa->rightnullpointer であることがわかります (確認済み)。その nullpointer を逆参照すると、Undefined Behaviorが生成されます。たとえば、クラッシュ。

        }
        else
        {
                if(a->below != NULL)
                {
                        insert(x, a->below);
                }
                else
                {
                        a->below->data = x;
                }

↑ これでa->belownullpointer であることがわかります (確認済み)。その nullpointer を逆参照すると、Undefined Behaviorが生成されます。たとえば、クラッシュ。} }

一般的なコメントとして、below2rightつの比喩が混在しています。belowそれらを and above、またはleftandと呼ぶ方がよいでしょうright。後者の選択は非常に一般的です。

(非更新の問題を修正するために) 参照によってノード ポインターを渡す代わりに、関数の結果として返すことを検討してください。

于 2012-11-13T03:28:01.910 に答える
1

値渡しを使用してポインタを渡しています。参照渡しを取得するには、それ自体ではなくvoid lcrs::insert(int x, node * & a)への参照を渡すものを使用する必要があります。ノードへのポインターがローカル変数にコピーされ、関数内で参照されます。その後、関数はコピー (およびそれが指しているメモリ) を自由に変更できますが、関数が戻ると、呼び出し元はまだ元のファイルを見ているため、コピーで何が起こったのかわかりません。 aaa

参照渡しでは、一方がコピーを使用し、他方がオリジナルを使用するのではなく、呼び出し元と呼び出された関数の両方が同じものを使用します。

于 2012-11-13T03:34:46.157 に答える