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

            C小加

            厚德 博學 求真 至善 The bright moon and breeze
            posts - 145, comments - 195, trackbacks - 0, articles - 0
              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理
            以前學數據結構的時候吧字典樹忽視了,導致到現在才學到。
            字典樹是一種樹形的數據結構,插入的復雜度為單詞的平均長度。本題只需要寫一個插入函數就可以了。
            由于過幾天就要省賽了,等到省賽后總結一下字典樹。

            // trietree.cpp : 定義控制臺應用程序的入口點。
            //
            #include<cstdio>
            #include<iostream>
            #include<string.h>

            using namespace std;
            const int num_chars = 26;            //關鍵碼最大位

            int _max;
            char ans[12];

            class Trie
            {
            public:
                Trie();
                Trie(Trie& tr);
                virtual ~Trie();
                //int trie_search(const char* word, char*entry) const;
                bool insert(const char* word);
            protected:
                struct Trie_node   //關鍵碼類型
                {
                    bool isfin;
                    int cnt;                     //關鍵碼當前位數
                    Trie_node* branch[num_chars];   //關鍵碼存放數組
                    Trie_node();
                };
                Trie_node* root;
            };

            Trie::Trie_node::Trie_node()   //結點定義
            {
                isfin = false;
                cnt = 0;
                for(int i = 0; i < num_chars;++i)
                    branch[i] = NULL;
            }

            Trie::Trie():root(NULL)
            {
            }

            Trie::~Trie()
            {
            }



            bool Trie::insert(const char*word)
            {
                int result = 1,position = 0;
                if(root == NULL)
                    root = new Trie_node;
                char char_code;
                Trie_node *location = root;
                while(location != NULL && *word != 0)
                {
                    if(*word >= 'a'&& *word <= 'z')
                        char_code = *word - 'a';
                    if(location->branch[char_code] == NULL)
                        location->branch[char_code] = new Trie_node;
                    location = location->branch[char_code];
                    position++;
                    word++;
                }

                ++location->cnt;
                if(location->cnt>_max)
                {
                    _max=location->cnt;
                    return true;
                }
                else
                return false;
            }


            int main()
            {
                Trie t;
                int n;
                while(scanf("%d",&n)!=EOF)
                {
                    _max=0;
                    char s[12];
                    for(int i=0;i<n;++i)
                    {
                        scanf("%s",s);
                        if(t.insert(s))
                        {
                            strcpy(ans,s);
                        }

                    }
                    printf("%s %d\n",ans,_max);
                }


                return 0;
            }
            麻豆精品久久精品色综合| 久久黄视频| 久久精品国产清高在天天线| 亚洲精品无码久久久影院相关影片 | 久久久久久精品免费免费自慰| 久久无码高潮喷水| 91精品国产91久久久久久| 久久AV高潮AV无码AV| 91久久精品国产成人久久| 一本一本久久aa综合精品| 国产亚洲成人久久| 国产精品美女久久久久网| 欧美久久久久久| 国产精品综合久久第一页| 久久这里只有精品18| 一本久久免费视频| 国产99久久久国产精免费| 久久国产精品无码HDAV| 久久久午夜精品| 欧美久久综合九色综合| 国产福利电影一区二区三区,免费久久久久久久精 | 午夜精品久久久久成人| 亚洲欧美精品伊人久久| 精品国际久久久久999波多野| 中文字幕久久亚洲一区| 久久天天躁狠狠躁夜夜不卡 | 久久免费视频一区| 久久精品视屏| 欧美与黑人午夜性猛交久久久| 久久青青草原综合伊人| 91精品国产91久久久久久| 日韩欧美亚洲综合久久影院d3| 久久精品国产免费| 亚洲一区中文字幕久久| 国产精品久久久天天影视香蕉| 日韩欧美亚洲综合久久影院d3| 久久精品国产69国产精品亚洲| 久久96国产精品久久久| 日韩欧美亚洲综合久久影院d3| 狠狠色伊人久久精品综合网| 精品国产婷婷久久久|