随笔-88  评论-224  文章-22  trackbacks-0
需求分析
   在数据结构中,树有两种存储方式,一种是链式存储,另一种是顺序存储。前者就是使用指针来记录树结点间的关系,在新增结点或删除结点时,只需改变与父结点或兄弟结点的指针值即可,实现较为简单;后者就是使用数组来存储,可以用相对偏移量来记录树结点间的关系,在新增结点或删除结点时,则不仅是改变与父结点或兄弟结点的相对偏移量,还需要改变其它结点的相对偏移量,实现较为复杂。近来在项目中,对一个普通文本文件进行分析提取数据,而这个文件内的数据从内容看,具有层次嵌套关系,要将这样的数据发送到服务器去处理,我考虑了两种如下方法:
 (1)自定义XML格式,在本地使用XML库,如libxml2、tinyxml等,将数据写到XML临时文件或内存中,再将这个XML临时文件或内存发过去,在服务器那边使用XML库来解析。这种方法比较通用而且跨平台,如果XML库不支持将其所存储的数据转储到一块连续内存,那么就只能先存到XML临时文件,再将这个文件发过去,这样一来,就存在磁盘IO操作,效率较低。否则,就可以先将数据转储到一块连续内存,再将这块内存发过去,这样一来,这块连续内存就需要另外开辟,因此多了一套内存管理操作,但是比用临时文件方式,没有磁盘IO,效率要高些。
 (2)实现基于顺序存储的树,而且还是多叉树,因为实际数据具有多层次嵌套关系,将数据放进这颗树中,再直接将这颗树发过去,在服务器那边直接解析这颗树,这样一来,不用临时文件,没有磁盘IO,无须另外开辟内存,充分利有现有空间,效率较高。

设计开发
   从服务器效率至上的观点考虑,我选择了第2种方法,并实现了基于顺序存储的多叉树,关于顺序存储,又有两种如下方式:
  (1)深度优先存储,按照自上而下从左到右存储树的所有结点,先存储结点及它的孩子,再存储它的兄弟。因此结点的孩子和兄弟都不一定是连续的,当一个结点的所有孩子都是叶子结点时,则所有孩子是连续存放的。结点和它的第一个孩子(若有)是连续的,如下图所示                            
                      
 
  (2)广度优先存储,
按照从左到右自上而下存储树的所有结点,先存储结点及它的兄弟,再存储它的孩子,因此结点的孩子和兄弟都是连续存放的,孩子与其父亲之间不一定是连续的,如下图所示 
                      

   本文描述第1种存储方式实现的多叉树,介绍三种主要操作:设置根结点、增加结点和删除结点,为简单起见,使用vector作为内部动态数组,使用索引而非迭代器作为外部接口,来访问结点,索引0表示空索引,有效索引从1开始。关于迭代器的设计,有诸多考虑,如前序、后序、广度优先、指定深度、叶子结点等各种遍历方法,因时间和篇幅原因,不能一一讲述,待后面有时间会陆续补充完善。
   1)树结点定义,由5个偏移量域和1个数据域组成,C++代码描述如下    
 1template<typename T>
 2struct order_tree_node
 3{
 4    size_t parent_;      
 5    size_t first_child_;  
 6    size_t last_child_;  
 7    size_t prev_sibling_; 
 8    size_t next_sibling_; 
 9    T      data_;         
10
11    order_tree_node();        
12    order_tree_node(const T& data);    
13}
;
  为了方便,定义了order_tree_node的两个构造函数,其实现如下
 1    template<typename T>
 2    order_tree_node<T>::order_tree_node()
 3        :parent_(0)
 4        ,first_child_(0)
 5        ,last_child_(0)
 6        ,prev_sibling_(0)
 7        ,next_sibling_(0)
 8    {
 9    }

10    template<typename T>
11    order_tree_node<T>::order_tree_node(const T& data)
12        :parent_(0)
13        ,first_child_(0)
14        ,last_child_(0)
15        ,prev_sibling_(0)
16        ,next_sibling_(0)
17        ,data_(data)
18    {
19    }
   2)设置根结点,为方便实现,根结点固定存放在数组中第1个位置,对应下标为0,C++代码描述如下  
 1    template<typename T>
 2    inline typename mtree<T,false>::iterator_base mtree<T,false>::set_root(const T& val)
 3    {
 4        if (!base_type::empty())
 5        {
 6            *(get_root()) = val;
 7        }

 8        else
 9        {
10            tree_node node(val);
11            push_back(node);
12        }

13        return iterator_base(this,0);
14    }
   这里用到了get_root函数来获取根结点,其实现如下
 1    template<typename T>
 2    inline typename mtree<T,false>::iterator_base mtree<T,false>::get_root() 
 3    {
 4        return iterator_base(this,0);
 5    }

 6    template<typename T>
 7    inline typename mtree<T,false>::const_iterator_base mtree<T,false>::get_root() const
 8    {
 9        return const_iterator_base(this,0);
10    }
   3)增加结点,这里要分为三步,第一步要找到插入位置,第二步插入结点,第三步改变相关结点的相对偏移量,这里相关结点包括当前所插结点、所插结点兄弟结点、父结点、祖先结点及其右兄弟结点;注意,这里可以作一些异常安全考虑,即如果第二步操作失败了,则可直接返回,这样就可保证整颗树不受影响。为了简单起见,以下C++代码对异常安全没有作处理,描述如下
 1    template<typename T>
 2    template<typename tree_iterator>
 3    inline tree_iterator mtree<T,false>::append_child(tree_iterator iter,const T& val)
 4    {
 5        assert(!iter.is_null());
 6        size_t off = append_child(iter.off_,val);    
 7        tree_iterator it(iter);
 8        it.off_ = off;
 9        return it;
10    }

11    template<typename T>
12    inline typename mtree<T,false>::fd_iterator mtree<T,false>::append_child(fd_iterator iter,const T& val)
13    {
14        assert(!iter.is_null());
15        size_t off = append_child(iter.off_,val);    
16        fd_iterator it(iter);
17        it.off_ = off; ++it.depth_;
18        return it;
19    }
   以上模板成员函数及其深度迭代器的特化版本都调用了内部append_child(size_t)函数,该函数实现如下:
 1    template<typename T>
 2    inline size_t mtree<T,false>::append_child(size_t index,const T& val)
 3    {
 4        size_t parent = index, pos;
 5        tree_node *p_parent = &(*this)[parent],*p_node, *p_child;
 6
 7        //找到插入位置
 8        pos = parent; p_node = p_parent;
 9        while (p_node->last_child_)
10        {
11            pos += p_node->last_child_;
12            p_node = &(*this)[pos];
13        }

14        size_t child = ++pos; 
15        //插入结点
16        tree_node node(val);
17        if (child >= this->size())
18            push_back(node);
19        else
20            base_type::insert(begin()+child,node);
21
22        //更新当前结点的prev_sibling值和其左兄弟结点的next_sibling值
23        p_parent = &(*this)[parent];
24        p_child = &(*this)[child]; 
25        if (p_parent->last_child_)
26        {
27            pos = parent+p_parent->last_child_;
28            (*this)[pos].next_sibling_ = p_child->prev_sibling_ = child-pos;
29        }

30        //从父结点开始,向上更新当前结点所有右边结点的偏移量
31        size_t next; 
32        tree_node* p_next;
33        pos = parent;
34        do 
35        {
36            p_node = &(*this)[pos];
37            if (p_node->next_sibling_)
38            {
39                if (p_node->parent_)
40                    ++(*this)[pos-p_node->parent_].last_child_;
41                //更新其祖先结点的next_sibling值
42                ++p_node->next_sibling_;
43                next = pos + p_node->next_sibling_;
44                p_next = &(*this)[next];
45                //更新其祖先结点的第一个右兄弟结点的prev_sibling值
46                ++p_next->prev_sibling_;
47                //更新其祖先结点的所有右兄弟结点的parent值
48                do 
49                {
50                    p_next = &(*this)[next];
51                    ++p_next->parent_;
52                    next += p_next->next_sibling_;
53                }
 while(p_next->next_sibling_);
54            }
    
55            pos -= p_node->parent_;
56        }
 while(p_node->parent_);
57
58        //更新当前结点的parent值和其父结点的firsh_child和last_child值
59        p_parent->last_child_ = p_child->parent_ = child-parent;
60        if (!p_parent->first_child_)
61            p_parent->first_child_ = p_child->parent_;
62        return child;
63    }
   4)删除结点,分为两步,第一步先删除结点及其所有后代结点,也就是删除以该结点为根的子树,由于这颗子树所有结点是连续存放的,因此可以批量一起删除,第二步更新所有相关结点的偏移量,这里相关结点包括所删除结点的兄弟结点、父结点、祖先结点及其右兄弟结点。注意,这里可以作一些异常安全考虑,即如果第二步操作失败了,则可直接返回,这样就可保证整颗树不受影响。为了简单起见,以下C++代码对异常安全没有作处理,描述如下
 1    template<typename T>
 2    template<typename tree_iterator>
 3    tree_iterator mtree<T,false>::erase(tree_iterator iter)
 4    {
 5        assert(!iter.is_null());
 6
 7        tree_iterator it(iter);
 8        it.skip_progeny(true); 
 9        ++it;
10        size_t num = erase(iter.off_);
11        if (!it.is_null() && it.off_>iter.off_)
12            it.off_ -= num;
13        return it;
14    }
   当删除一个结点时,实质也就是删除以该结点为根的子树时,要注意迭代器的行为,这里应该要跳过所有后代结点,直接进到下一个结点进行后续遍历,由于具有多种迭代器,因此使用了模板成员函数,其内
部调用了erase(size_t)重载版本,实现如下
 1template<typename T>
 2    inline size_t mtree<T,false>::erase(size_t index)
 3    {
 4        tree_node* p_node = &(*this)[index];
 5        size_t prev=p_node->prev_sibling_,next=p_node->next_sibling_,parent=p_node->parent_;
 6
 7        //计算以该结点为根的子树所有结点数
 8        size_t num = size(index), pos;
 9        //批量删除该结点及其所有后代结点
10        size_t first = index, last = first+num;
11        base_type::erase(begin()+first,begin()+last);
12
13        //保存兄弟结点及其父结点的偏移量
14        tree_node *p_prev=NULL, *p_next=NULL,*p_parent=NULL;
15        if (prev) p_prev = &(*this)[index-prev];
16        if (next) p_next = &(*this)[index];
17        if (parent) p_parent = &(*this)[index-parent];
18
19        if (p_next)  //被删除结点不是最后一个孩子结点时
20        {
21            //更新父结点的last_child值
22            p_parent->last_child_ -= num;
23            //更新第一个右兄弟结点的prev_sibling值
24            p_next->prev_sibling_ = prev;
25            //更新所有右兄弟结点的parent值
26            pos = index;
27            do 
28            {
29                p_node = &(*this)[pos];
30                p_node->parent_ -= num;
31                pos += p_node->next_sibling_;
32            }
 while(p_node->next_sibling_);
33        }

34        else   //被删除结点是最后一个孩子结点时
35        {
36
37            if (p_prev)
38            {
39                //更新左兄弟结点的next_sibling值和父结点的parent值
40                p_prev->next_sibling_ = next;
41                p_parent->last_child_ -= prev;
42            }

43            else //父结点只有一个该孩子结点时
44            {
45                if (p_parent)
46                {
47                    //更新父结点的first_child和last_child值
48                    p_parent->first_child_ = p_parent->last_child_ = 0;
49                }

50            }

51        }

52        if (NULL==p_parent)  return num;
53
54        //从父结点开始,向上更新当被删除结点的所有右边结点的偏移量
55        pos = index-parent;
56        do 
57        {
58            p_node = &(*this)[pos];
59            if (p_node->next_sibling_)
60            {
61                //更新祖先结点的next_sibling值
62                p_node->next_sibling_ -= num;
63                //更新祖先结点的第一个右兄弟结点的prev_sibling值
64                next = pos + p_node->next_sibling_;
65                p_next = &(*this)[next];
66                p_next->prev_sibling_ -= num;
67                if (p_node->parent_)  //存在父结点
68                {
69                    //更新父结点的last_child值
70                    (*this)[pos-p_node->parent_].last_child_ -= num;
71                }

72                //更新所有祖先结点的右兄弟结点的parent值
73                do 
74                {
75                    p_next = &(*this)[next];
76                    p_next->parent_ -= num;
77                    next += p_next->next_sibling_;
78                }
 while(p_next->next_sibling_);
79            }

80            pos -= p_node->parent_;
81        }
 while(p_node->parent_);
82        return num;
83    }

扩展优化
   由于是使用vector容器来管理树结点tree_node,因此,如果数据是非平凡的类对象,当插入结点或删除结点时,就存在着移动时拷贝构造、析构的开销,而实际上这种开销完全可以避免,这就需要自己设计实现数据的内存管理了,当加入结点时,只需将数据拷贝到这块内存对应的位置上,当删除结点时,只需移动后面的内存数据即可,关于移动调用C函数memmove即可;另外,这个mtree是个模板类,只能管理同一种类型的数据,如果想管理多种不同类型的数据,可以通过把mtree变为普通类,append_child变为模板成员函数,在tree_node中加入长度域来表示数据的大小来实现,这样一来,获取数据的函数也应该是模板成员函数,而具体的数据类型由业务层来决定。
posted on 2011-07-13 15:10 春秋十二月 阅读(2467) 评论(9)  编辑 收藏 引用 所属分类: Algorithm

评论:
# re: 判断整数的正负零特性 2011-07-13 17:08 | jejer
这不是扩展 叫删减吧...  回复  更多评论
  
# re: 判断整数的正负零特性[未登录] 2011-07-13 17:10 | xiaok
uint32_t a = (uint32_t) val, b = (uint32_t)-val;
return (b>>31) - (a>>31);

这样可以把  回复  更多评论
  
# re: 判断整数的正负零特性 2011-07-13 20:52 | 草原神鹰
@xiaok
你这样不对,举个例子, 若int32_t val = 0x80000000,则check32(val)为0,而不是-1。  回复  更多评论
  
# re: 判断整数的正负零特性 2011-07-13 23:49 | flyinghearts
位运算技巧 建议看 hacker's delight 这本书。

两道题,可以直接用:
 return (value >= 0) - (value <= 0);
  return value == 0;  //判断是否为0
虽然有条件判断,但是编译器优化后的代码一般不存在条件跳转。

非要用位运算的话:

bool is_zero(int value)
{
//return value == 0;
const int bits = CHAR_BIT * sizeof(value) - 1;
// return 1 + (((value - 1) & ~value) >> bits);
return 1 + (((value & -value) - 1) >> bits);
}

int get_sign(int value)
{
//return (value >= 0) - (value <= 0);
const int bits = CHAR_BIT * sizeof(value) - 1;
return (value >> bits) | -(-value >> bits);
}



  回复  更多评论
  
# re: 判断整数的正负零特性[未登录] 2011-07-14 10:02 | xiaok
@草原神鹰
没明白=,=

0x80000000 不是=-2147483648<0么  回复  更多评论
  
# re: 判断整数的正负零特性 2011-07-14 13:18 | crazy
(!!val)+2*(val>>31)  回复  更多评论
  
# re: 判断整数的正负零特性[未登录] 2011-07-14 21:06 | cexer
嵌入式?如果是一般应用开发面试出这种题有点不靠谱,写产品的人哪能钻到这样的细节里去。  回复  更多评论
  
# re: 判断整数的正负零特性 2011-07-15 18:02 | Khan's Notebook
负数不是补码么  回复  更多评论
  
# re: 判断整数的正负零特性 2012-01-10 12:45 | 张龙琪
@xiaok
解析下  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理