由于 Trie 结构中的字符串导致程序崩溃

Question

我正在实施一个特里树，一旦词尾为 reached.I，它也将打印定义我正在使用字符串作为 definition.But 当我将定义分配给字符串时，代码崩溃了。

#include <bits/stdc++.h>
#define ALPHABET_SIZE 26
#define CHAR_TO_INDEX(c) ((int)c - (int)'0')
using namespace std;
typedef struct trienode{

string definition;          //For Definition of the word
bool isLeaf; 
struct trienode *children[ALPHABET_SIZE]; 

}node;
node* getnode()
{
    int i;
    node *t=new node();
    t->isLeaf=false;
    for(i=0;i<26;i++)
    {
        t->children[i]=NULL;
    }
    return t;
}
void insert(node *root,string s)
{
    node *crawler=root;
    int level,index,length=s.length();
    for(level=0;level<length;level++)
    {
        index=  CHAR_TO_INDEX(s[level]);
        if(crawler->children[index]==NULL)
        {
            crawler->children[index]=getnode();
        }
        crawler=crawler->children[index];
    }
    crawler->definition= "Definition of" + s;  //Here is the code crashing,when I am assigning the definition
    crawler->isLeaf=true;
}

Answer 1

你的代码有很多问题。

我看到的越大，（我想）导致崩溃的问题在下一行

#define CHAR_TO_INDEX(c) ((int)c - (int)'0')

当c是表示数字的字符（从0到9).

问题是当 c 在 a 和 z 之间或（我想）在 A 之间时，您使用它来获取 0 到 25 之间的数字和 Z.

举例：当c为r时，(int)'r' - (int)'0')为114 - 48 = 66。因此，您尝试访问只有 26 个插槽的 children 的插槽 66。

要更正此问题，您可以用这种方式重写 CHAR_TO_INDEX()

#define CHAR_TO_INDEX(c) (c - (int)'a')

然后这样称呼

index = CHAR_TO_INDEX( std::tolower( s[level] ) );

但我认为使用宏是个坏主意，所以我建议你定义一个简单的函数并进行一些检查；像这样

int charToIndec (int ch)
 {
   if ( (ch < int(`a`)) || (ch > int(`z`)) )
    ; // throw something

   return ch - int(`a`);
 }

其他建议，排名不分先后...

您使用的是 C++，而不是 C；所以 trienode 不需要那个类型定义；你可以简单地写

struct trienode {
   string definition; //For Definition of the word
   bool isLeaf; 
   trienode *children[ALPHABET_SIZE]; 
};

并简单地使用结构作为 trienode

再说一次：您使用的是 C++，而不是 C；所以我不明白为什么你写一个函数 getnode() 应该是（恕我直言）trienode 的构造函数；像

trienode () : definition(""), isLeaf(false)
 {
   for ( int i = 0 ; i < ALPHABET_SIZE ; ++i )
      children[i] = NULL;
 }

应该这样使用

crawler->children[index]= new trienode;

无论如何，你已经将ALPHABET_SIZE定义为26；记得到处使用它而不是 26（当 26 是 children 的维度时）；所以用 ALPHABET_SIZE

替换 getnode() 中的 26

包括； bits/stdc++.h 是什么？我不知道，我什至不知道它是否是 C++ 标准包含。建议：使用标准includes.

最后的建议：您使用 new 作为节点；记得 delete 分配的节点；如果您可以使用 C++11 编译器，请考虑使用 std::unique_ptr 的假设来避免这种需要。

p.s.: 对不起我的英语不好

由于 Trie 结构中的字符串导致程序崩溃

Program Crashing due to string in structure in Trie

c++

data-structures

trie