posts - 14,  comments - 4,  trackbacks - 0
记得一年前 跑去CSDN问HDU1251(http://acm.hdu.edu.cn/showproblem.php?pid=1251)的写法,飞雪写了个很精简的代码,数组模拟字典树。问题是那个代码只适用于那道题目。
后来有道开了一次网络邀请赛,当时就有那么一道字典树的题,我对着它无解。。今天,我去看了一下字典树,仅仅是靠自己理解了一下字典树的图。

图片地址:http://baike.baidu.com/view/1436495.htm

居然就写出了1251,相比与当年飞雪的代码他的时间是46MS 我今天写的是93MS。可是让我开心的是,我觉得我写的这个扩展性强,我似乎有感觉我能解决当年那题有道邀请赛的题目~~好开心呀~~
当年一个人在寝室一个劲的学习链表~~后来很长一段时间觉得链表似乎没什么用。。。直到上次的线段树,现在的trie树,或者以后的红黑树~B树~?呵呵。如果没有链表的基础我不可能只看图就能写出字典树,基础如此的重要。
贴下代码:
  1/*
  2     3957388 2011-05-15 13:59:22 Accepted 1251 93MS 43768K 1163B C++ test 
  3     so happy learning sth by myself,share this happiness with you ^ ^
  4 */

  5
  6
  7
  8#include <iostream>
  9#include <cstdlib>
 10#include <cstdio>
 11#include <algorithm>
 12#include <cstring>
 13using namespace std;
 14
 15typedef struct tree 
 16{
 17    int num;
 18    struct tree *br[26];
 19}
Node;
 20
 21void insert(char *str,Node *root) // 插入字典
 22{
 23    for(;*str;++str)
 24    {
 25        int id = *str-'a';
 26        if (root->br[id]!=NULL)
 27        {
 28            root->br[id]->num++;
 29        }

 30        else
 31        {
 32            root->br[id] = (Node *)malloc(sizeof(Node));
 33            root->br[id]->num=1;
 34            for (int j=0;j<26;++j)
 35            {
 36                root->br[id]->br[j]=NULL;
 37            }

 38        }

 39        root=root->br[id];
 40    }

 41}

 42
 43
 44int find(char *str,Node *root) // 查找单词数
 45{
 46    for(;*str;++str)
 47    {
 48        int id = *str-'a';
 49        if (root->br[id]==NULL)
 50        {
 51            return 0;
 52        }

 53        else
 54        {
 55            if(*(str+1)==0)
 56            {
 57                return root->br[id]->num;
 58            }

 59            root=root->br[id];
 60        }

 61    }

 62    return 0;
 63}

 64
 65void freeM(Node *root) // 释放内存,其实OJ上不释放不影响结果
 66{
 67    for(int i=0;i<26;++i)
 68    {
 69        if(root->br[i]!=NULL)
 70        {
 71            freeM(root->br[i]);
 72        }

 73    }

 74    free(root);
 75}

 76int main()
 77{
 78    char str[10];
 79    //freopen("data1.in", "r", stdin);
 80    //freopen("data1.out", "w+", stdout);
 81    Node *root=(Node *)malloc(sizeof(Node));;
 82    int i;
 83    for (i=0;i<26;++i)
 84    {
 85        root->br[i]=NULL;
 86    }

 87    while (gets(str))
 88    {
 89        if (str[0]==0)break;
 90        insert(str,root);
 91    }

 92    while (gets(str))
 93    {
 94        printf("%d\n",find(str,root));
 95    }

 96    //fclose(stdout);
 97    //fclose(stdin);
 98    freeM(root);
 99    return 0;
100}

posted on 2011-05-15 14:16 mr_chen 阅读(295) 评论(0)  编辑 收藏 引用 所属分类: 数据结构字典树

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


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿

随笔档案(14)

文章分类(8)

文章档案(11)

搜索

  •  

最新评论

阅读排行榜

评论排行榜