青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆-162  評論-223  文章-30  trackbacks-0
類型定義 
   在多叉樹中,深度遍歷迭代器有只讀、讀寫、只讀反轉、讀寫反轉4種,在mtree容器中的定義如下:
1        typedef fd_iterator_impl<false,false> fd_iterator;
2        typedef fd_iterator_impl<false,true> reverse_fd_iterator;
3        typedef fd_iterator_impl<true,false> const_fd_iterator;
4        typedef fd_iterator_impl<true,true> const_reverse_fd_iterator;

接口定義
   多叉樹的深度遍歷是指訪問某子樹某同一深度上的所有結點,下面代碼是深度遍歷迭代器的聲明: 
 1        template<bool is_const,bool is_reverse>
 2        class fd_iterator_impl : public iterator_base_impl<is_const>
 3        {
 4            friend class mtree<T,false>;
 5            typedef iterator_base_impl<is_const> base_type;
 6            typedef typename base_type::node_pointer_type node_pointer_type;
 7            typedef typename base_type::tree_pointer_type tree_pointer_type;
 8            using base_type::tree_;
 9            using base_type::off_;
10            using base_type::root_;
11        public:
12            fd_iterator_impl();
13            fd_iterator_impl(const base_type& iter,size_t depth);
14            fd_iterator_impl&  operator++();            
15            fd_iterator_impl&  operator--();            
16            fd_iterator_impl operator++(int);            
17            fd_iterator_impl operator--(int);            
18            fd_iterator_impl operator + (size_t off);            
19            fd_iterator_impl& operator += (size_t off);            
20            fd_iterator_impl operator - (size_t off);            
21            fd_iterator_impl& operator -= (size_t off);            
22            fd_iterator_impl begin() const;        
23            fd_iterator_impl end() const;            
24        protected:
25            void first(no_reverse_tag);            
26            void first(reverse_tag);            
27            void last(no_reverse_tag);            
28            void last(reverse_tag);            
29            void increment(no_reverse_tag);            
30            void increment(reverse_tag);            
31            void decrement(no_reverse_tag);            
32            void decrement(reverse_tag);            
33        private:
34            void forward_first();            
35            void forward_last();            
36            void forward_next();            
37            void forward_prev();            
38        private:
39            size_t  depth_;
40        }
;

接口實現
  下面重點講述深度遍歷中4種定位方法的具體實現,隨后列出其它所有方法的實現代碼。
   (1)forward_first:求正向第一個結點,步驟如下:a) 向下遍歷第一個孩子,如果存在第一個孩子則深度加1,并繼續該過程直到達到某深度為止,否則轉到步驟b)。b) 向右遍歷兄弟結點,如果存在右兄弟且該右兄弟沒有孩子結點,則繼續該過程直到存在孩子結點為止,這時轉向步驟a),否則轉到步驟c)。c) 向上遍歷父結點,深度減1,直到父結點存在右兄弟或碰到子樹根結點或不存在父結點為止,如果碰到子樹根結點或不存在父結點則返回end,否則轉向步驟b)。代碼如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::forward_first()
 4    {
 5        size_t curdepth = 0; off_ = root_;
 6        node_pointer_type p_node = &(*tree_)[off_];
 7        while(curdepth<depth_)
 8        {
 9            while(!p_node->first_child_)
10            {
11                while (!p_node->next_sibling_)
12                {
13                    if (off_==root_ || !p_node->parent_)  
14                    {
15                        off_ = tree_->size();
16                        return;
17                    }

18                    off_ -= p_node->parent_;
19                    p_node = &(*tree_)[off_];
20                    --curdepth;
21                }

22                off_ += p_node->next_sibling_;
23                p_node = &(*tree_)[off_];
24            }

25            off_ += p_node->first_child_;
26            p_node = &(*tree_)[off_];
27            ++curdepth;
28        }

29    }
   (2)forward_last:求正向最后
個結點,步驟如下:a) 向下遍歷最后一個孩子,如果存在最后一個孩子則深度加1,并繼續該過程直到達到某深度為止,否則轉到步驟b)。b) 向左遍歷兄弟結點,如果存在左兄弟且該左兄弟沒有孩子結點,則繼續該過程直到存在孩子結點為止,這時轉向步驟a),否則轉到步驟c)。c) 向上遍歷父結點,深度減1,直到父結點存在右兄弟或碰到子樹根結點或不存在父結點為止,如果碰到子樹根結點或不存在父結點則返回end,否則轉向步驟b)。代碼如下: 
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::forward_last()
 4    {
 5        size_t curdepth = 0; off_ = root_;
 6        node_pointer_type p_node = &(*tree_)[off_];
 7        while(curdepth<depth_)
 8        {
 9            while(!p_node->last_child_)
10            {
11                while (!p_node->prev_sibling_)
12                {
13                    if (off_==root_ || !p_node->parent_)  
14                    {
15                        off_ = tree_->size();
16                        return;
17                    }

18                    off_ -= p_node->parent_;
19                    p_node = &(*tree_)[off_];
20                    --curdepth;
21                }

22                off_ -= p_node->prev_sibling_;
23                p_node = &(*tree_)[off_];
24            }

25            off_ += p_node->last_child_;
26            p_node = &(*tree_)[off_];
27            ++curdepth;
28        }

29    }
  (3)forward_next:求正向下一個結點,步驟如下:a) 如果當前結點不是子樹根結點且存在右兄弟結點,那么下一個結點就是其右兄弟結點,否則轉到步驟b)。b) 向上遍歷父結點,深度減1,直到存在右兄弟結點或碰到子樹根結點或不存在父結點,如果碰到子樹根結點或不存在父結點,那么返回end,否則轉到步驟c)。c) 向右遍歷其右兄弟直到存在孩子結點為止,如果不存在右兄弟結點,那么轉到步驟b),否則轉到步驟c)。c) 向下遍歷第一個孩子結點,深度加1,直到不存在孩子結點或深度達到為止,如果不存孩子結點,在這種情況下,如果存在右兄弟那么轉到步驟c),否則轉到步驟b)
代碼如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::forward_next()
 4    {
 5        node_pointer_type p_node = &(*tree_)[off_];
 6        if (off_!=root_&&p_node->next_sibling_)
 7        {
 8            off_ += p_node->next_sibling_;
 9        }

10        else
11        {
12            size_t curdepth = depth_;
13        upward:
14            while (off_!=root_&&p_node->parent_&&!p_node->next_sibling_)
15            {
16                off_ -= p_node->parent_;
17                p_node = &(*tree_)[off_];
18                --curdepth;
19            }

20            if (off_==root_||!p_node->parent_)
21            {
22                off_ = tree_->size();
23                return ;
24            }

25        downward:
26            off_ += p_node->next_sibling_; p_node = &(*tree_)[off_];
27            while (!p_node->first_child_)
28            {
29                if (!p_node->next_sibling_)
30                    goto upward;
31                off_ += p_node->next_sibling_;            
32                p_node = &(*tree_)[off_];
33            }

34            while(curdepth<depth_&&p_node->first_child_)
35            {
36                off_ += p_node->first_child_;
37                p_node = &(*tree_)[off_];
38                ++curdepth;
39            }

40            if (curdepth<depth_)
41            {
42                if (p_node->next_sibling_) goto downward;
43                else goto upward;
44            }

45        }

46    }
  (4)forward_prev:求正向前一個結點,步驟如下:a) 如果當前結點不是子樹根結點且存在左兄弟結點,那么下一個結點就是其左兄弟結點,否則轉到步驟b)。b) 向上遍歷父結點,深度減1,直到存在左兄弟結點或碰到子樹根結點或不存在父結點,如果碰到子樹根結點或不存在父結點,那么返回end,否則轉到步驟c)。c) 向左遍歷其左右兄弟直到存在孩子結點為止,如果不存在左兄弟結點,那么轉到步驟b),否則轉到步驟c)。c) 向下遍歷最后一個孩子結點,深度加1,直到不存在孩子結點或深度達到為止,如果不存孩子結點,在這種情況下,如果存在左兄弟那么轉到步驟c),否則轉到步驟b)
代碼如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::forward_prev()
 4    {
 5        node_pointer_type p_node = &(*tree_)[off_];
 6        if (off_!=root_&&p_node->prev_sibling_)
 7        {
 8            off_ -= p_node->prev_sibling_;
 9        }

10        else
11        {
12            size_t curdepth = depth_;
13        upward:
14            while (off_!=root_&&p_node->parent_&&!p_node->prev_sibling_)
15            {
16                off_ -= p_node->parent_;
17                p_node = &(*tree_)[off_];
18                --curdepth;
19            }

20            if (off_==root_||!p_node->parent_)
21            {
22                off_ = tree_->size();
23                return;
24            }

25        downward:
26            off_ -= p_node->prev_sibling_; p_node = &(*tree_)[off_];
27            while (!p_node->last_child_)
28            {
29                if (!p_node->prev_sibling_)
30                    goto upward;
31                off_ -= p_node->prev_sibling_;            
32                p_node = &(*tree_)[off_];
33            }

34            while (curdepth<depth_&&p_node->last_child_)
35            {
36                off_ += p_node->last_child_;
37                p_node = &(*tree_)[off_];
38                ++curdepth;
39            }

40            if (curdepth<depth_)
41            {
42                if (p_node->prev_sibling_) goto downward;
43                else goto upward;
44            }

45        }

46    }
   (5)構造函數的實現,代碼如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::fd_iterator_impl()
 4        :base_type()
 5    {
 6        root_ = 0;
 7    }

 8    template<typename T>
 9    template<bool is_const,bool is_reverse>
10    inline mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::fd_iterator_impl(const base_type& iter,size_t depth)
11        :base_type(iter),depth_(depth)
12    {
13        root_ = off_;
14    }
  (6)公有方法的實現,代碼如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline typename mtree<T,false>::template fd_iterator_impl<is_const,is_reverse>&
 4        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::operator++()
 5    {
 6        increment(typename reverse_trait<is_reverse>::type());
 7        return *this;
 8    }

 9    template<typename T>
10    template<bool is_const,bool is_reverse>
11    inline typename mtree<T,false>::template fd_iterator_impl<is_const,is_reverse>&
12        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::operator--()
13    {
14        decrement(typename reverse_trait<is_reverse>::type());
15        return *this;
16    }

17    template<typename T>
18    template<bool is_const,bool is_reverse>
19    inline typename mtree<T,false>::template fd_iterator_impl<is_const,is_reverse>
20        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::operator++(int)
21    {
22        fd_iterator_impl<is_const,is_reverse> iter(*this);
23        --(*this);
24        return iter;
25    }

26    template<typename T> 
27    template<bool is_const,bool is_reverse>
28    inline typename mtree<T,false>::template fd_iterator_impl<is_const,is_reverse>
29        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::operator--(int)
30    {
31        fd_iterator_impl<is_const,is_reverse> iter(*this);
32        --(*this);
33        return iter;
34    }

35    template<typename T> 
36    template<bool is_const,bool is_reverse>
37    inline typename mtree<T,false>::template fd_iterator_impl<is_const,is_reverse>
38        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::operator + (size_t off)
39    {
40        fd_iterator_impl<is_const,is_reverse> iter(*this);
41        iter += off;
42        return iter;
43    }

44    template<typename T> 
45    template<bool is_const,bool is_reverse>
46    inline typename mtree<T,false>::template fd_iterator_impl<is_const,is_reverse>&
47        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::operator += (size_t off)
48    {
49        while (off)
50        {
51            if (base_type::is_null()) break;
52            ++(*this); --off;
53        }

54        return *this;
55    }

56    template<typename T> 
57    template<bool is_const,bool is_reverse>
58    inline typename mtree<T,false>::template fd_iterator_impl<is_const,is_reverse>
59        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::operator - (size_t off)
60    {
61        fd_iterator_impl<is_const,is_reverse> iter(*this);
62        iter -= off;
63        return iter;
64    }

65    template<typename T> 
66    template<bool is_const,bool is_reverse>
67    inline typename mtree<T,false>::template fd_iterator_impl<is_const,is_reverse>&
68        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::operator -= (size_t off)
69    {
70        while (off)
71        {
72            if (base_type::is_null()) break;
73            --(*this); --off;
74        }

75        return *this;
76    }

77    template<typename T>
78    template<bool is_const,bool is_reverse>
79    inline typename mtree<T,false>::template fd_iterator_impl<is_const,is_reverse>
80        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::begin() const
81    {
82        fd_iterator_impl<is_const,is_reverse> iter(*this);
83        iter.first(typename reverse_trait<is_reverse>::type());
84        return iter;
85    }

86    template<typename T>
87    template<bool is_const,bool is_reverse>
88    inline typename mtree<T,false>::template fd_iterator_impl<is_const,is_reverse> 
89        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::end() const
90    {
91        fd_iterator_impl<is_const,is_reverse> iter(*this);
92        if (tree_)
93        {
94            iter.off_ = tree_->size();
95        }

96        return iter;
97    }

使用示例
   (1)正向遍歷某子樹某深度上的所有結點,代碼如下:
1    mtree<int,false>::iterator_base root; size_t depth;
2    mtree<int,false>::fd_iterator it(root,depth);
3    mtree<int,false>::fd_iterator last = --it.end();
4    for (it = it.begin();it!=it.end();++it)
5    {
6        cout << *it;
7        if (it!=last)
8            cout <<" ";
9    }
  (2)反
向遍歷某子樹某深度上的所有結點,代碼如下:
1    mtree<int,false>::iterator_base root; size_t depth;
2    mtree<int,false>::reverse_fd_iterator r_it(root,depth);
3    mtree<int,false>::reverse_fd_iterator r_last = --r_it.end();
4    for (r_it = r_it.begin();r_it!=r_it.end();++r_it)
5    {
6        cout << *r_it;
7        if (r_it!=r_last)
8            cout <<" ";
9    }
posted on 2011-10-03 17:52 春秋十二月 閱讀(3174) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲精品欧美在线| 136国产福利精品导航| 亚洲无限乱码一二三四麻| 亚洲高清网站| 欧美福利电影在线观看| 夜夜嗨av一区二区三区中文字幕| 亚洲国产精品成人精品| 欧美日韩视频一区二区| 亚洲免费视频在线观看| 久久国产欧美日韩精品| 亚洲高清视频在线| 一本久久青青| 国产亚洲欧美日韩一区二区| 免费视频亚洲| 欧美激情久久久久| 亚洲欧美日韩视频二区| 久久久久欧美| 这里只有精品视频| 欧美一区二区三区四区在线观看地址| 韩国福利一区| 亚洲乱码精品一二三四区日韩在线 | 国产综合欧美在线看| 欧美国产综合一区二区| 欧美亚洲成人免费| 麻豆精品一区二区综合av| 欧美日韩色综合| 免费久久99精品国产| 欧美日韩一区在线播放| 久久只有精品| 国产精品播放| 欧美国产日韩一区二区三区| 国产精品久久久久久久久免费桃花 | 久久精品一区二区| 欧美日韩亚洲综合在线| 久久亚洲精品一区| 国产精品久久久久aaaa| 亚洲福利视频网| 国产午夜久久久久| 宅男精品导航| 亚洲人成7777| 久久久久久久成人| 欧美一区二区三区成人| 欧美日韩高清在线观看| 免费成人av| 黄色成人免费网站| 亚洲欧美日韩成人高清在线一区| 一区二区免费在线视频| 久久综合五月| 美女精品视频一区| 国产午夜精品视频免费不卡69堂| 99在线热播精品免费| 亚洲精品小视频| 久久午夜av| 开元免费观看欧美电视剧网站| 国产精品亚洲不卡a| 99re热精品| 亚洲一级免费视频| 欧美日韩在线视频一区| 亚洲精品视频免费观看| 亚洲精品国偷自产在线99热| 免费观看成人网| 欧美激情按摩在线| 亚洲精品久久久久久久久久久久久 | 国产精品美女主播在线观看纯欲| 欧美激情视频给我| 亚洲片在线观看| 牛牛影视久久网| 亚洲电影免费观看高清完整版在线| 一区二区三区在线免费播放| 久久九九国产| 美女尤物久久精品| 亚洲欧洲一级| 欧美日韩八区| 99在线热播精品免费| 亚洲欧美日韩国产一区二区三区| 国产精品久久久久国产a级| 亚洲五月六月| 久久久久青草大香线综合精品| 国内精品久久久久久久影视蜜臀| 久久久久久黄| 最新国产成人av网站网址麻豆| 一本在线高清不卡dvd| 国产精品成人一区二区三区夜夜夜| 中文在线不卡| 久热精品视频在线观看| 亚洲理论在线观看| 国产精品乱看| 久久久最新网址| 亚洲毛片在线看| 欧美影院一区| 亚洲欧洲在线看| 国产精品高清网站| 久久精品毛片| 一本一道久久综合狠狠老精东影业 | 性欧美精品高清| 米奇777在线欧美播放| 一区二区三区国产盗摄| 国产欧美日韩高清| 欧美高清视频www夜色资源网| 99在线|亚洲一区二区| 麻豆精品视频在线观看| 亚洲美女淫视频| 国产主播喷水一区二区| 欧美激情第4页| 欧美在线视频全部完| 亚洲激情亚洲| 久久久亚洲高清| 亚洲一区一卡| 91久久久一线二线三线品牌| 国产欧美在线看| 欧美伦理91i| 久久久亚洲国产美女国产盗摄| 亚洲精品一区二区在线| 麻豆精品精品国产自在97香蕉| 亚洲免费中文字幕| 亚洲精品一区二区三区福利| 国产字幕视频一区二区| 欧美三级精品| 欧美国产一区在线| 久久久国产91| 午夜久久久久久久久久一区二区| 亚洲精品一区在线| 亚洲国产免费| 免费看精品久久片| 久久久人成影片一区二区三区观看 | 欧美 日韩 国产精品免费观看| 亚洲欧美在线免费观看| 日韩视频在线免费| 亚洲欧洲一二三| 在线观看日韩欧美| 国内自拍一区| 国产片一区二区| 国产精品免费小视频| 欧美午夜精品电影| 欧美日韩视频在线一区二区| 欧美高清自拍一区| 欧美大学生性色视频| 蜜臀久久99精品久久久久久9| 久久久久国产一区二区三区| 亚洲欧美国产另类| 午夜一区二区三区在线观看| 亚洲午夜精品一区二区| 亚洲一区国产精品| 亚洲免费人成在线视频观看| 亚洲网站啪啪| 午夜精品国产精品大乳美女| 校园春色综合网| 久久不射中文字幕| 久久久精品网| 老司机午夜精品视频| 久久字幕精品一区| 欧美激情久久久| 欧美日韩免费观看一区| 国产精品久久国产愉拍 | 欧美日韩999| 欧美午夜精品理论片a级大开眼界| 欧美日韩综合一区| 国产精品一区在线观看你懂的| 国产精品自拍网站| 国产精品一区二区三区观看| 国产精品日韩精品欧美在线 | 欧美日韩精品一本二本三本| 欧美日韩亚洲网| 国产精品午夜在线| 亚洲第一区在线观看| 一区二区三区欧美在线观看| 亚洲欧美激情四射在线日| 亚洲欧美日韩精品| 麻豆av福利av久久av| 亚洲精品国产品国语在线app| 99国产精品国产精品久久 | 欧美激情区在线播放| 一本久道久久综合婷婷鲸鱼| 亚洲欧美日韩区| 麻豆成人在线播放| 国产精品日韩欧美一区| 亚洲国产电影| 亚洲欧美国产视频| 免费不卡视频| 亚洲一区国产| 欧美a一区二区| 国产色视频一区| 99国产精品久久久| 久久久午夜电影| 一本一本a久久| 免费中文日韩| 国产欧美一区二区视频| 亚洲国产91| 亚洲欧美日韩在线观看a三区| 欧美成人dvd在线视频| 亚洲视频精品| 欧美国产一区视频在线观看| 国产欧美在线观看| 亚洲一区视频| 亚洲欧洲精品一区二区三区不卡 | 亚洲美女免费精品视频在线观看| 欧美在线在线| 国产精品视频99| 亚洲视频axxx| 亚洲福利在线看|