字典树.txt

高效的字符串查找数据结构

#include<stdio.h>
#include<memory.h>
typedef struct TTrie
{
	TTrie *next[26];
	bool terminated;
}Trie;

Trie * new_trie()
{
	Trie *p=new Trie;
	memset(p,0,sizeof(Trie));
	return p;
}

void insert(Trie *trie,char *str)
{
	int i=0;
	Trie *p=trie;
	while(str[i]!='\0')
	{
		if(p->next[str[i]-'a']==NULL)
		{
			p->next[str[i]-'a']=new Trie;
			memset(p->next[str[i]-'a'],0,sizeof(Trie));
		}
		p=p->next[str[i]-'a'];
		i++;		
	}
	p->terminated=1;
}
int search(Trie *trie,char *str)
{
	Trie *p=trie;
	for(int i=0;str[i]!=0;i++)
	{
		if(p->next[str[i]-'a']==NULL)return 0;
		else p=p->next[str[i]-'a'];
	}
	if(p->terminated==1)return 1;
	else return 0;
}

int delet_node(Trie *trie,char *str,int i)
{
	Trie *p=trie;
	Trie *p2=trie;
	int k=i;
	++k;
	if(str[i]=='0')
	{
		for(int j=0;j<26;j++)
		{
			if(p->next[j]!=NULL)
			{
				p->terminated=0;
				return 0;
			}
		}
		return 1;
	}
	p=p->next[str[i]-'a'];
	if(delet_node(p,str,k)==1)
	{
		delete p2->next[str[i]-'a'];
		p2->next[str[i]-'a']=NULL;
		if(p2->terminated==1)return 0;
		for(int j=0;j<26;j++)
		{
			if(p2->next[j]!=NULL)
			{
			//	p->terminated=0;
				return 0;
			}
		}
		return 1;
	}
	return 0;
}

void main()
{
	Trie *trie=new_trie();
	insert(trie,"abc");
	insert(trie,"aba");

	delet_node(trie,"aba0",0);
	printf("%d",search(trie,"abc"));
}


//下面是自己写的字典树
#include<stdio.h>
#include<memory.h>
#include<string>
#include<iostream>
using namespace std;
typedef struct TTrie
{
	TTrie *next[26];
	bool terminated; 
	int num; //这个是用来判断以某一个结点为前缀的有多少个。
}Trie;
Trie T[1000000];
int num,N=0;
Trie * new_trie()
{
	Trie *p=new Trie;
	memset(p,0,sizeof(Trie));
	return p;
}

void insert(Trie *trie,char *str)
{
	int i=0;
	Trie *p=trie;
	while(str[i]!='\0')
	{
		if(p->next[str[i]-'a']==NULL)
		{
			
			p->next[str[i]-'a'] = &T[N++];
			memset(p->next[str[i]-'a'],0,sizeof(Trie));
		}
		p=p->next[str[i]-'a']; 
		p->num ++;
		i++;		
	}
	p->terminated=1;
}
int search(Trie *trie,char *str)
{
	Trie *p=trie;
	for(int i=0;str[i]!=0;i++)
	{
		if(p->next[str[i]-'a']==NULL)return 0;
		else p=p->next[str[i]-'a'];
	}
	if(p->terminated==1)return 1;
	else return 0;
}

//int delet_node(Trie *trie,char *str,int i)
//{
//	Trie *p=trie;
//	Trie *p2=trie;
//	int k=i;
//	++k;
//	if(str[i]=='0')
//	{
//		for(int j=0;j<26;j++)
//		{
//			if(p->next[j]!=NULL)
//			{
//				p->terminated=0;
//				return 0;
//			}
//		}
//		return 1;
//	}
//	p=p->next[str[i]-'a'];
//	if(delet_node(p,str,k)==1)
//	{
//		delete p2->next[str[i]-'a'];
//		p2->next[str[i]-'a']=NULL;
//		if(p2->terminated==1)return 0;
//		for(int j=0;j<26;j++)
//		{
//			if(p2->next[j]!=NULL)
//			{
//			//	p->terminated=0;
//				return 0;
//			}
//		}
//		return 1;
//	}
//	return 0;
//}
int delete_node(Trie *trie,char *str,int i)
{
	if(str[i]==0) {trie->terminated = 0; return 1;} //表示已经找到末尾了。
	if(trie->next[str[i]-'a']==NULL) return 0;
	else 
	{
		if(delete_node(trie->next[str[i]-'a'], str, i+1)==0) return 0;
		else 
		{
			for(int j=0;j<26;j++) 
				if(trie->next[str[i]-'a']->next[j]!=NULL || trie->next[str[i]-'a']->terminated==1)
					return 1;
			trie->next[str[i]-'a']=NULL;
			return 1;
		}
	}
}
void main()
{
	Trie *Root=new_trie();
	insert(Root,"bcc");
	insert(Root,"bccd");
	search(Root,"bccd");
	delete_node(Root,"bcc",0);
}