| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
简单的字典树操作!#include <iostream>
#include <stdio.h>
#include <string>
#include <map>
#include <string.h>
using namespace std;
//字典树
struct Trie
{
Trie * next[26];
char text[15];
int flag;
Trie()
{
for(int i = 0; i < 26; i++)
{
next[i] = NULL;
flag = 0;
memset(text,0,sizeof(text));
}
}
};
Trie *root;
void Insert(char msg[],char text[])
{
//printf("%s %s\n",msg,text);
Trie *cur = root;
int k;
int i = 0;
while(msg[i])
{
k = msg[i] - 'a';
if(cur->next[k] == NULL)
cur->next[k] = new Trie();
cur = cur->next[k];
i++;
}
cur->flag = 0;
strcpy(cur->text,text);
}
void search_Trie(char msg[])
{
Trie * cur = root;
int k;
int i = 0;
while(msg[i])
{
k = msg[i] - 'a';
if(cur->next[k] == NULL)
{
printf("eh\n");
return;
}
cur = cur->next[k];
i++;
}
if(cur->flag == 0)
printf("%s\n",cur->text);
else
printf("eh\n");
}
void Delete(Trie *root)
{
for(int i = 0; i < 26; i++)
if(root->next[i] != NULL)
Delete(root->next[i]);
delete root;
}
int main()
{
char msg[30];
char eng[15];
char fore[15];
int i,j,k;
root = new Trie();
while(gets(msg) && strlen(msg) != 0)
{
memset(fore,0,sizeof(fore));
memset(eng,0,sizeof(eng));
for(i=0;;i++)
{
if(msg[i] == ' ')
break;
}
msg[i] = '\0';
strcat(eng,msg);
strcpy(fore,&msg[i+1]);
Insert(fore,eng);
}
while(scanf("%s",fore) != EOF)
{
search_Trie(fore);
}
Delete(root);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator