数据结构——字典树
程序员文章站
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,最后查看程序运行是否正常退出。
运行截图:
上一篇: 聚类方法的原理以及python实现