需求分析
在數(shù)據(jù)結(jié)構(gòu)中，樹有兩種存儲方式，一種是鏈?zhǔn)酱鎯Γ硪环N是順序存儲。前者就是使用指針來記錄樹結(jié)點間的關(guān)系，在新增結(jié)點或刪除結(jié)點時，只需改變與父結(jié)點或兄弟結(jié)點的指針值即可，實現(xiàn)較為簡單；后者就是使用數(shù)組來存儲，可以用相對偏移量來記錄樹結(jié)點間的關(guān)系，在新增結(jié)點或刪除結(jié)點時，則不僅是改變與父結(jié)點或兄弟結(jié)點的相對偏移量，還需要改變其它結(jié)點的相對偏移量，實現(xiàn)較為復(fù)雜。近來在項目中，對一個普通文本文件進行分析提取數(shù)據(jù)，而這個文件內(nèi)的數(shù)據(jù)從內(nèi)容看，具有層次嵌套關(guān)系，要將這樣的數(shù)據(jù)發(fā)送到服務(wù)器去處理，我考慮了兩種如下方法：
（1）自定義XML格式，在本地使用XML庫，如libxml2、tinyxml等，將數(shù)據(jù)寫到XML臨時文件或內(nèi)存中，再將這個XML臨時文件或內(nèi)存發(fā)過去，在服務(wù)器那邊使用XML庫來解析。這種方法比較通用而且跨平臺，如果XML庫不支持將其所存儲的數(shù)據(jù)轉(zhuǎn)儲到一塊連續(xù)內(nèi)存，那么就只能先存到XML臨時文件，再將這個文件發(fā)過去，這樣一來，就存在磁盤IO操作，效率較低。否則，就可以先將數(shù)據(jù)轉(zhuǎn)儲到一塊連續(xù)內(nèi)存，再將這塊內(nèi)存發(fā)過去，這樣一來，這塊連續(xù)內(nèi)存就需要另外開辟，因此多了一套內(nèi)存管理操作，但是比用臨時文件方式，沒有磁盤IO，效率要高些。
（2）實現(xiàn)基于順序存儲的樹，而且還是多叉樹，因為實際數(shù)據(jù)具有多層次嵌套關(guān)系，將數(shù)據(jù)放進這顆樹中，再直接將這顆樹發(fā)過去，在服務(wù)器那邊直接解析這顆樹，這樣一來，不用臨時文件，沒有磁盤IO，無須另外開辟內(nèi)存，充分利有現(xiàn)有空間，效率較高。
設(shè)計開發(fā)
從服務(wù)器效率至上的觀點考慮，我選擇了第2種方法，并實現(xiàn)了基于順序存儲的多叉樹，關(guān)于順序存儲，又有兩種如下方式：
（1）深度優(yōu)先存儲，按照自上而下從左到右存儲樹的所有結(jié)點，先存儲結(jié)點及它的孩子，再存儲它的兄弟。因此結(jié)點的孩子和兄弟都不一定是連續(xù)的，當(dāng)一個結(jié)點的所有孩子都是葉子結(jié)點時，則所有孩子是連續(xù)存放的。結(jié)點和它的第一個孩子（若有）是連續(xù)的，如下圖所示
（2）廣度優(yōu)先存儲，按照從左到右自上而下存儲樹的所有結(jié)點，先存儲結(jié)點及它的兄弟，再存儲它的孩子，因此結(jié)點的孩子和兄弟都是連續(xù)存放的，孩子與其父親之間不一定是連續(xù)的，如下圖所示
本文描述第1種存儲方式實現(xiàn)的多叉樹，介紹三種主要操作：設(shè)置根結(jié)點、增加結(jié)點和刪除結(jié)點，為簡單起見，使用vector作為內(nèi)部動態(tài)數(shù)組，使用索引而非迭代器作為外部接口，來訪問結(jié)點，索引0表示空索引，有效索引從1開始。關(guān)于迭代器的設(shè)計，有諸多考慮，如前序、后序、廣度優(yōu)先、指定深度、葉子結(jié)點等各種遍歷方法，因時間和篇幅原因，不能一一講述，待后面有時間會陸續(xù)補充完善。
1）樹結(jié)點定義，由5個偏移量域和1個數(shù)據(jù)域組成，C++代碼描述如下
1
template<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的兩個構(gòu)造函數(shù)，其實現(xiàn)如下
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）設(shè)置根結(jié)點，為方便實現(xiàn)，根結(jié)點固定存放在數(shù)組中第1個位置，對應(yīng)下標(biāo)為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函數(shù)來獲取根結(jié)點，其實現(xiàn)如下
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）增加結(jié)點，這里要分為三步，第一步要找到插入位置，第二步插入結(jié)點，第三步改變相關(guān)結(jié)點的相對偏移量，這里相關(guān)結(jié)點包括當(dāng)前所插結(jié)點、所插結(jié)點兄弟結(jié)點、父結(jié)點、祖先結(jié)點及其右兄弟結(jié)點；注意，這里可以作一些異常安全考慮，即如果第二步操作失敗了，則可直接返回，這樣就可保證整顆樹不受影響。為了簡單起見，以下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 }
以上模板成員函數(shù)及其深度迭代器的特化版本都調(diào)用了內(nèi)部append_child(size_t)函數(shù)，該函數(shù)實現(xiàn)如下：
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 //插入結(jié)點
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 //更新當(dāng)前結(jié)點的prev_sibling值和其左兄弟結(jié)點的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 //從父結(jié)點開始,向上更新當(dāng)前結(jié)點所有右邊結(jié)點的偏移量
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 //更新其祖先結(jié)點的next_sibling值
42 ++p_node->next_sibling_;
43 next = pos + p_node->next_sibling_;
44 p_next = &(*this)[next];
45 //更新其祖先結(jié)點的第一個右兄弟結(jié)點的prev_sibling值
46 ++p_next->prev_sibling_;
47 //更新其祖先結(jié)點的所有右兄弟結(jié)點的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 //更新當(dāng)前結(jié)點的parent值和其父結(jié)點的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）刪除結(jié)點，分為兩步，第一步先刪除結(jié)點及其所有后代結(jié)點，也就是刪除以該結(jié)點為根的子樹，由于這顆子樹所有結(jié)點是連續(xù)存放的，因此可以批量一起刪除，第二步更新所有相關(guān)結(jié)點的偏移量，這里相關(guān)結(jié)點包括所刪除結(jié)點的兄弟結(jié)點、父結(jié)點、祖先結(jié)點及其右兄弟結(jié)點。注意，這里可以作一些異常安全考慮，即如果第二步操作失敗了，則可直接返回，這樣就可保證整顆樹不受影響。為了簡單起見，以下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 }
當(dāng)刪除一個結(jié)點時，實質(zhì)也就是刪除以該結(jié)點為根的子樹時，要注意迭代器的行為，這里應(yīng)該要跳過所有后代結(jié)點，直接進到下一個結(jié)點進行后續(xù)遍歷，由于具有多種迭代器，因此使用了模板成員函數(shù)，其內(nèi)
部調(diào)用了erase(size_t)重載版本，實現(xiàn)如下
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 //計算以該結(jié)點為根的子樹所有結(jié)點數(shù)
8 size_t num = size(index), pos;
9 //批量刪除該結(jié)點及其所有后代結(jié)點
10 size_t first = index, last = first+num;
11 base_type::erase(begin()+first,begin()+last);
12
13 //保存兄弟結(jié)點及其父結(jié)點的偏移量
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) //被刪除結(jié)點不是最后一個孩子結(jié)點時
20 {
21 //更新父結(jié)點的last_child值
22 p_parent->last_child_ -= num;
23 //更新第一個右兄弟結(jié)點的prev_sibling值
24 p_next->prev_sibling_ = prev;
25 //更新所有右兄弟結(jié)點的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 //被刪除結(jié)點是最后一個孩子結(jié)點時
35 {
36
37 if (p_prev)
38 {
39 //更新左兄弟結(jié)點的next_sibling值和父結(jié)點的parent值
40 p_prev->next_sibling_ = next;
41 p_parent->last_child_ -= prev;
42 }
43 else //父結(jié)點只有一個該孩子結(jié)點時
44 {
45 if (p_parent)
46 {
47 //更新父結(jié)點的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 //從父結(jié)點開始,向上更新當(dāng)被刪除結(jié)點的所有右邊結(jié)點的偏移量
55 pos = index-parent;
56 do
57 {
58 p_node = &(*this)[pos];
59 if (p_node->next_sibling_)
60 {
61 //更新祖先結(jié)點的next_sibling值
62 p_node->next_sibling_ -= num;
63 //更新祖先結(jié)點的第一個右兄弟結(jié)點的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_) //存在父結(jié)點
68 {
69 //更新父結(jié)點的last_child值
70 (*this)[pos-p_node->parent_].last_child_ -= num;
71 }
72 //更新所有祖先結(jié)點的右兄弟結(jié)點的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 }
擴展優(yōu)化
由于是使用vector容器來管理樹結(jié)點tree_node，因此，如果數(shù)據(jù)是非平凡的類對象，當(dāng)插入結(jié)點或刪除結(jié)點時，就存在著移動時拷貝構(gòu)造、析構(gòu)的開銷，而實際上這種開銷完全可以避免，這就需要自己設(shè)計實現(xiàn)數(shù)據(jù)的內(nèi)存管理了，當(dāng)加入結(jié)點時，只需將數(shù)據(jù)拷貝到這塊內(nèi)存對應(yīng)的位置上，當(dāng)刪除結(jié)點時，只需移動后面的內(nèi)存數(shù)據(jù)即可，關(guān)于移動調(diào)用C函數(shù)memmove即可；另外，這個mtree是個模板類，只能管理同一種類型的數(shù)據(jù)，如果想管理多種不同類型的數(shù)據(jù)，可以通過把mtree變?yōu)槠胀悾琣ppend_child變?yōu)槟０宄蓡T函數(shù)，在tree_node中加入長度域來表示數(shù)據(jù)的大小來實現(xiàn)，這樣一來，獲取數(shù)據(jù)的函數(shù)也應(yīng)該是模板成員函數(shù)，而具體的數(shù)據(jù)類型由業(yè)務(wù)層來決定。
posted on 2011-07-13 15:10
春秋十二月 閱讀(4587)
評論(9) 編輯 收藏 引用 所屬分類:
Algorithm