Hash涓昏鏄氳繃涓涓猦ash鍑芥暟鏉ュ緩绔嬩竴涓瓧絎︿覆涓庣洰鏍囩殑鏄犲皠錛孒ash鍑芥暟鐨勯夋嫨涓庢煡鎵炬晥鐜囨湁寰堝ぇ鍏崇郴錛岀綉涓婂緢澶氳繖鏂歸潰鐨勪粙緇嶃?br>
Trie鏍?wèi)鏄竴縐嶆爲(wèi)鐘剁粨鏋勶紝榪欓噷鏈夎鏄?/span>銆?/a>褰撶劧緗戜笂榪樺彲浠ユ壘鍒版洿濂界殑浠嬬粛銆傚叾娌℃墿灞曚竴涓妭鐐逛細(xì)錛屼細(xì)鎵╁睍鍑?6錛堣嫢鏄彧澶勭悊鏅氬瓧絎︼紝涓嶅尯鍒嗗ぇ灝忓啓錛変釜鑺傜偣錛屽ぇ澶х殑嫻垂浜嗗瓨鍌ㄧ┖闂淬傚叾浠ｇ爜濡備笅錛?
1 const int M=26;
2 const char CH='A';
3 struct node
4 {
5 bool isend;
6 node* child[M];
7 node()
8 {
9 isend=false;
10 for(int i=0;i<M;++i)
11 child[i]=NULL;
12 }
13 };
14 node *root;
15 void Insert(char str[],node* &root)
16 {
17 if(root==NULL)
18 root=new node;
19 node* p=root;
20 int i=0;
21 while(str[i]!='\0')
22 {
23 if(p->child[str[i]-CH]==NULL)
24 p->child[str[i]-CH]=new node;
25 p=p->child[str[i]-CH];
26 ++i;
27 }
28 p->isend=true;
29 }
30 bool Seach(char str[],node* root)
31 {
32 node* p=root;
33 int i=0;
34 while(str[i]!='\0')
35 {
36 if(p->child[str[i]-CH]==NULL)
37 return false;
38 else p=p->child[str[i]-CH];
39 ++i;
40 }
41 if(p->isend) return true;
42 else return false;
43
44 }
2 const char CH='A';
3 struct node
4 {
5 bool isend;
6 node* child[M];
7 node()
8 {
9 isend=false;
10 for(int i=0;i<M;++i)
11 child[i]=NULL;
12 }
13 };
14 node *root;
15 void Insert(char str[],node* &root)
16 {
17 if(root==NULL)
18 root=new node;
19 node* p=root;
20 int i=0;
21 while(str[i]!='\0')
22 {
23 if(p->child[str[i]-CH]==NULL)
24 p->child[str[i]-CH]=new node;
25 p=p->child[str[i]-CH];
26 ++i;
27 }
28 p->isend=true;
29 }
30 bool Seach(char str[],node* root)
31 {
32 node* p=root;
33 int i=0;
34 while(str[i]!='\0')
35 {
36 if(p->child[str[i]-CH]==NULL)
37 return false;
38 else p=p->child[str[i]-CH];
39 ++i;
40 }
41 if(p->isend) return true;
42 else return false;
43
44 }
涓夊弶鏍?/span>鏈塼rie鐨勪紭鐐癸紝鍗村張姣攖rie鍗犵敤鐨勭┖闂村皬錛屽ソ鍍忚繖涓笢瑗挎瘮trie鏇村姞瀹炵敤錛屽茍涓旀晥鐜囦笉璧栵紝寰堝緗戠珯鐨勫疄鏃惰ˉ鍏呭崟璇嶏紙鍗籌紝杈撳叆鍗曡瘝鐨勫墠緙浼?xì)鑷姩琛ュ厖鍚庡崐閮ㄥ垎鍗曡瘝锛墳鏄敤瀹冦備笁鍙夋爲(wèi)鐨勬瘡涓妭鐐逛細(xì)鏈変竴涓猭ey錛屽乏瀛愭爲(wèi)錛屽彸瀛愭爲(wèi)錛屼腑闂村瓙鏍?wèi)銆傛煡鎵炬垨鏄彃鍏ョ被浼間簬浜屽弶鏍?wèi)锛岃嫢鏄彃鍏ョ殑鏁版嵁澶т簬key灝辨彃鍏ュ乏瀛愭爲(wèi)錛岃嫢鏄ぇ浜巏ey灝辨彃鍏ュ彸瀛愭爲(wèi)錛岀瓑浜巏ey鎻掑叆涓棿瀛愭爲(wèi)錛堝ソ鍍忓彨璧鋒潵涓嶉『鍙ｏ級錛屽綋鐒跺弽涔嬩害鍙傚叾鍏蜂綋瀹炵幇浠ｇ爜濡備笅錛?
1 struct node
2 {
3 node* l;
4 node* r;
5 node* mid;
6 char key;
7 bool isend;
8 node():l(NULL),r(NULL),mid(NULL),isend(false),key(0){}
9 };
10 void insert(char *str,node* &root)
11 {
12 if(root==NULL)
13 {
14 root=new node;
15 root->key=str[0];
16 }
17 node* p=root;
18 node* t=p;
19 while(*str)
20 {
21 if(*str>p->key)
22 {
23 if(p->r==NULL)
24 {
25 p->r=new node;
26 p->r->key=*str;
27 }
28 p=p->r;
29 }
30 else if(*str<p->key)
31 {
32 if(p->l==NULL)
33 {
34 p->l=new node;
35 p->l->key=*str;
36 }
37 p=p->l;
38 }
39 else
40 {
41 ++str;
42 if(*str=='\0') break;
43 if(p->mid==NULL)
44 {
45 p->mid=new node;
46 p->mid->key=*str;
47 }
48 p=p->mid;
49 }
50 }
51 p->isend=true;
52 }
53 bool search(char *str,node* root)
54 {
55 while(*str)
56 {
57 if(*str> root->key)
58 {
59 root=root->r;
60 }
61 else if(*str<root->key)
62 {
63 root=root->l;
64 }
65 else
66 {
67 ++str;
68 if(*str!='\0')
69 root=root->mid;
70 }
71 if(root==NULL) return false;
72 }
73 if(root->isend) return true;
74 else return false;
75 }
2 {
3 node* l;
4 node* r;
5 node* mid;
6 char key;
7 bool isend;
8 node():l(NULL),r(NULL),mid(NULL),isend(false),key(0){}
9 };
10 void insert(char *str,node* &root)
11 {
12 if(root==NULL)
13 {
14 root=new node;
15 root->key=str[0];
16 }
17 node* p=root;
18 node* t=p;
19 while(*str)
20 {
21 if(*str>p->key)
22 {
23 if(p->r==NULL)
24 {
25 p->r=new node;
26 p->r->key=*str;
27 }
28 p=p->r;
29 }
30 else if(*str<p->key)
31 {
32 if(p->l==NULL)
33 {
34 p->l=new node;
35 p->l->key=*str;
36 }
37 p=p->l;
38 }
39 else
40 {
41 ++str;
42 if(*str=='\0') break;
43 if(p->mid==NULL)
44 {
45 p->mid=new node;
46 p->mid->key=*str;
47 }
48 p=p->mid;
49 }
50 }
51 p->isend=true;
52 }
53 bool search(char *str,node* root)
54 {
55 while(*str)
56 {
57 if(*str> root->key)
58 {
59 root=root->r;
60 }
61 else if(*str<root->key)
62 {
63 root=root->l;
64 }
65 else
66 {
67 ++str;
68 if(*str!='\0')
69 root=root->mid;
70 }
71 if(root==NULL) return false;
72 }
73 if(root->isend) return true;
74 else return false;
75 }
]]>
]]>