欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构——字典树

程序员文章站 2022-05-20 19:53:28
...

字典树是一个存储字符串集合的一种数据结构,它显著的特点就是牺牲大量的空间来换取程序运行的时间。

当字符串有公共前缀的时候会公用一个分支,节点中的flag标志标记着从头节点到当前节点沿途字母是否构成一个单词,而节点中包含的一个长达26的指针数组的下标是可以理解为当前节点所代表的字母(由于所有小写字母只有26个,所以数组长度为26),而指针指示的是下一个字母的节点的地址。

1.插入操作

void Tries::insert(const string&s)
{
    Tries*cur=this;
    for(int i=0; i<s.size(); i++)
    {
        int index=s[i]-'a';
        if(cur->next[index]==nullptr)
        {
            cur->next[index]=new Tries;
        }
        cur=cur->next[index];
    }
    cur->flag=true;
}

2.查询操作

bool Tries::search(const string&s)
{
    Tries*cur=this;
    for(int i=0; i<s.size(); i++)
    {
        int index=s[i]-'a';
        if(cur->next[index]==nullptr)
        {

            return false;
        }
        cur=cur->next[index];
    }
    if(cur->flag)
        return true;
    return false;
}

 3.销毁操作——注意头节点不是new出来的,所以不能使用delete删除节点,其次是不要使用析构函数来调用Delete函数,否则在其中一个节点被释放的同时会调用析构函数,析构函数再次调用Delete函数,从而造成十分糟糕的死递归!!!!程序运行阶段错误!!!

void Tries::Delete(Tries*p)
{
    for(int i=0;i<26;i++)
    {
        if(p->next[i]!=nullptr)
        {
            Delete(p->next[i]);
        }
    }
    delete p;
}
void Tries::delTree()
{
    for(int i=0;i<26;i++)
    {
        if(this->next[i]!=nullptr)
            Delete(this->next[i]);
    }
}

整体代码: 

#include<iostream>
#include<vector>
#include<cstdbool>
using namespace std;

class Tries
{
private:
    Tries* next[26]= {nullptr};
    bool flag;
    void Delete(Tries*p);
public:
    Tries();
    void insert(const string&s);
    bool search(const string&s);
    void delTree();
};
Tries::Tries()
{
    flag=false;
}
void Tries::insert(const string&s)
{
    Tries*cur=this;
    for(int i=0; i<s.size(); i++)
    {
        int index=s[i]-'a';
        if(cur->next[index]==nullptr)
        {
            cur->next[index]=new Tries;
        }
        cur=cur->next[index];
    }
    cur->flag=true;
}
bool Tries::search(const string&s)
{
    Tries*cur=this;
    for(int i=0; i<s.size(); i++)
    {
        int index=s[i]-'a';
        if(cur->next[index]==nullptr)
            {
                cout<<"hey";
                return false;
            }
            cur=cur->next[index];
    }
    if(cur->flag)
        return true;
    return false;
}
void Tries::Delete(Tries*p)
{
    for(int i=0;i<26;i++)
    {
        if(p->next[i]!=nullptr)
        {
            Delete(p->next[i]);
        }
    }
    delete p;
}
void Tries::delTree()
{
    for(int i=0;i<26;i++)
    {
        if(this->next[i]!=nullptr)
            Delete(this->next[i]);
    }
}
int main()
{
    Tries ok;
    string s="love";
    ok.insert(s);
    cout<<ok.search(s);
    ok.delTree();
    return 0;
}

测试用例:

插入love字符串,并查询字符串love,最后查看程序运行是否正常退出。

运行截图:

数据结构——字典树

相关标签: 算法与数据结构