我有一個關于數據結構的作業，prof希望我們在項目中使用不同類型的DS，但我不知道他的意思是（一種將項目保持相互位置關系的三維數據結構。數據結構中的每個單元格都可以容納多個項目。） 我嘗試了對象的 Arraylists、對象隊列！知道我可以嘗試哪種 DS 來節省我的時間嗎？
2 回答
FFIVE
TA貢獻1797條經驗 獲得超6個贊
最簡單的空間數據結構是 3D 數組。在 java 中，您可以創建一個如下：
Object[][][] my3DArray = new Object[10][10][10];
在這里，您可以存儲 10*10*10=1000 個彼此空間關系的對象。不幸的是，每個維度只有 10 個可能的坐標。
如果您想要更高效的東西，請尋找四叉樹/八叉樹、kd 樹（如@BeyelerStudios 在評論中提到的）、R 樹、LSH（局部敏感哈希）甚至空間填充曲線（Z 曲線、希爾伯特曲線） ，……）。這些只是主要的系列，每種類型的 DS 都有許多版本。
編輯以回答評論。除了 3D 陣列方法，上述所有解決方案都非常節省空間?？臻g效率最高的可能是PH-Tree（一種四叉樹，由我自己開發），在某些情況下，它可能需要比普通坐標數組更少的內存。不幸的是，它的理解和實現相對復雜。
如果要使用一維排序方案，例如數組或列表，請嘗試使用空間填充曲線。Z 曲線可能是最簡單的。使用空間填充曲線，您可以為空間中的每個點計算一個“關鍵”（z-key 或 Morton-number），然后在數組或列表中對它們進行排序。在這樣的有序列表/數組中，直接鄰居也可能（但不保證）在 3D 空間中接近。相反，在 3D 空間中接近的點往往（但不能保證）在列表/數組中接近。
對于整數坐標，可以通過交錯坐標位來計算z 鍵（也稱為MortonNumber）。您也可以對浮點值執行此操作，但您需要小心處理負值，否則您可能會在正值和負值之間產生裂痕。
慕桂英3389331
TA貢獻2036條經驗 獲得超8個贊
如果你被允許使用 Guava，那么我會考慮一個Multimap的MyObjindexed by XyzCoord，其中XyzCoord是一個自定義對象來保存三個位置數字，并且MyObj是你希望在不同坐標處存儲一個或多個的自定義對象。
避免番石榴，您可以使用標準Map的List<MyObj>。它也可以由List<Integer>長度為 3 的哪個索引。
事實上，有很多很多方法可以做到這一點。因此，您的問題可能有點過于寬泛。再看一下集合類，如果您不知道它們是如何使用的，請嘗試詢問有關每個類的具體問題。
添加回答
舉報
0/150
提交
取消