题意:给定一序列的映射关系,然后再给定一些单词,要求如果该单词有映射的单词就输出映射的单词,否则输出"eh"
思路:把给定的映射关系的中的单词建立成字典树,然后输入单词的时候查找即可。但是这一题不能够利用静态分配的思想,应该要利用动态的分配
代码:
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAXN = 100010; const int N = 11; const int M = 26; struct Node{ int index; Node* child[M]; Node(){ index = -1; for(int i = 0 ; i < M ; i++) child[i] = NULL; } }; Node* root; int pos; char word[MAXN][N]; void insert(int index , char* str){ Node* s = root; int len = strlen(str); for(int i = 0 ; i < len ; i++){ int num = str[i]-'a'; if(s->child[num] == NULL) s->child[num] = new Node(); s = s->child[num]; } s->index = index; } int search(char *str){ Node* s = root; int len = strlen(str); for(int i = 0 ; i < len ; i++){ int num = str[i]-'a'; if(s->child[num] == NULL) return -1; s = s->child[num]; } return s->index; } int main(){ pos = 0; root = new Node(); char str[N*3]; char tmp[N]; int cnt = 0; while(gets(str) && str[0] != '\0'){ sscanf(str , "%s %s" , word[cnt] , tmp); insert(cnt++ , tmp); } while(scanf("%s" , tmp) != EOF){ int index = search(tmp); if(index == -1) printf("eh\n"); else printf("%s\n" , word[index]); } return 0; }