如何在一个n-way树中找到一个孩子？

Question

我有一个使用std :: vector实现的n-way树。 Node类仅保存指向根元素的指针，Link类具有指向其自身的std ::向量。当我创建它们时，我命名了每个链接，但是当我尝试使用链接的名称在此树中找到一个节点，但却出现了分段错误时。此外，我意识到我的函数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; 
} 

编辑：重写前面的代码作为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号线这是“根=新链接（）”中的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（），然后无条件地返回结果（循环在AT MOST ONCE处执行）。

另外，Node，Link和root之间的区别对我来说还不是很清楚。这里，我假设你想实现，以尽可能少的额外的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++风格”的版本（不是说这是一个特别的好一个）：

编辑：我只是意识到你正在使用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(); 
    } 
}