就是字典树

//2267164 2010-03-30 13:19:45 Accepted 1251 93MS 43800K 1607 B C++ 
#include <iostream>
#include <cstring>
#include <cstdio>
#include <malloc.h>
using namespace std;

const int N = 26;

typedef struct dicTNode
{
	struct dicTNode *child[N];
	int cnt;
}dicTNode, *dictree;

void init(dictree &root)
{//对根节点初始化，根节点不存储任何数据
	root = new dicTNode;
	for(int i = 0; i < N; i++)
		root->child[i] = NULL;
	root->cnt = 0; 
}

void insert(char *str, dictree &root)
{
	dictree curNode, newNode;
	int len = strlen(str);
	int i, j;
	
	if(len == 0)
		return;//无须插入的情况
	curNode = root;
	for(i = 0; i < len; i++)
	if(curNode->child[str[i] - 'a'])
	{//子树存在
		curNode = curNode->child[str[i] - 'a'];
		curNode->cnt++; 
	} else
	{//子树不存在的情况 
		newNode = new dicTNode;
		for(j = 0; j < N; j++)
			newNode->child[j] = NULL;
		newNode->cnt = 1;
		
		curNode->child[str[i] - 'a'] = newNode;
		curNode = curNode->child[str[i] - 'a']; 
	}
}

int find(char *str, dictree root)
{
	int i, len;
	dictree curNode;
	len = strlen(str);
	
	if(len == 0)
		return 0;
	curNode = root;
	for(i = 0; i < len; i++)
	{//一直遍历到串底
		if(curNode->child[str[i] - 'a'])
			curNode = curNode->child[str[i] - 'a'];
		else
			return 0; 
	}
	return curNode->cnt;
}

void dfs(dictree &tc)
{
	if(tc)
	{
		for(int i = 0;i < N; i++)
			dfs(tc->child[i]);
	}
	free(tc);
	tc = NULL;
}
int main()
{
	int n, j, ll;
	char str[12];
	dictree root;
	init(root);
	while(gets(str), strcmp(str, "") != 0)
		insert(str, root);
	while(scanf("%s", str) != EOF)
	{
		printf("%d\n", find(str, root));
	}
	return 0;
}

• 相关文章
• 全局相关文章