Reiks的技术博客
C/C++/STL/Algorithm/D3D
posts - 17, comments - 2, trackbacks - 0, articles - 0
C++博客
::
首页
::
新随笔
::
联系
::
聚合
::
管理
Trie树
Posted on 2009-08-28 10:32
reiks
阅读(970)
评论(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
知识库
博问
管理
Powered by:
C++博客
Copyright © reiks
日历
<
2013年12月
>
日
一
二
三
四
五
六
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔分类
Direct3D(1)
算法与数据结构(15)
心情随笔(1)
随笔档案
2011年5月 (2)
2009年8月 (15)
搜索
最新评论
1. re: 如何在Direct3D里面使用GDI
为什么我用IDirect3DSurface9的GetDC接口得到dc,然后画矩形框显示不出来?
获取dc是成功的
--herman
2. re: 如何在Direct3D里面使用GDI
很想知道,为什么要在D3D里使用GDI?
--K.V
阅读排行榜
1. RMQ问题ST算法(3497)
2. 如何在Direct3D里面使用GDI(1538)
3. Trie树(970)
4. 最大流 Edmonds-Karp(685)
5. 匈牙利算法(572)
6. Topsort(511)
7. MST-PRIM(483)
8. 并查集(416)
9. 大整数乘除小整数(405)
10. 树状数组(329)
评论排行榜
1. 如何在Direct3D里面使用GDI(2)
2. 新的开始(0)
3. 最大流 Edmonds-Karp(0)
4. 树状数组(0)
5. 匈牙利算法(0)
6. 并查集(0)
7. Topsort(0)
8. Trie树(0)
9. 大整数乘除小整数(0)
10. RMQ问题ST算法(0)