作者ric2k1 (Ric)
看板EE_DSnP
標題[公告] ref/adtTest.bst is now ready!
時間Fri May 16 03:03:09 2008
Please go to homework website to download.
Some comments:
1. 最後還是決定不要用 _tail (dummy node) 了, 因為好像沒什麼必要,
但卻會引起一個不太好處理的 bug...
2. 沒有 _parent, 原因是覺得 maintain 他太麻煩
3. 因為沒有 _parent, 所以當一個 node 的 right = 0 時, successor() 並不好找...
所以 keep 了一個 _trace 在 iterator 裡, 記錄這個 iterator 走過的痕跡...
不過跟我上課時說的不同, 我不是用 static data member, 因為這樣無法支援
多個 iterator 同時存在, 而且 li++ 及 li-- 也沒有辦法同時使用.
至於我的 trace 怎麼做... 其實還蠻簡單的, 應該是少於 50 行 code,
所以我賣個關子... XD
4. 建議大家先將 insert() and erase() 做好後先測一下, 不過為了讓 adtPrint
可以動作, 我寫了一個 BSTree::print() 如下:
void BSTree::print() const {
if (_root) _root->print(0);
}
void BSTreeNode::printSpace(size_t indent) const {
for (size_t i = 0; i < indent; ++i) cout << ' '; }
void BSTreeNode::print(size_t indent) const {
printSpace(indent); cout << _data << endl;
if (_left) _left->print(indent+2);
else { printSpace(indent+2); cout << "[0]" << endl; }
if (_right) _right->print(indent+2);
else { printSpace(indent+2); cout << "[0]" << endl; }
}
然後在 adtTest.h 裡加上:
void print(bool reverse = false) {
#ifdef TEST_BST
_container.print();
#endif
...
目前所附的 reference program 我並沒有將這個 print() 拿掉,
可以給大家參考一下.
5. ADTDelete -Random 會很慢, 主要是因為 AdtTest::getPos().
稍微改善了一下:
AdtType<AdtTestObj>::iterator li = _container.begin();
AdtType<AdtTestObj>::iterator lj = _container.end();
while ((li != lj) && (i++ != pos)) ++li;
不過還是有點慢就是了.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.121.129.110
1F：推 bnsblue:要是我已經用了_parent寫.......orz 05/16 08:39
2F：推 timrau:STL set的node也是有parent的 所以也還好XD 05/16 10:29
3F：推 bnsblue:真的喔 XD 我本來想去看set的 我記得那好像也是BST架構 05/16 12:09
4F：→ bnsblue:可是後來想這樣就作弊了XD就算了 05/16 12:09
5F：推 danielko:好像還是得iterator寫完再測 不然adtTest.h 05/16 14:32
6F：→ danielko:compile會不給過 orz 05/16 14:32
7F：推 bnsblue:你有把上面幾個print放到該放的地方嗎@@ 05/16 15:00
8F：推 danielko:所以要放到bst.h還是adtTest.h ?? 05/16 17:18
9F：→ danielko:喔喔 我看到老師新po的文章了 XD 05/16 17:18
10F：→ ric2k1:大家交上來的時候不要把上面的 print 加進去哦! 05/17 09:43