Hash涓昏鏄氳繃涓涓猦ash鍑芥暟鏉ュ緩绔嬩竴涓瓧絎︿覆涓庣洰鏍囩殑鏄犲皠錛孒ash鍑芥暟鐨勯夋嫨涓庢煡鎵炬晥鐜囨湁寰堝ぇ鍏崇郴錛岀綉涓婂緢澶氳繖鏂歸潰鐨勪粙緇嶃?br>
Trie鏍戞槸涓縐嶆爲鐘剁粨鏋勶紝榪欓噷鏈夎鏄?/span>銆?/a>褰撶劧緗戜笂榪樺彲浠ユ壘鍒版洿濂界殑浠嬬粛銆傚叾娌℃墿灞曚竴涓妭鐐逛細錛屼細鎵╁睍鍑?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鏇村姞瀹炵敤錛屽茍涓旀晥鐜囦笉璧栵紝寰堝緗戠珯鐨勫疄鏃惰ˉ鍏呭崟璇嶏紙鍗籌紝杈撳叆鍗曡瘝鐨勫墠緙浼氳嚜鍔ㄨˉ鍏呭悗鍗婇儴鍒嗗崟璇嶏級灝辨槸鐢ㄥ畠銆備笁鍙夋爲鐨勬瘡涓妭鐐逛細鏈変竴涓猭ey錛屽乏瀛愭爲錛屽彸瀛愭爲錛屼腑闂村瓙鏍戙傛煡鎵炬垨鏄彃鍏ョ被浼間簬浜屽弶鏍戯紝鑻ユ槸鎻掑叆鐨勬暟鎹ぇ浜巏ey灝辨彃鍏ュ乏瀛愭爲錛岃嫢鏄ぇ浜巏ey灝辨彃鍏ュ彸瀛愭爲錛岀瓑浜巏ey鎻掑叆涓棿瀛愭爲錛堝ソ鍍忓彨璧鋒潵涓嶉『鍙ｏ級錛屽綋鐒跺弽涔嬩害鍙傚叾鍏蜂綋瀹炵幇浠ｇ爜濡備笅錛?
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 }
]]>
]]>