Problem C （字典树的查找删除和插入）2016百度之星 - 资格赛（Astar Round1）

本文主要是介绍Problem C （字典树的查找删除和插入）2016百度之星 - 资格赛（Astar Round1），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、insert : 往神奇字典中插入一个单词2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串

5
insert hello
insert hehe
search h
delete he
search hello

Yes
No

Trie  字典树模拟  

有几个提示

1.自己是自己的前缀

2.插入和删除的时候是单词  查找的时候是字符串

AC代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct Trie
{//对应26个小写英文字母 Trie *word[26];//计算次数 int time;Trie(){time=0;for(int i=0;i<26;i++)word[i]=NULL;}
};
//建树 
void build(Trie *root,char *str)
{for(str;*str;str++){if(!root->word[*str-'a']){root->word[*str-'a']=new Trie();}root->word[*str-'a']->time++;root=root->word[*str-'a'];}
}
//删除 
void del(Trie *root,char *str)
{Trie *head,*pre;head=root;int num,i;for(i=0;str[i]!='\0';i++){if(root->word[str[i]-'a']){pre=root;num=root->word[str[i]-'a']->time;root=root->word[str[i]-'a'];}elsebreak;}if(str[i]=='\0'){//回收需要删除的节点 free(pre->word[str[i-1]-'a']);//置为NULL  防止出现野指针 pre->word[str[i-1]-'a']=NULL;for(int i=0;str[i]!='\0';i++){if(head->word[str[i]-'a']!=NULL){head->word[str[i]-'a']->time-=num;head=head->word[str[i]-'a'];}}}
}
//查找 
bool search(Trie *root,char *str)
{int i;for(i=0;str[i]!='\0';i++){if(root->word[str[i]-'a'])root=root->word[str[i]-'a'];elsebreak;}if(str[i]=='\0'){// 如果次数大于0  证明为单词的前缀 if(root->time>0)return true;}return false;
}
int main()
{int n;Trie *root=new Trie();scanf("%d",&n);for(int i=0;i<n;i++){char order[10];char str[35];scanf("%s %s",order,str);if(strcmp(order,"insert")==0){build(root,str);}if(strcmp(order,"delete")==0){del(root,str);}if(strcmp(order,"search")==0){if(search(root,str))puts("Yes");elseputs("No");}}return 0;
}

这篇关于Problem C （字典树的查找删除和插入）2016百度之星 - 资格赛（Astar Round1）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！