• <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)

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲va久久久噜噜噜久久狠狠| 久久99国产精品二区不卡| 久久99精品九九九久久婷婷| 久久这里只有精品视频99| 亚洲国产天堂久久综合| 久久亚洲精精品中文字幕| 中文字幕成人精品久久不卡| 亚洲综合久久久| 国产精品久久永久免费| 午夜福利91久久福利| 国产精品久久99| 模特私拍国产精品久久| 大美女久久久久久j久久| 99精品久久久久久久婷婷 | 久久99精品久久久大学生| 久久久久亚洲AV无码专区体验| 久久国产香蕉视频| 国产精品九九九久久九九| 亚洲国产精品高清久久久| 久久精品中文字幕有码| 国产精品久久久久9999高清| 伊人久久大香线蕉av不卡| 欧美性大战久久久久久| 97精品伊人久久久大香线蕉| 91精品国产综合久久久久久| 人妻久久久一区二区三区| 亚洲国产精品无码久久久久久曰| 品成人欧美大片久久国产欧美| 欧美va久久久噜噜噜久久| 99久久精品国产一区二区| 亚洲精品乱码久久久久久中文字幕 | 日产精品久久久一区二区| 热久久视久久精品18| 久久精品国产福利国产琪琪| 国产欧美久久久精品| 精品国产一区二区三区久久| 9久久9久久精品| 99久久国产综合精品网成人影院 | 久久一区二区三区免费| 狠狠人妻久久久久久综合蜜桃| 精品久久久久久久中文字幕 |