Regarding representation of Josephus puzzle using arrays
Algorithms by Robert Sedwick, It was mentioned that linked list can be represented using Arrays, at following link
http://flylib.com/books/en/3.55.1.34/1/
Fig 3.8, here if 5 is removed from my understanding next 4 should be changed to index 6 as val 5 is removed, as we go thourgh the figure at item 4 is removed 开发者_如何学运维 next of val 3 is chaned. I am not following the logic of the figure. can aany one please help me.
Thanks!
the index is zero-based as opposed to the value itself (letters would be better values).
Example of removing the value 5
: before removing, next index of the node with value 4
is 4, which points to value 5
; after removing, next index is changed to 5, pointing to value 6
(next changed from 4 to 5).
Or, using the prefix v
to indicate values:
before
index ... 3 4 5 ...
----------------------
value v4 v5 v6
next 4 5 6
after
index ... 3 4 5 ...
----------------------
value v4 v5 v6
next 5 5 6
as you can see the node v4
is followed by v6
(index 5) practically removing v5
from the chain.
The values in the next
array are the index of the next value in the chain. If you want to remove the value 5, which sits at index 4, you have to change next[3]
from 4 to 5, so that the value at index 4 is effectively removed from the circle and will be skipped on later traversals.
After the update highlighted, the "node" with a value of 4 points to the "node" with a value of 6.
精彩评论