#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函数中遇到了Segmentation Fault

首先,第一件事向我解释了崩溃的原因。
向我解释我如何可以改善trie的实现。

最佳答案

您正在为成员变量和局部变量使用相同的名称,如下所示:

trienode* root = root;


编译器无法告诉本地根和trie :: root之间的区别,因此您将其分配给自己。

关于c++ - 使用 vector C++实现Trie的段错误,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/27730235/

10-12 23:30