coreBugZJ

此 blog 已弃。

字典树

高效处理大量较短字符串的插入查找


 1 // DictInsert( &rootDict, s, id )
 2 
 3 // DictSearch( rootDict, s )
 4 
 5 
 6 
 7 #include <stdlib.h>
 8 
 9 
10 
11 #define  T  250
12 
13 typedef struct __DICT
14 
15 {
16 
17         int id;
18 
19         struct __DICT * ch[T];
20 
21 } DICT;
22 
23 
24 
25 DICT * rootDict = 0;
26 
27 
28 
29 void DictInsert( DICT ** roo, const char * p, int id ){
30 
31         for(;;){
32 
33                 if*roo == 0 ){
34 
35                         *roo = (DICT*)malloc( sizeof(DICT) );
36 
37                         (*roo)->id = 0;
38 
39                         memset( (*roo)->ch, 0sizeof( (*roo)->ch ) );
40 
41                 }
42 
43                 if*p ){
44 
45                         roo = &( (*roo)->ch[*p++] );
46 
47                 }
48 
49                 else{
50 
51                         (*roo)->id = id;
52 
53                         return;
54 
55                 }
56 
57         }
58 
59 }
60 
61 
62 
63 int DictSearch( DICT * roo, const char * p ){
64 
65         for(;;){
66 
67                 if( roo == 0 ){
68 
69                         return 0;
70 
71                 }
72 
73                 if*p ){
74 
75                         roo = roo->ch[*p++];
76 
77                 }
78 
79                 else{
80 
81                         return roo->id;
82 
83                 }
84 
85         }
86 
87 }
88 
89 


posted on 2011-03-20 19:51 coreBugZJ 阅读(1433) 评论(0)  编辑 收藏 引用 所属分类: DataStructure


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理