0

以下は、私が VS2008 で書いた 2 つのサンプル コードです。最初のサンプル コードは正常に動作しますが、(ツリーの) 2 番目のサンプル コードではエラーが発生します。 

 1)
#include<iostream>
using namespace std;

struct node{
        int number;
        struct node *right;
        struct node *left;
    }nodeType;

int insert(struct node *,int);

int main(){

        struct node * root=(struct node *)malloc(sizeof(node));
        root->left=NULL;
        root->right=NULL;
        root->number=10;
        insert(root,100);
      cout<<root->right->number; //This works fine

        return 1;
    }

int insert(struct node * leaf,int data){
        leaf->left =(struct node *)malloc(sizeof(node));
        leaf->right =(struct node *)malloc(sizeof(node));
        struct node *temp = leaf;
        temp->right->number=12;
        temp->left->number=11;
        temp->right->right=NULL;
        temp->right->left=NULL;
        temp->left->left=NULL;
        temp->left->right=NULL;
        return 1;
    }





  2)

#include<iostream>
using namespace std;
struct node{
    int number;
    struct node *right;
    struct node *left;
}nodeType;

int insert(struct node *,int);

int main(){

    int data[50];
    int i;
    for(i=0;i<50;i++){
     data[i]=rand()%100;
    }

    struct node * root=(struct node *)malloc(sizeof(node));
    root->left=NULL;
    root->right=NULL;

    root->number = 36;
    for(i=0;i<50;i++){
        insert(root,data[i]);
    }
    cout<<root->right->number; //This doesn't work, and it throws some memory error. Though it assigns a value(it is 41) which goes to the right side in the insert function, the root's right side pointer is not able to point into that memory location. Similar case with root->.... also.
    return 1;
}

int insert(struct node * leaf,int data){

    if(leaf==NULL){
        leaf = (struct node *)malloc(sizeof(node));
        leaf->number=data;
        leaf->left=NULL;
        leaf->right=NULL;
    }
    else if(data>=leaf->number){
        insert(leaf->right,data);
    }
    else if (data<leaf->number){
        insert(leaf->left,data);
    }
    else
    {

    }

    return 1;
}

2 番目のプログラムで、その場所を指すことができないのはなぜですか?

編集:実行時に発生したエラーは次のとおりです。

test.exe の 0x004114b4 で未処理の例外: 0xC0000005: アクセス違反の読み取り場所 0x000000004。

中断 継続 無視

4

2 に答える 2

4

@whozcraigは、自分を抑えるという正しい男らしい仕事をしました。私は自制心が弱いので、あなたがまだ気づいていない (または症状さえ見られない) コードの問題のいくつかについて話します。

mallocまず、通常は C++ コードで使用しないでください(さらに言えばstruct xxx、構造体のインスタンスを定義することもできません)。

第 2 に、両方にコードがあり、main実際には の ctorinsertによって処理されるべき作業を行っていますnode(たとえば、ノードの子ポインタを NULL に設定します)。

3 番目に、insert決して false にならない条件をテストし、else実行できない空を追加します (ただし、とにかく何もしません)。

次のように書き直すnodeことから始めます。

struct node{
    int number;
    node *right;
    node *left;

    node(int n) : number(n), right(NULL), left(NULL) {}
};

このようにして、ノードの ctor はその子ポインターを NULL に初期化し、必要な値をノード自体に入れます。

これにより、他のコードを大幅に簡素化できます。たとえば、次のinsertようになります。

void insert(node *&leaf, int data){
    if (leaf == NULL)
        leaf = new node(data);
    else if (data < leaf->number)
        insert(leaf->left, data);
    else
        insert(leaf->right, data);
}

これは二分木であるため、実際には 3 つの可能性しかありません: 1) 「現在の」ノードが存在しない -- この場合、新しいデータを「ここに」挿入するか、2) 新しいデータが現在のノードの左側に属するノード、または 3) 現在のノードの右側に属します。このコードは、その 3 方向の決定プロセスを直接反映しています。

のコードのかなりの部分mainも不必要に思えます。たとえば、ツリーにいくつかの数値を挿入したいだけの場合、コードを次のように単純化するのは簡単です。

node *root = NULL;

for (int i = 0; i < 50; i++)
    insert(root, rand() % 100);

最初にデータを配列に入れる必要はありません。生成されたときに各項目をツリーに直接入れることができます。

もちろん、何が起こっているのかを確認するために、ツリー内の特定の 1 つのノードだけでなく、(おそらく) すべてのデータを出力する必要があります。幸いなことに、それも非常に簡単です。

void show(node *tree) {
    if (tree == NULL)
        return;
    show(tree->left);
    std::cout << "\t" << tree->number;
    show(tree->right);
}

これは、ツリーの単純な順序どおりのトラバーサルを行い、トラバースしたときに各ノードを出力します。ツリー用に作成したメモリのリークを避けるために、おそらくツリー内のノードを削除するのと同様のことをしたいと思うでしょう。主な違いは、このためにポストオーダー トラバーサルを実行する必要があることです (両方の子を再帰的に削除してから、現在のノードを削除します)。

もう1つのポイントは、ツリーは実際にはメンバー関数としての独自のクラスである必要があるということinsertです（おそらく、ツリーを破棄してそのすべてのコンテンツを削除するdtorも必要です。show上記のようなものが必要な場合は、おそらくoperator<<to doのオーバーロードそれなど）

于 2013-09-03T08:53:39.660 に答える
3

2 番目の挿入関数は、ノード ポインターを値渡ししています。参照または住所ではありません。したがって、それに対する変更は関数の範囲外には実行されません。

これを変える：

int insert(struct node * leaf,int data)

これに：

int insert(struct node*& leaf,int data)

プロトタイプと実装の両方で。

malloc()C++ プログラムでの の使用に関するすべてのコメントを保留します。それは悪いことですが、それはあなたの問題とは何の関係もありません。

于 2013-09-03T08:11:13.100 に答える