专家
公告
财富商城
电子网
旗下网站
首页
问题库
专栏
标签库
话题
专家
NEW
门户
发布
提问题
发文章
Trie树; 模拟了一个简单的输入法;
2019-04-14 21:49
发布
生成海报
站内文章
/
模拟电子
9517
0
1784
#include
using namespace std; //Trie Node structure struct TrieNode { bool isStr; char word[20]; //模拟拼音输入法 TrieNode* next[26]; TrieNode() { isStr=false; memset(next,0,sizeof(next)); } }; //Initiate Trie void initiate(TrieNode *&root) { root=new TrieNode(); } //Insert TrieNode void insertNode(const char *str,TrieNode *root,const char *cn) { TrieNode *location=root; while((*str)!='/0') { if(location->next[(*str)-'a']==NULL) { TrieNode *p=new TrieNode(); location->next[(*str)-'a']=p; } location=location->next[(*str)-'a']; ++str; } location->isStr=true; strcpy(location->word,cn); } //Search TrieNode bool searchNode(const char *str,TrieNode *root) { TrieNode *location=root; while((*str)!='/0'&&location!=NULL) { location=location->next[(*str)-'a']; ++str; } if((location!=NULL)&&(location->isStr)) { cout<
word<
isStr==true) { cout<
word<
next[i]!=0) { char temp[20]; char c[2]; strcpy(temp,str); sprintf(c,"%c",i+'a'); strcat(str,c); printTrie(root->next[i],str); strcpy(str,temp); } } } //销毁Trie void destroy(TrieNode *root) { for(int i=0;i<26;++i) { if(root->next[i]!=0) { destroy(root->next[i]); } } delete root; } //删除单词 void deleteStr(const char *str,TrieNode *root) { //首先找到单词存储的结点,取消标记,删除对应汉字,看该结点的26个next是否全为null //如果不是,那么操作结束 //如果是,那么删除这个结点,将上一个存有单词的结点与该结点之间的结点全部删除即可 // 所以,要求在深搜的过程中,记录存有单词的preNode结点 TrieNode *location=root; TrieNode *pre=0; int preNum; while((*str)!='/0'&&location!=NULL) { pre=location; preNum=(*str)-'a'; location=location->next[(*str)-'a']; ++str; } if((location!=NULL)&&(location->isStr)) { int i; for(i=0;i<26;++i) { if(location->next[i]!=NULL) { break; } } if(i!=26) { location->isStr=false; return; } else { delete location; pre->next[preNum]=NULL; } } else { cout<<"没有存储这个字符"<
>pinYin; cin>>hanZi; while((*pinYin)!='0') { insertNode(pinYin,root,hanZi); ++n; cin>>pinYin; cin>>hanZi; } cout<<"下面可以测试输入法了!您被允许输入"<
>search; searchNode(search,root); } cout<
以下说明是转载的:
l
Trie
原理
Trie
的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
l
Trie
性质
好多人说trie的根节点不包含任何字符信息,我所习惯的trie根节点却是包含信息的,而且认为这样也方便,下面说一下它的性质 (基于本文所讨论的简单trie树)
1.
字符的种数决定每个节点的出度,即branch数组(空间换时间思想)
2.
branch
数组的下标代表字符相对于a的相对位置
3.
采用标记的方法确定是否为字符串。
4.
插入、查找的复杂度均为O(len),len为字符串长度
Ta的文章
更多
>>
浪涌抗扰性试验
0 个评论
一个非常适合单片机的滤波算法
0 个评论
Trie树; 模拟了一个简单的输入法;
0 个评论
热门文章
×
关闭
举报内容
检举类型
检举内容
检举用户
检举原因
广告推广
恶意灌水
回答内容与提问无关
抄袭答案
其他
检举说明(必填)
提交
关闭
×
打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮