单链DNA

换了个地址：http://www.cnblogs.com/vizhen/

 

【数据结构】字典树

 
字典树概念   Trie，又称单词查找树，是一种树形结构，是哈希树的变种。
   典型应用：于统计和排序大量的字符串（但不仅限于字符串），所以经常用于搜索引擎系统用于文本词频的统计。
   优点：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

字典树性质1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每一个节点所包含的字符都不相同。

图片示例
单词：abcd，bcd，efg，hii构建的字典树示例

结构体定义
 const int KIND=26;//26个小写字母
 struct Trie
 {
     int count;//统计该字母出现次数
     Trie *next[KIND];//子节点
     Trie()
     {
        count=0;
        for(int i=0;i<KIND;i++)
            next[i]=NULL;
     }
 }

操作函数
void InsertNode(TreeNode *&root,char *word)//向root根节点插入字符串word
{
    TreeNode *location=root;
    int i=0,branch=0;

    if (location==NULL)
    {
        location=new TreeNode();
        root=location;
    }

    while(word[i])
    {
        branch=word[i]-'a';
        
        if (location->next[branch])
        {
            location->next[branch]->count++;
            //如果该字符存在，串数量加1
        } 
        else
        {
            //不存在 则建立新节点
            location->next[branch]=new TreeNode();
        }
        i++;
        location=location->next[branch];
    }
}


//查找  与插入类似
int SeacrhWord(TreeNode *root,char *word)
{
    TreeNode *location=root;
    int i=0,branch=0;
    int ans;

    if (location==NULL)
    {
        return 0;
    }

    while(word[i])
    {
        branch=word[i]-'a';
        if (!location->next[branch]) return 0;
        i++;
        location=location->next[branch];
        ans=location->count;
    }
    return ans;
}


posted on 2010-10-24 18:13 Geek.tan 阅读(767) 评论(0)  编辑 收藏 引用 所属分类: 算法学习


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

公告

coding是我的寂寞，我是谁的寂寞

随笔分类(40)

随笔档案(48)

搜索

积分与排名

最新评论

评论排行榜