Re: [請益] XOR linked list
※ 引述《wsx02 ()》之銘言：
: 我碰到一個問題 http://ppt.cc/~ZsY 這邊的(e)小題
: 拿index=2的那邊 左link = 十進1 = 二進001 右link = 十進3 = 二進011
: 所以(b)的答案是 001 XOR 011 = 010
: 其他的答案是(a)010, (b)010, (c)110, (d)011
: 可是這要怎麼traverse呢?
: 我在wiki查到的 http://en.wikipedia.org/wiki/XOR_linked_list
: 有一段When you traverse the list from left to right:提到
: 可是我看不太懂0.0
: 請問用這題的數字當例子 應該要怎麼找呢?
: 謝謝
我們會存成這樣的資料結構:
1 2 3 4
data HAT CAT EAT BAT
link 2 2 6 3
要往下一格移動時我們需要前一格在哪和這一格在哪
例如我們現在在 HAT (1), 已知前一格是接地 (0),
那麼下一格就是 link(1) XOR 0 = 2 XOR 0 = 2 就到了 CAT
再一次的話 現在在 CAT (2), 前一格在 (1)
於是下一格就是 link(2) XOR 1 = 2 XOR 1 = 3 就到了 EAT 依此類推
只要當找出來的下一格是接地 (0) 就是結束了
大概像是這樣
--
1985/01/12 三嶋鳴海 1989/02/22 優希堂悟 1990/02/22 冬川こころ 1993/07/05 小町
つぐみ 歡迎來到 1994/05/21 高江ミュウ 1997/03/24 守野いづみ 1997/03/24 伊野瀬
チサト 1998/06/18 守野くるみ 打越鋼太郎的 1999/10/19 楠田ゆに 2000/02/15 樋口遙
2002/12/17 八神ココ 2011/01/11 HAL18於朱倉岳墜機 ∞與∫的世界 2011/04/02 茜崎空
啟動 2012/05/21 第貮日蝕計畫預定 2017/05/01~07 LeMU崩壞 2019/04/01~07 某大學合宿
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.91
推
04/17 21:27, , 1F
04/17 21:27, 1F