我正在尝试使用类在C中实现trie数据结构 . 在TrieNode类中，我有一个 TrieNode *children[26]; 数组和一个 isEndOfWord 布尔值来确定它是否是结束字 . 在同一个类中，我有其他适合函数的函数，如getter和setter，另外还有insert和search .
每当我尝试添加一个新单词时，通过将true设置为 isEndOfWord ，它也会在每个单词的结尾处将bool值设置为true . 但在搜索功能中，它并不是确定单词的结尾 . 请指导我，因为我是这个数据结构的新手，请评论我编写代码的方式以及编写代码的适当方式（如果感兴趣，以专业的方式） . 谢谢！
#include<cstdio>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
class TrieNode{
private:
TrieNode *children[26];
bool isEndOfWord;
public:
TrieNode(){
for(int i = 0; i < 26; i++){
children[i] = NULL;
}
isEndOfWord = false;
}
bool checkNull(char temp){
cout<<"\nIncheckNULL "<<temp<<" "<<(temp - 'a')<<" \n";
if(children[temp - 'a'] == NULL){
return true;
}
else{
return false;
}
}
void setNode(char temp){
cout<<"Setting node \n";
children[temp - 'a'] = new TrieNode();
}
TrieNode *getNode(char temp){
return children[temp - 'a'];
}
void setEndWord(){
this->isEndOfWord = true;
}
bool getEndWord(){
return this->isEndOfWord;
}
void insert(TrieNode*, string);
bool search(TrieNode*, string);
};
void TrieNode::insert(TrieNode *root, string key){
TrieNode *crawl = root;
//cout<<"key is "<<key<<endl;
int length = sizeof(key)/sizeof(key[0]);
//cout<<"find length\n";
for(int i = 0; key[i] != '\0'; i++){
cout<<"TEST null check key is "<<key[i]<<endl;
if(crawl->checkNull(key[i])){
cout<<"null check key is "<<key[i]<<endl;
crawl->setNode(key[i]);
crawl = crawl->getNode(key[i]);
if(key[i + 1] == '\0'){
cout<<"In setting end word\n";
if(crawl->getEndWord()){
cout<<"Word already exists";
}
else{
crawl->setEndWord();
cout<<"End word setted "<<crawl->getEndWord()<<endl;
}
}
}
else{
if(key[i + 1] == '\0'){
cout<<"In setting end word\n";
if(crawl->getEndWord()){
cout<<"Word already exists";
}
else{
crawl->setEndWord();
cout<<"End word setted\n";
}
}
else{
crawl = crawl->getNode(key[i]);
}
}
}
}
bool TrieNode::search(TrieNode *root, string key){
TrieNode *crawl = root;
cout<<"key is "<<key<<endl;
cout<<"\n In search\n";
int length = sizeof(key)/sizeof(key[0]);
for(int i = 0; key[i] != '\0'; i++){
if(crawl->checkNull(key[i])){
cout<<"INside search checknull"<<endl;
cout<<"Word does not exists"<<"sorry"<<endl;
break;
}
else{
cout<<"IN each character getting getEndWord "<<crawl->getEndWord()<<endl;
if(key[i + 1] == '\0'){
if(crawl->getEndWord()){
cout<<"Word Exists";
}
else{
cout<<"Word does not exists"<<"sorry"<<endl;
break;
}
}
else{
crawl = crawl->getNode(key[i]);
}
}
}
}
int main(){
TrieNode *root = new TrieNode();
cout<<"starting"<<endl;
root->insert(root, "hello");
cout<<"first added"<<endl;
root->insert(root, "anna");
root->insert(root, "anni");
cout<<"words added"<<endl;
root->search(root, "hello");
root->search(root, "anny");
}
3 回答
有很多事情我会给你反馈，但这不是代码审查网站，而是针对具体问题 . 我会简要地指出一些我注意到的事情：
1）不包括C头;用c代替 .
2）什么类型的字符串？
3）你计算长度（错误地，假设问题2的答案是“标准c字符串类”），但你不使用它 .
4）search（）返回一个bool，但你不返回任何东西 . 当您找到单词的结尾时，您应该从该函数返回 .
5）search（）在for循环的顶部调用checkNull（），而不确保它不为null . 在此之后：
crawl = crawl->getNode(key[i]);它可能为null，但是然后你循环并通过指针而不测试它 .6）setNode是一个公共函数，无条件地覆盖给定变量的槽中的任何内容 . 如果某人使用相同的字符两次调用它并泄漏（并且可能会丢失树中的数据），则可以破坏现有的子项 .
7）搜索不需要是TrieNode的成员 . 实际上，它不会通过“this”访问任何数据 . 您可能根本不希望TrieNode公开，而是Trie的内部实现细节，这是搜索功能应该存在的位置，应该存储和管理根 .
8）在c中使用nullptr而不是NULL
9）看起来你需要调试search（），因为当你检查单词结尾时它不在最后一个字母上 .
10）您需要一个析构函数并需要释放您的节点 . 或者将它们存储在unique_ptr <>中，以便在对象超出范围时自动删除 .
11）不要“使用命名空间std;”在 Headers 中 . 它使您的 Headers 有毒，包含在我的代码中 .
您的插入和搜索功能可以简化一点 .
考虑一下 . （阅读下面代码中的注释，它们说明代码的作用）
利用C的力量
std::string你的整个
temp - 'a'逻辑对我来说有点不对劲 . 除非我需要，否则我不会使用ASCII值你为什么要包括一大堆
CHeaders ？只需iostream即可完成cstdio所做的事情 .if(!ptr)是检查NULL的更自然的方法 .在 生产环境 中不要使用
using namespace std;而是仅仅使用cout和endl作为std::. 这样做的原因是为了避免污染标准命名空间 .阅读一本好的CPP OOP书:) . 它会帮助你很多 .
我也笑了
anna和anni. 你的安娜和安妮一定要自豪地成为你的朋友:Dinsert和search函数很乱 . 他们使用相当有人工作的方法来检查字符串的结尾，不必要地复制以及其中一个分支中的错误 .这是更简单的版本 . 它们使用字符串
size作为循环边界，循环结束时所需的动作是在循环之后进行的，这更自然 .我使用了相同的样式，但省略了调试输出以提高可读性 .
此外，代码实际上并没有使用
search作为函数，它没有返回值 . 相反，它依靠调试输出来显示结果 . 现在已经纠正了 . 补充它们的功能如下所示 .