好不容易寫的一個(gè)模版~本來是想按照我們數(shù)據(jù)結(jié)構(gòu)教程的trie樹來寫，但是他的實(shí)現(xiàn)我實(shí)在覺得太難
所以還是采用簡(jiǎn)化版的trie樹

這個(gè)應(yīng)該算是比較標(biāo)準(zhǔn)的trie樹結(jié)構(gòu)，但是他的插入實(shí)現(xiàn)起來不僅僅是插入本身的單詞，可能還需要修改原來的數(shù)結(jié)構(gòu)
比如說本身已經(jīng)存在了bobwhite，現(xiàn)在添加bobwhq，就要在第二層的基礎(chǔ)上繼續(xù)擴(kuò)展，bobwhite的位置也要重新定位，刪除操作也是這樣
可能還要上移某些單詞，這個(gè)昨天試了很久，寫出來的都不行。
而且對(duì)這種字典樹的結(jié)構(gòu)本身我的理解就很混亂。
簡(jiǎn)化版的trie樹

以下這種實(shí)現(xiàn)方法是根據(jù)別人改編的，昨天被逼得沒辦法還是覺得簡(jiǎn)化版的，突然發(fā)現(xiàn)個(gè)牛人的寫法和我的很相似（這著實(shí)還讓我激動(dòng)了下下），就邊學(xué)習(xí)邊改了，呵呵
它是根據(jù)杭電的一道題來寫的，以下是我的代碼：
http://acm.hdu.edu.cn/showproblem.php?pid=1247
#include < iostream >
#define keyNum26
#define MaxN50
struct trie ... {
struct trieNode ... { // trie結(jié)點(diǎn)的結(jié)構(gòu)
trieNode * link[keyNum]; // 下標(biāo)為'A','B','C',,'Z'的指針數(shù)組
int num[keyNum]; // 插入key的次數(shù)
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)); // 初始化時(shí)為root申請(qǐng)了空間
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 ;
}