求大佬帮忙看看为啥输出不正确。。是代码问题还是逻辑问题。。
在Debug的时候发现Node *temp=new Node这个语句运行错误?但不知道为什么
//原题地址http://hihocoder.com/problemset/problem/1014
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
struct Node
{
char ch;
int num;
Node *next;
Node *son;
};
class Trie
{
private:
Node *head; //头部节点
Node *curr; //当前节点
public:
Trie()
{
*head=Node{'a',0,0,0};
}
~Trie();
void add(string str); //添加一个英文单词
void clear(Node *a); //删除以a为头部的子树
int Find(string str); //找到前缀的子树并返回计数
};
void Trie::add(string str)
{
curr=head;//初始化
for (int i=0; i<str.size(); i++)
{
bool flag=1;
while (curr->next)//当前节点的兄弟节点不为空节点时
{
if (curr->ch==str[i])//当前节点的字母为遍历字母
{
curr->num++;//遍历成功 计数+1
if (curr->son)
curr=curr->son;//假如当前节点有子节点 则指向子节点
else//否则就创建新的节点作为子节点 并指向子节点
{
Node *temp=new Node;
*temp=Node{'a',0,0,0};
curr->son=temp;
curr=temp;
}
flag=0;
break;
}
else//遍历不成功就指向下一个节点
{
curr=curr->next;
}
}
if (flag)//此时下一个节点为空节点
{
if (curr->ch==str[i])//遍历成功同上
{
curr->num++;
if (curr->son)
curr=curr->son;
else
{
Node *temp=new Node;
*temp=Node{'a',0,0,0};
curr->son=temp;
curr=temp;
}
}
else//遍历不成功 则创建一个新的next节点 并创http://hihocoder.com/problemset/problem/1014建一个新的子节点 连接上以后 当前节点指向新的next节点的子节点
{
Node *temp=new Node;
Node *son=new Node;
*temp=Node{str[i],0,0,0};
temp->num++;
curr->next=temp;
*son=Node{'a',0,0,0};
temp->son=son;
curr=son;
}
}
}
}
void Trie::clear(Node *a)
{
if (a==0)
return;
clear(a->next);
clear(a->son);
delete a;
}
Trie::~Trie()
{
clear(head->next);
clear(head->son);
}
int Trie::Find(string str)
{
curr=head;//初始化
for (int i=0; i<str.size(); i++)
{
while (curr)//当前节点不是一个空节点
{
if (curr->ch==str[i])
{
curr=curr->son;//指向儿子
break;
}
else
curr=curr->next;//指向下一个
}
if (curr&&i==str.size()-1)//当遇到最后一个字母的时候
return curr->num; //返回最后一个字母的计数
else if (!curr)//当前节点是空节点返回0
return 0;
}
}
int main()
{
Trie tree;
int n;
scanf("%d",&n);
while (n--)
{
char s[11];
scanf("%s",s);
string str;
str=s;
tree.add(str);
}
scanf("%d",&n);
while(n--)
{
char s[11];
scanf("%s",s);
string str;
str=s;
int d=tree.Find(str);
printf("%d\n",d);
}
return 0;
}