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