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