使用向量 C++ 的 trie 实现中的分段错误

Question

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

using namespace std;

#define LOWERCASE_ALPHABET_SiZE 26

typedef int (*ptr) (char );

inline int charToIndex(char a) { return a - 'a'; };

class trienode
{
    private:
        vector< trienode* > child;
        bool leaf;
    public:
        trienode(int );
        ~trienode();
        void initialiseChild(int i);
        trienode* getChild(int i);
        void setLeaf() { leaf = true; };
        bool isLeaf() { return leaf; };
};

trienode::trienode(int size)
{
    for(int i = 0; i < size; i++)
    {
        child.push_back(NULL);
    }
    leaf = false;
}

trienode::~trienode()
{
    for(int i = 0; i < child.size(); i++)
    {
        delete child.at(i);
        child.at(i) = NULL;
    }
}

void trienode::initialiseChild(int i)
{
    child.at(i) = new trienode(child.size());
}

trienode* trienode::getChild(int i)
{
    return child.at(i);
}

class trie
{
    private:
        trienode* root;
        ptr toIndex;
    public:
        trie(int , ptr );
        ~trie();
        void insert(const string& ref);
        bool search(const string& ref);
};

trie::trie(int size, ptr toIndex) : toIndex(toIndex), root(new trienode(size)) { }

trie::~trie()
{
    cout << "In destructor trie" << endl;
    delete root;
    root = NULL;
}

void trie::insert(const string& ref)
{
    int size = ref.size();
    trienode* root = root;
    for(int i = 0; i < size; i++)
    {
        int index = toIndex(ref[i]);
        if(root->getChild(index) == NULL) // crashing in getChild()
        {
            root->initialiseChild(index);
        }
        root = root->getChild(index);
    }
    root->setLeaf();
}

bool trie::search(const string& ref)
{
    trienode* root = root;
    int size = ref.size();
    for(int i = 0; i < size && root != NULL; i++)
    {
        int index = toIndex(ref[i]);
        if((root = root->getChild(index)) == NULL)
        {
            break;
        }
    }
    return (root != NULL && root->isLeaf());
}

int main(int argc,char* argv[])
{
    trie* altrie = new trie(LOWERCASE_ALPHABET_SiZE, charToIndex);
    int n;
    string temp;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> temp;
        altrie->insert(temp);
    }
    int k;
    for(int i = 0; i < k; i++)
    {
        cin >> temp;
        if(altrie->search(temp))
        {
            cout << temp << " exists in the trie" << endl;
        }
        else
        {
            cout << temp << " doesn`t exist in the trie" << endl;
        }
    }
    return 0;
}

我正在创建 Trie，方法是提供它在每个级别中不能有的子节点和函数指针以将给定字符转换为索引。之后，我正在创建 trie 的根节点，当我插入第一个字符串时，它在 getChild 函数

中出现分段错误

首先要向我解释崩溃背后的原因。向我解释如何改进 trie 的实现。

Answer 1

您对成员变量和局部变量使用了相同的名称，如下所示：

trienode* root = root;

编译器无法分辨本地根和 trie::root 之间的差异，因此您将其分配给自己。

使用向量 C++ 的 trie 实现中的分段错误

Segmentation fault in trie implementation using vector c++

c++

vector

trie