如何在一個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(); 
    } 
}