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