Reiks的技術博客

C/C++/STL/Algorithm/D3D

posts - 17, comments - 2, trackbacks - 0, articles - 0

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理

Trie樹

Posted on 2009-08-28 10:32 reiks 閱讀(1040) 評論(0) 編輯收藏引用所屬分類: 算法與數據結構

Name: Trie樹的基本實現

Author: MaiK

Description: Trie樹的基本實現 ,包括查找插入和刪除操作(衛星數據可以因情況而異)

#include<algorithm>

#include<iostream>

using namespace std;

const int sonnum=26,base='a';

struct Trie

{

int num; //to remember how many word can reach here,that is to say,prefix

bool terminal; //If terminal==true ,the current point has no following point

struct Trie *son[sonnum]; //the following point

};

Trie *NewTrie()// create a new node

{

Trie *temp=new Trie;

temp->num=1;

temp->terminal=false;

for (int i=0; i<sonnum; ++i)

temp->son[i] = NULL;

return temp;

}

void Insert(Trie *pnt,char *s,int len)// insert a new word to Trie tree

{

Trie *temp=pnt;

for (int i=0;i<len;++i)

{

if (temp->son[s[i]-base]==NULL)

temp->son[s[i]-base]=NewTrie();

else

temp->son[s[i]-base]->num++;

temp=temp->son[s[i]-base];

}

temp->terminal=true;

}

void Delete(Trie *pnt) // delete the whole tree

{

if (pnt!=NULL)

{

for (int i=0;i<sonnum;++i)

if (pnt->son[i]!=NULL)

Delete(pnt->son[i]);

delete pnt;

pnt=NULL;

}

Trie* Find(Trie *pnt,char *s,int len) //trie to find the current word

{

Trie *temp=pnt;

for (int i=0;i<len;++i)

if (temp->son[s[i]-base]!=NULL)

temp=temp->son[s[i]-base];

else return NULL;

return temp;

}

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 最大流 Edmonds-Karp 樹狀數組匈牙利算法并查集 Topsort Trie樹大整數乘除小整數 RMQ問題ST算法 MST-Kruskal 組合數

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

Reiks的技術博客

Trie樹

日歷

常用鏈接

留言簿

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜