我正在編寫基於手機的遊戲。我對數據結構很感興趣，它支持快速（如果可能的話，分段O（1））插入，查找和刪除。數據結構將存儲來自域[0，n]的整數，其中n是事先知道的（這是一個常數），n相對較小（大約爲100000）。c中的數據結構用於快速查找/插入/去除整數（來自已知的有限域）
到目前爲止，我已經考慮了一個整數數組，其中「ith」位被設置，如果該集合中包含「ith」整數（所以a [0]是整數0到31，a [1]是整數32到63等）。
有沒有更簡單的方法來做到這一點在c？
你的想法很簡單和高效 - 假設你有100000/8 = 12.5KB的玩法，那麼在尋找其他解決方案時我沒有看到任何意義。
一個平面陣列會做，但會花費100,000位。 另一種可能性是「哈希集合」。
100,000位只有12.5 KB - 除非他需要大量的這些位集，那麼內存不應該是一個問題？ – 2010-05-23 18:27:24
@Paul R - 它的100,000位與設置的數量無關。如果他只設置幾個，他可能不想花那麼多。我同意，即使在「手機」上，12KB對我來說也不是很重要。但是，如果他需要這種結構的幾個實例，那麼更少會更好。在任何情況下，爲了它的價值，散列集也是O（1）。 – ChrisW 2010-05-23 20:40:34
更簡單的方法（但更多的內存消耗）：'char a [100000];'。其他可能性（取決於使用場景）是使用散列表。 – avakar 2010-05-23 17:25:08
我認爲你考慮的是位陣列。您可以搜索Google現有的實施。但也許char陣列的小開銷就足夠了？ – Anycorn 2010-05-23 17:29:59
你說你正在存儲和檢索整數，但似乎你可能正在存儲布爾值。或者你所說的位數組只是表示存儲在另一個表中的數據？ – nategoose 2010-05-23 20:15:17