Как получить ребенка в n-образном дереве?

Question

У меня есть дерево n-way, реализованное с использованием std :: vector. Класс Node содержит только указатель на корневой элемент, а класс Link имеет std :: vector указателей на себя. Я назову каждую из своих ссылок, когда я их создаю, но когда я пытаюсь найти узел в этом дереве, используя имя ссылки, но получаю ошибку сегментации. Также я понимаю, что моя функция GetLink() не делает никаких проверок ошибок, я пробовал пару вещей, но они не работали, поэтому, если возможно, было бы очень полезно получить какое-либо предложение о том, как реализовать это в этом случае. Вот мой код:

// in node.h 
class Node { 
public: 
// constructors 
// fuctions 
private: 
Link *root; 
}; 

// in link.h 
class Link { 
public: 
//EDIT: added vector initialization in the constructor 
Link() : my_links(0) { } 
// some functions 
// EDIT: example of making the tree 
bool Load(token) { 
// parsing code based on token 
    else if (strcmp (temp, "link") == 0) 
    { 
     Link* lnk = new Link(); 
     lnk->Load (token); 
     lnk->Init(); 
     AddChild (lnk); 
     lnk->m_parent = this; 
    } 
    // some more parsing code 
} 
void Link::AddChild (Link* pChild) 
{ 
    my_links.push_back(pChild); 
} 

Link* Link::GetLink(char* str) // this is the function that is the problem. 
{ 
    if (strcmp(name, str) == 0) 
    { 
    return this; 
    } 

    for (int i=0; i < (int) my_links.size(); i++) 
    { 
    //Edit: added check for NULL ptr 
    if (my_links[i] == NULL) 
    { 
     fprintf (stderr, "\n\t Couldn't find link\n\n"); 
     break; 
    } 
    //Edit: typo corrected 
    return my_links[i]->GetLink(str); 
    } 
} 

private: 
char name[256]; 
Link* m_parent; 
std::vector<Link*> my_links; 
}; 

// in main.cpp 
static Node* node; 
static Link* link; 
main() 
{ 
    char *str = "link_3"; 
    link = node->GetLink(str); 
    printf("\n found link: %s", link->GetName()); 
    retrun 0; 
} 

EDIT: Переписывание ранее код как MCVE

#include <cstdio> 
#include <vector> 
#include <cstring> 

class Link { 
public: 
//EDIT: added vector initialization in the constructor 
Link() : my_links(0) 
{ 
    m_parent = NULL; 
} 

void SetParent(Link* pParent) 
{ 
    m_parent = pParent; 
} 

// EDIT: example of making the tree 
bool Load(char *str) 
{ 
     unsigned int len; 
     Link* lnk = new Link(); 
     len = strlen(str); 
     strcpy(name, str); 
     lnk->SetParent(this); 
     AddChild (lnk); 
     return true; 
} 

void AddChild (Link* pChild) 
{ 
    my_links.push_back(pChild); 
} 

Link* GetLink(char* str) // this is the function that is the problem. 
{ 
    if (strcmp(name, str) == 0) 
    { 
    return this; 
    } 

    for (int i=0; i < (int) my_links.size(); i++) 
    { 
    //Edit: added check for NULL ptr 
    if (my_links[i] == NULL) 
    { 
     fprintf (stderr, "\n\t Couldn't find link\n\n"); 
     break; 
    } 
    //Edit: typo corrected 
    return my_links[i]->GetLink(str); 
    } 
    fprintf(stderr, "\n\t Cannot get link\n\n"); 
    return 0; 
} 

char* GetName() 
{ 
    return name; 
} 

private: 
char name[256]; 
Link* m_parent; 
std::vector<Link*> my_links; 
}; 


class Node { 
public: 
Node() 
{ 
    root = NULL; 
} 

bool Load (char *str) 
{ 
    unsigned int len; 
    root = new Link(); // here is where the error occurs 
    len = strlen(str); 
    strcpy(name, str); 
    return true; 
} 

void AddChild (char *str) 
{ 
    root->Load(str); 
} 

Link* GetRoot() 
{ 
    return root; 
} 

private: 
char name[256]; 
Link *root; 
}; 

static Node* node; 
static Link* lnk; 
int main() 
{ 
    node->Load((char*)"I am root"); 
    node->AddChild((char*)"I am child 1"); 
    node->AddChild((char*)"I am child 2"); 
    node->AddChild((char*)"I am child 3"); 
    char *str = (char*)"I am child 2"; 
    lnk = node->GetRoot()->GetLink(str); 
    printf("\n found link: %s", lnk->GetName()); 
    return 0; 
} 

Я получаю ошибку сейчас в VS2010 на линии 77, который является "корень = новый Link()" в классе Node , функция Load() является:

Unhandled exception at 0x012e1bbe in nWayTree.exe: 0xC0000005: Access violation writing location 0x00000100. 

Answer 1

причина вы получите ошибку в MCVE является то, что вы никогда не экземпляр node и в результате, node->Load((char*)"I am root"); разыменовывает неинициализированный указатель в результате ип определенного поведения. Фактически вы получаете нарушение доступа, когда ваша программа пытается записать в ячейку памяти, где ожидает переменная-член «root». Вы можете исправить это, написав

static Node* node = new Node(); 

Однако, даже после устранения этой ошибки, ваш MCVE по-прежнему имеет семантические ошибки. Каждый раз, когда вы вызываете node->AddChild, вы не добавляете другого ребенка, но вы переименовываете свой узел и назначаете новую построенную по умолчанию ссылку (без имени) на переменную-член root узла. Кроме того, функция GetLink() не рекурсивно вызывает GetLink() для всех дочерних элементов (если они есть), но только вызывает GetLink() для первого дочернего элемента и затем безоговорочно возвращает результат (цикл выполняется НА САМОМ ONCE).

Также разница между узлом, узлом и связью не совсем понятна для меня. Вот, что я предполагаю, что вы хотите достичь, с минимальным количеством дополнительных C++ (по сравнению с вашим примером), как это возможно:

#include <cstdio> 
#include <vector> 
#include <cstring> 

class Node { 
private: 
    char m_name[256]; 
    Node* m_parent; 
    std::vector<Node*> my_links; 
public: 
    //EDIT: added vector initialization in the constructor 
    Node(const char* name, Node* parent=nullptr) : m_parent(parent), my_links() { 
     strcpy(m_name, name); 
    } 

    void AddChild(const char* childname) { 
     my_links.push_back(new Node(childname,this)); 
    } 

    Node* GetNode(const char* str) { 
     if (strcmp(m_name, str) == 0) { 
      return this; 
     } 
     for (size_t i = 0; i < my_links.size(); i++) 
     { 
      Node* t = my_links[i]->GetNode(str); 
      if (t != NULL) return t; 
     } 
     return NULL; 

    } 

    char* GetName() { 
     return m_name; 
    } 
}; 

Node root((const char*)"I am root"); 

int main() 
{ 
    root.AddChild("I am child 1"); 
    root.AddChild("I am child 2"); 
    root.AddChild("I am child 3"); 
    const char *str1 = "I am child 2"; 
    const char *str2 = "I am child 1 of child 2 of root"; 
    root.GetNode(str1)->AddChild(str2); 
    Node* node = root.GetNode(str2); 
    if (node == NULL) { 
     printf("Link not found"); 
    } else 
    { 
     printf("\n found link: %s", node->GetName()); 
    } 
} 

А вот «современный C++ стиль» версия (не утверждая, что это особенно хорошо один):

EDIT: Я просто понял, что вы используете VS2010, который не сможет скомпилировать следующий пример, потому что он использует некоторые C++ 11 и C++ 14 (текущие стандарты C++). Тем не менее, вы можете создать его со свободной версией VS2013 и должны иметь возможность построить его с любой последней версией g ++ и clang ++ (вам придется добавить флаг «-std = C++ 14» или подобное, хотя).

#include <iostream> 
#include <vector> 
#include <string> 
#include <memory> 

using namespace std; 

class Node { 
private: 
    string m_name; 
    Node* m_parent; 
    vector<unique_ptr<Node>> my_links; 

public: 
    Node(const string& name, Node* parent = nullptr) : 
     m_name(name), 
     m_parent(parent), 
     my_links() 
    {} 

    void AddChild(const string& childname) { 
     my_links.push_back(make_unique<Node>(childname, this)); 
    } 

    Node* GetNode(const string& str) { 
     if (m_name == str) { 
      return this; 
     } 
     for (auto& e:my_links) 
     { 
      Node* t = e->GetNode(str); 
      if (t != nullptr) return t; 
     } 
     return nullptr;   
    } 

    string GetName() { 
     return m_name; 
    } 
}; 

Node root("I am root"); 

int main() 
{ 
    root.AddChild("I am child 1"); 
    root.AddChild("I am child 2"); 
    root.AddChild("I am child 3"); 
    string str1("I am child 2"); 
    string str2("I am child 1 of child 2 of root"); 
    root.GetNode(str1)->AddChild(str2); 
    Node* node = root.GetNode(str2); 
    if (node == nullptr) { 
     cout <<"Link not found"; 
    } else { 
     cout << "found link: "<< node->GetName(); 
    } 
}