好不容易寫的一個(gè)模版~本來(lái)是想按照我們數(shù)據(jù)結(jié)構(gòu)教程的trie樹來(lái)寫，但是他的實(shí)現(xiàn)我實(shí)在覺得太難
所以還是采用簡(jiǎn)化版的trie樹
這個(gè)應(yīng)該算是比較標(biāo)準(zhǔn)的trie樹結(jié)構(gòu)，但是他的插入實(shí)現(xiàn)起來(lái)不僅僅是插入本身的單詞，可能還需要修改原來(lái)的數(shù)結(jié)構(gòu)
比如說本身已經(jīng)存在了bobwhite，現(xiàn)在添加bobwhq，就要在第二層的基礎(chǔ)上繼續(xù)擴(kuò)展，bobwhite的位置也要重新定位，刪除操作也是這樣
可能還要上移某些單詞，這個(gè)昨天試了很久，寫出來(lái)的都不行。
而且對(duì)這種字典樹的結(jié)構(gòu)本身我的理解就很混亂。
簡(jiǎn)化版的trie樹
以下這種實(shí)現(xiàn)方法是根據(jù)別人改編的，昨天被逼得沒辦法還是覺得簡(jiǎn)化版的，突然發(fā)現(xiàn)個(gè)牛人的寫法和我的很相似（這著實(shí)還讓我激動(dòng)了下下），就邊學(xué)習(xí)邊改了，呵呵
它是根據(jù)杭電的一道題來(lái)寫的，以下是我的代碼：
http://acm.hdu.edu.cn/showproblem.php?pid=1247
#include<iostream>
#define keyNum 26
#define MaxN 50
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&¤t->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()
{
trie a;
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\n",c[i]);
break;}
}
else c[i][j]=tmp;
}
a.Delete(a.root);
return 0;
}
這個(gè)模版還不是很完善~用起來(lái)還是不大方便，比如刪除節(jié)點(diǎn)，我的刪除只是寫了刪所有的，用遞歸寫的。
還有遍歷節(jié)點(diǎn)，都不是很方便的。
以上代碼解釋幾點(diǎn)：
首先我構(gòu)造了一格trie的結(jié)構(gòu)：在此結(jié)構(gòu)中有root，和這棵樹的基本三個(gè)操作
再次trie結(jié)構(gòu)中的每個(gè)節(jié)點(diǎn)都是trieNode的結(jié)構(gòu)，包括root也是
這棵樹是動(dòng)態(tài)生成的，所以對(duì)trieNode的init很重要，這點(diǎn)寫過的就知道，不Init會(huì)出現(xiàn)很多問題的,
在trieNode結(jié)構(gòu)中主要有26個(gè)link和26個(gè)num，剛開始我自己寫的時(shí)候就是這26個(gè)num搞不清，只寫了一個(gè)num，這是對(duì)樹結(jié)構(gòu)的理解混亂造成的
num在這里是標(biāo)記這個(gè)單詞插入的次數(shù)，為0表示這個(gè)單詞還沒有被插入過
trieNode還有個(gè)很重要的成員函數(shù)就是init了。
posted on 2008-04-06 13:09
zoyi 閱讀(3181)
評(píng)論(3) 編輯 收藏 引用 所屬分類:
數(shù)據(jù)結(jié)構(gòu)