作者ric2k1 (Ric)
看板EE_DSnP
标题Re: [问题] dlist的dummy放哪
时间Wed Dec 8 11:38:47 2010
※ 引述《hiroki1139 (小波)》之铭言：
: // 版上好多人都写完了好可怕
: 请问一下
: dummy要放在头还是尾巴啊
: 因为有一行注解写到// _head is dummy node
: 可是同学都说要放最後一个
: 所以要怎麽放呢
: 还是根本没差XD
: 谢谢~~
1. 在 dlist 刚 construct 时，整个 dlist 只有一个 dummy node,
所以 _head is dummy node, 而且其 _prev 与 _next 都是指到自己。
2. 但在有 data insert 进去之後，
_head 就是指到真正的第一笔资料 (i.e. 最小的 data),
这时 _head->_prev = dummy, dummy->_next = _head.
同时要注意，有效资料的最後一笔 (i.e. 最大的 data), say "tail",
要保持 tail->_next = dummy, dummy->_prev = tail.
也就是说，从 _head 到 tail 到 dummy 再回到 _head，绕成一圈，
而且因为是 doubly linked list, 所以反向绕也可以通.
3. 注意我们只有 _head 这个 data member,
上面所述的 dummy 与 tail 只是说明用而已，你要自行保证 link 的连续性。
4. dummy node 从头到尾都会存在，而且是同一个 ListNode,
因为 dlist 在做任何操作时顶多只会动到 dummy node 的 _prev or_next,
不会动到 dummy node 本身。
5. clear() 会把所有 data node 清掉，只剩 dummy node.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.36.52.227
1F：推 TommyKSHS:那如果从头到尾 dlist 都有一个 dummy node 但是结果是 12/09 02:54
2F：→ TommyKSHS:对的 这样可以吗？ (我一开始误解了就写成一直有 dummy. 12/09 02:54
3F：→ ric2k1:? 从头到尾都有 dummy node 是没错啊! 你的问题是? 12/09 10:55
4F：→ ric2k1:不过昨天有人问说如果 _head 一直指到 dummy node 可不可以 12/09 10:57
5F：→ ric2k1:==> 虽然我是说 _head 应该是要指到最小的 element, 但是如 12/09 10:57
6F：→ ric2k1:果你们已经写了, 那就算了, 毕竟题目好像也没有规定清楚... 12/09 10:58
7F：推 TommyKSHS:呃…我的意思是 _head 一直指到 dummy Orz... 12/09 12:12
8F：→ TommyKSHS:昨天晚上意识不清 说错了 12/09 12:13
9F：→ ric2k1:回楼上，是的，这就是昨天同学问我的，如果你们已经这样做 12/09 13:36
10F：→ ric2k1:也 OK 啦! 12/09 13:36
11F：→ ckmarkoh:也就是直接把_head当成end() 那begin()就取_head+1 12/11 19:44
12F：→ ckmarkoh:其实这样比较方便 不需要更改_head所指的位置 12/11 19:45
13F：→ ric2k1:嗯，也是啦! 12/11 20:17
14F：推 wintercobra:cool! 12/13 16:42