转载

字典树的实现

最近对字典树来了兴趣,心血来潮,把代码敲了

下面是对字典树的大体解释:

字典树是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。

 字典树的基本功能是用来查询某个单词(前缀)在所有单词中出现次数的一种数据结构,它的插入和查询复杂度都为O(len),Len为单词(前缀)长度,但是它的空间复杂度却非常高,如果字符集是26个字母,那每个节点的度就有26个,典型的以空间换时间结构。

我们可以在字典树的叶子节点记录信息

话不多说,直接代码好理解:

<span style="font-family:SimSun;font-size:18px;">#include<iostream> 
using namespace std;
#include<string.h>
#include<stdio.h>
#include<malloc.h> 
const int MAX = 26;

typedef struct tree
{
	char ch;//字符 
	int  count;//储存单词出现的次数,如果其为0,即没有出现过
	struct tree *next[MAX];//接下来的子节点 ,MAX为26,只有26个字母 

}tree, *Linktree;

Linktree ZDtree = NULL; //字典树的根节点作为全局变量,在以后函数好引用 

void InitZDtree(Linktree &ZDtree)  
{
	ZDtree = (Linktree)malloc(sizeof(tree));
	ZDtree->count = 0;
	for (int i = 0; i<26; i++)//数据节点的初始化 
		ZDtree->next[i] = NULL;
}

void Creattree(Linktree &p, char e)
{
	p = (Linktree)malloc(sizeof(tree));
	p->ch = e;
	p->count = 0;
	for (int i = 0; i<26; i++)//数据节点的初始化 
		p->next[i] = NULL;
}

int  DeleteZDtree(char *s1) //删除操作,只要将单词叶子节点的count值改为0即可 
{
	int n = strlen(s1);
	int i, m;
	Linktree p = ZDtree;
	for (i = 0; i < n; i++)
	{
		m = s1[i] - 'a';
		if (p->next[m] == NULL || p->next[m]->count == 0)
		{
			cout << "The word is not exit" << endl;
			return 0;
		}
		p = p->next[m];
	}
	p->count = 0;
	cout << "The word is already" << endl;
	return 1;
}

int SearchZDtree(char  *s1)
{
	int n = strlen(s1);
	int i,m;
	Linktree p = ZDtree;
	for (i = 0; i < n; i++)
	{
		m = s1[i] - 'a';
		if (p->next[m] == NULL || p->next[m]->count == 0)
		{
			cout << "The word is not exit"<<endl;
			return 0;
		}
		p = p->next[m];
	}
	cout << "The word is exit"<<endl;
	return 1;
}

void InsertZDtree(char *s1)//s1是单词
{
	int i, m;
	Linktree p = ZDtree;
	int n = strlen(s1);
	for (i = 0; i<n; i++)
	{
		m = s1[i] - 'a';
		if (p->next[m] == NULL)
			Creattree(p->next[m], s1[i]);

		p = p->next[m];
		if (i == n - 1)	
			p->count++;
	}
}


int main()
{
	char  s1[MAX];
	char  s2[MAX];
	InitZDtree(ZDtree);//初始化字典树 
	
	while (gets_s(s1)&&s1[0]!='\0') //输入单词以创建字典树 ,空行为结束标志 
	InsertZDtree(s1);
	
    while(gets_s(s2)&&s1[0]!='\0')
    SearchZDtree(s2); //查找单词
    
    while(gets_s(s3)&&s1[0]!='\0') 
    DeleteZDtree(s3); //删除单词 
	 
	return 1;
}</span>
如果看完了,可以做一下这道题:杭电acm1251题

正文到此结束
本文目录