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

隨筆-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>
            欧美精品日韩一区| 亚洲人成毛片在线播放女女| 亚洲欧美国产三级| 国产香蕉97碰碰久久人人| 欧美一级夜夜爽| 欧美专区在线观看一区| 黄网站色欧美视频| 亚洲国产精品成人综合色在线婷婷| 玖玖精品视频| 亚洲午夜高清视频| 亚洲永久在线| 在线日本成人| 99热免费精品| 激情成人av| 亚洲精品国精品久久99热一| 国产精品永久免费| 欧美激情一二区| 国产精品久久77777| 久久综合久久综合久久| 欧美精品一区二区三| 性欧美videos另类喷潮| 免费欧美电影| 午夜亚洲视频| 欧美成人亚洲成人| 欧美在线高清| 欧美日韩情趣电影| 久久婷婷国产综合国色天香| 欧美黄在线观看| 久久精品国产999大香线蕉| 欧美成人激情在线| 久久久91精品国产一区二区三区| 女人色偷偷aa久久天堂| 久久精品一二三区| 欧美日韩免费观看一区二区三区| 久久精品综合| 国产精品伦一区| 欧美激情综合| 国产主播一区二区| 中文国产一区| 亚洲精品在线观看免费| 久久久久国产精品午夜一区| 亚洲综合导航| 欧美另类在线播放| 欧美成人亚洲成人日韩成人| 国产婷婷精品| 亚洲一区二区高清| 一区二区三区视频在线| 免费观看成人网| 久久亚洲电影| 国产亚洲精品福利| 香蕉成人啪国产精品视频综合网| 中文有码久久| 欧美日韩国产限制| 亚洲级视频在线观看免费1级| 影音先锋久久久| 久久成人免费网| 久久精品女人| 国产色婷婷国产综合在线理论片a| 99国产精品久久久| 午夜在线精品偷拍| 国产精品s色| 欧美高清在线视频| 国产一区二区三区久久| 亚洲欧美一区二区精品久久久| 亚洲精品乱码视频| 免费观看成人网| 亚洲国产成人久久综合| 在线日韩日本国产亚洲| 老**午夜毛片一区二区三区| 久久亚洲精品一区二区| 国产一级精品aaaaa看| 西瓜成人精品人成网站| 久久久久一区二区三区四区| 国产日韩欧美综合精品| 久久久999精品免费| 免费不卡在线观看| 亚洲人精品午夜在线观看| 欧美成人在线免费观看| 亚洲人成毛片在线播放女女| 一区二区久久| 国产精品素人视频| 欧美一区二视频| 免费在线观看精品| 一区二区免费在线视频| 国产精品捆绑调教| 久久精品免费看| 欧美大学生性色视频| 一区二区三区四区五区在线| 国产精品国产自产拍高清av王其| 亚洲一区免费| 农夫在线精品视频免费观看| 99国产麻豆精品| 国产欧美日韩一级| 欧美成人a视频| 一区二区三区高清视频在线观看| 欧美一区综合| 91久久精品国产91久久| 国产精品久久久久77777| 久久精品亚洲精品| 亚洲美女在线视频| 久久久噜噜噜久久| 一区二区精品| 激情综合色综合久久| 欧美日韩免费观看一区| 久久精品2019中文字幕| 亚洲人妖在线| 久久午夜羞羞影院免费观看| 99精品免费网| 精品福利免费观看| 国产精品高潮呻吟久久| 久久久久一区二区三区四区| 一本久久青青| 欧美国产视频在线| 久久国产精品久久w女人spa| 日韩亚洲国产欧美| 在线免费观看日本一区| 国产精品久久久一区麻豆最新章节| 久久久久久午夜| 亚洲制服少妇| av成人老司机| 亚洲国产老妈| 欧美国产欧美亚洲国产日韩mv天天看完整 | 日韩小视频在线观看专区| 久久精品一区二区三区不卡牛牛| 日韩亚洲欧美综合| 亚洲大胆人体视频| 国产综合久久| 国产精品一卡二卡| 欧美午夜影院| 欧美美女bb生活片| 欧美sm重口味系列视频在线观看| 久久丁香综合五月国产三级网站| 一区二区三区日韩欧美| 亚洲精品免费观看| 亚洲高清资源| 欧美国产综合视频| 免费久久99精品国产自在现线| 欧美专区18| 久久精品观看| 欧美在线精品免播放器视频| 亚洲免费视频中文字幕| 亚洲一区精品视频| 亚洲主播在线| 亚洲午夜激情网页| 亚洲欧美国产日韩中文字幕| 亚洲视频视频在线| 亚洲在线成人精品| 亚洲欧美卡通另类91av| 亚洲欧美在线一区二区| 午夜日韩在线| 欧美中文字幕第一页| 久久人人97超碰精品888| 久久久欧美精品| 欧美成人精品不卡视频在线观看| 久久伊人亚洲| 欧美国产亚洲视频| 亚洲电影免费| 夜夜嗨av色综合久久久综合网 | 久久九九久久九九| 久久久另类综合| 欧美高清视频在线| 日韩视频中文| 午夜精品婷婷| 久久中文精品| 欧美日韩国产片| 国产精品美女久久久久久2018 | 欧美日韩理论| 国产日韩欧美精品在线| 亚洲第一毛片| 亚洲视频精品在线| 久久国产免费看| 亚洲电影一级黄| 亚洲一二三级电影| 久久久视频精品| 欧美日韩一区二区三区免费| 国产精品综合| 亚洲区中文字幕| 亚洲在线网站| 欧美福利视频在线| 在线视频你懂得一区二区三区| 欧美一级在线播放| 欧美激情免费在线| 国产视频精品网| aⅴ色国产欧美| 久久久久网址| 一区二区三区视频观看| 久久久久成人网| 欧美亚洲第一区| 亚洲第一精品在线| 久久成人免费网| 亚洲三级视频在线观看| 久久国产视频网| 欧美视频在线观看| 亚洲精品欧美日韩| 久久亚洲国产精品日日av夜夜| 亚洲精品在线观| 久久在线视频| 黄色成人av在线| 欧美亚洲一级| 一区二区久久|