开发者

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.

Regarding representation of Josephus puzzle using arrays

After the update highlighted, the "node" with a value of 4 points to the "node" with a value of 6.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜