作者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