好不容易写的一个模版~本来是想按照我们数据结构教程的trie树来写，但是他的实现我实在觉得太难
所以还是采用简化版的trie树

这个应该算是比较标准的trie树结构，但是他的插入实现起来不仅仅是插入本身的单词，可能还需要修改原来的数结构
比如说本身已经存在了bobwhite，现在添加bobwhq，就要在第二层的基础上继续扩展，bobwhite的位置也要重新定位，删除操作也是这样
可能还要上移某些单词，这个昨天试了很久，写出来的都不行。
而且对这种字典树的结构本身我的理解就很混乱。
简化版的trie树

以下这种实现方法是根据别人改编的，昨天被逼得没办法还是觉得简化版的，突然发现个牛人的写法和我的很相似（这着实还让我激动了下下），就边学习边改了，呵呵
它是根据杭电的一道题来写的，以下是我的代码：
http://acm.hdu.edu.cn/showproblem.php?pid=1247
#include < iostream >
#define keyNum26
#define MaxN50
struct trie ... {
struct trieNode ... { // trie结点的结构
trieNode * link[keyNum]; // 下标为'A','B','C',,'Z'的指针数组
int num[keyNum]; // 插入key的次数
trieNode() ... {
memset(num, 0 , sizeof (num));
memset(link,NULL, sizeof (link));
}
void init() ... {
memset(link,NULL, sizeof (link));
memset(num, 0 , sizeof (num));
}
} ;
trieNode * root;
trie()
... {
root = (trieNode * )malloc( sizeof (trieNode)); // 初始化时为root申请了空间
root -> init();
}
bool Search( char * );
void Insert( char []);
void Delete(trieNode * );
} ;
bool trie::Search( char * x)
... {
if ( * x == 0 ) return false ;
trieNode * current = root;
x ++ ;
while ( * x) ... {
if (current -> link[ * (x - 1 ) - ' a ' ])
current = current -> link[ * (x - 1 ) - ' a ' ];
else break ;
x ++ ;
}
if ( * x == 0 && current -> num[ * (x - 1 ) - ' a ' ])
return true ;
else return false ;
}
void trie::Delete(trieNode * t)
... {
int i;
for (i = 0 ;i < keyNum;i ++ )
if (t -> link[i])Delete(t -> link[i]);
memset(t -> num, 0 , sizeof (t -> num));
delete(t);
}
void trie::Insert( char x[])
... {
trieNode * current = root;
int i = 1 ;
while (x[i]) ... {
if (current -> link[x[i - 1 ] - ' a ' ] == NULL) ... {
current -> link[x[i - 1 ] - ' a ' ] = (trieNode * )malloc( sizeof (trieNode));
(current -> link[x[i - 1 ] - ' a ' ]) -> init();
}
current = current -> link[x[i - 1 ] - ' a ' ];
i ++ ;
}
(current -> num[x[i - 1 ] - ' a ' ]) ++ ;
}
char c[ 50000 ][MaxN],tmp;
int main()
... {
triea;
int i = 0 ,j,num;
while (scanf( " %s " ,c[i]) != EOF)
a.Insert(c[i ++ ]);
num = i;
for (i = 0 ;i < num;i ++ )
for (j = 1 ;c[i][j];j ++ ) ... {
tmp = c[i][j];
c[i][j] = 0 ;
if (a.Search(c[i])) ... {
c[i][j] = tmp;
if (a.Search( & c[i][j])) ... {
printf( " %s " ,c[i]);
break ;}
}
else c[i][j] = tmp;
}
a.Delete(a.root);
return 0 ;
}