Ewharain 2017-10-15 14:18
浏览 348

Trie树的具体实现的问题

求大佬帮忙看看为啥输出不正确。。是代码问题还是逻辑问题。。
在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;
}

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 outlook无法配置成功
    • ¥15 Pwm双极模式H桥驱动控制电机
    • ¥30 这是哪个作者做的宝宝起名网站
    • ¥60 版本过低apk如何修改可以兼容新的安卓系统
    • ¥25 由IPR导致的DRIVER_POWER_STATE_FAILURE蓝屏
    • ¥50 有数据,怎么建立模型求影响全要素生产率的因素
    • ¥50 有数据,怎么用matlab求全要素生产率
    • ¥15 TI的insta-spin例程
    • ¥15 完成下列问题完成下列问题
    • ¥15 C#算法问题, 不知道怎么处理这个数据的转换