Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Access violation przy rekursywnym tworzeniu drzewa

Ostatnio zmodyfikowano 2016-04-06 01:49
Autor Wiadomość
WaffleWarrior
Temat założony przez niniejszego użytkownika
Access violation przy rekursywnym tworzeniu drzewa
» 2016-04-06 00:29:40
Mam za zadanie przekształcić w drzewo notację prefixową. Napisałem z pomocą wskaźników drzewo, ale przy rekursywnym wywołaniu funkcji, dostaję błąd. Przekazuję root przez wskaźnik, a mimo to leaf (który powinien teraz wskazywać na root?) nie alokuje pamieci dla left i right Oto kod:

Tree.cpp:

C/C++
#include "stdafx.h"
#include "Tree.h"
#include <iomanip>


Tree::Tree()
{
    root = NULL;
   
   
}

void Tree::insert( Node * leaf, std::string str )
{
    char c = str[ 0 ];
    if( isdigit( c ) )
    {
        if( leaf->left == NULL ) //access violation
        {
            leaf->left = new Node;
            leaf->left->keyValue = c;
           
            leaf->left->left = NULL;
            leaf->left->right = NULL;
        }
        else
        {
            leaf->right = new Node;
            leaf->right->keyValue = c;
           
            leaf->right->left = NULL;
            leaf->right->right = NULL;
        }
    }
    else
    {
        str.erase( 0, 1 );
        insert( leaf->left, str );
       
        str.erase( 0, 1 );
        insert( leaf->right, str );
    }
    str.erase( 0, 1 );
    c = str[ 0 ];
}

void Tree::TreeFromExpression( std::string str )
{
    char c = str[ 0 ];
   
    while( !str.empty() )
    {
        if( root != NULL )
        {
            insert( root, str );
        }
        else
        {
            root = new Node;
            root->keyValue = c;
            str.erase( 0, 1 );
            c = str[ 0 ];
            root->left = NULL;
            root->right = NULL;
        }
    }
   
   
}

void Tree::PrintTree( Node * start, int indentation )
{
    if( start != NULL )
    {
        std::cout << start->keyValue << "\n";
        if( start->left )
             PrintTree( start->left, indentation + 4 );
       
        if( start->right )
             PrintTree( start->right, indentation + 4 );
       
        if( indentation )
             std::cout << std::setw( indentation ) << ' ';
       
    }
}







Tree::~Tree()
{
}

Tree.h:

C/C++
#pragma once
#include "Node.h"
#include <iostream>
class Tree
{
public:
    Tree();
    void TreeFromExpression( std::string str );
    void PrintTree( Node * start, int indentation = 0 );
    ~Tree();
private:
    void insert( Node * leaf, std::string str );
    Node * root;
   
};

Node.h:
C/C++
#pragma once
struct Node {
    int keyValue;
    Node * left;
    Node * right;
};

Main.cpp:

C/C++
#include "stdafx.h"
#include "Tree.h"
#include "ExpressionEval.h"


int main()
{
    Tree testTree;
    std::string str = "+*12-34";
   
    testTree.TreeFromExpression( str );
   
    return 0;
}
P-147006
wojtu111
OK
» 2016-04-06 01:49:29
Ok, popatrzyłem w Twój kod i jest taki problem, że

C/C++
if( isdigit( c ) ) //(1) Pierwszy znak to + więc idziemy do else
{
    if( leaf->left == NULL ) // (3) Ten leaf jest tak naprawdę root->left(NULL!)->left
    {
        leaf->left = new Node;
        leaf->left->keyValue = c;
       
        leaf->left->left = NULL;
        leaf->left->right = NULL;
    }
    else
    {
        leaf->right = new Node;
        leaf->right->keyValue = c;
       
        leaf->right->left = NULL;
        leaf->right->right = NULL;
    }
}
else
{
    str.erase( 0, 1 );
    insert( leaf->left, str ); // (2) Zanim dojdzie tam najpierw wchodzi tutaj!!!! A więc robimy root->left i przekazujemy NULL;
   
    str.erase( 0, 1 );
    insert( leaf->right, str );
}
 Jak najbardziej w tym miejscu jest błąd ponieważ po pierwszym wejściu okazuje się że nie jest digit więc dajesz insert do leaf->left ( gdzie leaf jest jeszcze root ) a ten leaf->left nie został stworzony i jest NULL a więc robisz NULL->left(3).

Mam nadzieję że nie chociaż troszkę wyjaśniłem (jestem słaby w tłumaczeniu :D ). Ogólnie masz tam jeszcze kilka błędów, jednak jako że to jest jakieś zadanie (nie wiem czy konkursowe czy szkolne/uczelniane to nic nie piszę :) )
P-147007
« 1 »
  Strona 1 z 1