在博问上有个人提问汉字字典树的问题，于是自己手动了实现了一个汉字字典树。和英文字典树不同的是，每个节点的指针不是26个英文字母，汉字字典树的节点的指针是根据输入的汉词来决定的。节点中使用map<string,int>来存放每个汉字的指针
#include <iostream> #include <string.h> #include <stdlib.h> #include <stdio.h> #include <map> using namespace std; //字典树，根节点为1 struct Node { int length=0; string lines=""; map<string,int> words; map<string,int> count; }tree[1005]; //表示字典树的节点数 int len; string res[105]; /*char* word(char *aw,int j) { char w[105]={' '}; int p=0; for(int i=j*3;i<j*3+3;i++) { w[p++]=aw[i]; } return w; } void strcatt(char *as,char *bs,int j) { int l=strlen(as); for(int i=l;i<l+3;i++) { as[i]=bs[j*3+i-l]; } }*/ //往字典树立插入字符串 void insert(string a,int i,int j) { if(i==a.length()/3) { return; } if(tree[j].words[a.substr(i*3,3)]!=0) { insert(a,i+1,tree[j].words[a.substr(i*3,3)]); } else { tree[j].words[a.substr(i*3,3)]=++len; tree[j].lines+=a.substr(i*3,3); tree[j].length+=3; if(i==a.length()/3-1) tree[j].count[a.substr(i*3,3)]++; insert(a,i+1,len); } } /* bool equal(char *ae,char *be) { if(strlen(ae)!=strlen(be)) return false; else { for(int i=0;i<strlen(ae);i++) { if(ae[i]!=be[i]) return false; } return true; } }*/ void remove(Node &s,string x) { int y=0; for(int i=0;i<s.length/3;i++) { if(s.lines.substr(i*3,3)==x) { y=i;break; } } for(int i=y*3;i<s.length;i++) { s.lines[i]=s.lines[i+3]; } s.length-=3; } //删除字符串 bool del(string a,int i,int j) { if(tree[j].words[a.substr(i*3,3)]==0) return false; else { int x=tree[j].words[a.substr(i*3,3)]; tree[j].words[a.substr(i*3,3)]=0; remove(tree[j],a.substr(i*3,3)); return del(a,i+1,x); } } //查询某个字符串为前缀的所有词 void QueryPrefix(string a,int i,int j,string str,int &l2) { if(i>=a.length()/3) { if(tree[j].length==0) { return; } for(int k=0;k<tree[j].length/3;k++) { str+=tree[j].lines.substr(k*3,3); if(tree[j].count[tree[j].lines.substr(k*3,3)]!=0) res[l2++]=str; QueryPrefix(a, i+1, tree[j].words[tree[j].lines.substr(k*3,3)],str,l2); } } else if(tree[j].words[a.substr(i*3,3)]==0) return; else { //strcatt(str,aq,i); str+=a.substr(i*3,3); if(i==a.length()/3-1) res[l2++]=str; QueryPrefix(a, i+1, tree[j].words[a.substr(i*3,3)],str,l2); } } //查询某个字符串是否存在 bool IsExist(string a,int i,int j) { if(i==a.length()/3) { return false; } if(tree[j].words[a.substr(i*3,3)]==0) return false; else { if(i==a.length()/3-1&&tree[j].count[a.substr(i*3,3)]!=0) { return true; } return IsExist(a, i+1,tree[j].words[a.substr(i*3,3)]); } } string input[1005]; int n; string output; int main() { printf("请输入要插入字典树的字符串数组的长度 "); scanf("%d",&n); printf("请输入要插入字典树的字符串数组 "); len=1; for(int i=0;i<n;i++) { cin>>input[i]; insert(input[i],0,1); } printf("请输入key "); cin>>output; printf("查找key是否存在 "); IsExist(output,0, 1); if(IsExist(output,0,1)) printf("key存在 "); else printf("key不存在 "); printf("找出所有以key为前缀的字符串 "); string str=""; int l1=0;int l2=0; QueryPrefix(output, 0, 1,str, l2); for(int i=0;i<l2;i++) cout<<res[i]<<endl; printf("key为一句话，找出key中存在的最长词 "); printf("输入key "); cin>>output; int le=output.length(); string xx=""; string ans=""; int res2=0; for(int i=0;i<le/3;i++) { for(int l=3;i*3+l<=le;l+=3) { xx=output.substr(i*3,l); if(IsExist(xx, 0, 1)) { if(res2<l) { res2=l; ans=xx; } } } } if(res2==0) { printf("不存在 "); } else { cout<<ans<<endl; } return 0; }