• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 14,  comments - 4,  trackbacks - 0
            記得一年前 跑去CSDN問HDU1251(http://acm.hdu.edu.cn/showproblem.php?pid=1251)的寫法,飛雪寫了個很精簡的代碼,數(shù)組模擬字典樹。問題是那個代碼只適用于那道題目。
            后來有道開了一次網(wǎng)絡(luò)邀請賽,當(dāng)時就有那么一道字典樹的題,我對著它無解。。今天,我去看了一下字典樹,僅僅是靠自己理解了一下字典樹的圖。

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

            居然就寫出了1251,相比與當(dāng)年飛雪的代碼他的時間是46MS 我今天寫的是93MS。可是讓我開心的是,我覺得我寫的這個擴(kuò)展性強(qiáng),我似乎有感覺我能解決當(dāng)年那題有道邀請賽的題目~~好開心呀~~
            當(dāng)年一個人在寢室一個勁的學(xué)習(xí)鏈表~~后來很長一段時間覺得鏈表似乎沒什么用。。。直到上次的線段樹,現(xiàn)在的trie樹,或者以后的紅黑樹~B樹~?呵呵。如果沒有鏈表的基礎(chǔ)我不可能只看圖就能寫出字典樹,基礎(chǔ)如此的重要。
            貼下代碼:
              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) // 查找單詞數(shù)
             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) // 釋放內(nèi)存,其實OJ上不釋放不影響結(jié)果
             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 閱讀(323) 評論(0)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)字典樹

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            <2012年7月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿

            隨筆檔案(14)

            文章分類(8)

            文章檔案(11)

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久99国产精品久久99| 久久久久无码中| 91精品日韩人妻无码久久不卡| 国内精品久久久久久久久| 无码人妻久久一区二区三区蜜桃 | 亚洲欧美成人久久综合中文网| 最新久久免费视频| 69国产成人综合久久精品| 久久性生大片免费观看性| 久久精品国产99久久无毒不卡 | 亚洲成色www久久网站夜月| 99久久www免费人成精品| 亚洲精品乱码久久久久久| 久久精品国产99久久丝袜| 99国产欧美精品久久久蜜芽| 国产精品久久久久久久久久影院| 亚洲国产成人久久精品动漫| 日韩人妻无码精品久久免费一| 久久久WWW成人| 国产成人久久久精品二区三区| 久久国产色AV免费看| 久久午夜夜伦鲁鲁片免费无码影视| 大美女久久久久久j久久| www.久久99| 国产精品久久久久久久| 狠狠综合久久综合88亚洲 | 国产午夜精品理论片久久影视| 精品久久久久久久久免费影院| 久久无码人妻精品一区二区三区 | 99精品久久精品一区二区| 欧美精品丝袜久久久中文字幕 | 91久久精品电影| 色噜噜狠狠先锋影音久久| 久久精品国产亚洲av日韩| 久久亚洲中文字幕精品有坂深雪| 亚洲AV无码久久精品色欲| 中文字幕日本人妻久久久免费| 亚洲精品午夜国产va久久| 日韩人妻无码一区二区三区久久99| 亚洲伊人久久成综合人影院| 日本精品一区二区久久久|