基於矩陣的問題的數據結構

Question

我經常發現自己不確定什麼數據結構對於基於矩陣的算法更好。

「基於矩陣的算法」我的意思是算法，如Needleman-Wunsh alignment。有很多算法可以用矩陣直觀地表示。

我不知道我應該選擇：陣列

• 陣列
• 鏈表的鏈表
• 哈希表，其中的關鍵是像（行，列）
• 等一個元組

面對這個僵局時我需要考慮什麼？

Obs：我的問題是「語言開放」。您可以在答案中使用任何編程語言。

Answer 1

要使用的數據結構取決於您的算法以及您將如何訪問該矩陣。例如，如果大小是固定的並且需要快速訪問，則最好使用2維數組，因爲無論您使用什麼，都必須分配該空間。如果矩陣的大小是動態確定的，那麼可能是矢量的矢量（或者取決於語言的類似數據結構）。 另一個問題是，如果您的矩陣非常稀疏且非常大（如在數字幾何算法中）並且您必須經常對該矩陣進行算術運算，那麼三重格式的數據結構可能非常有用，例如可以創建的壓縮行存儲使用3個向量。您可以在此鏈接閱讀更多https://de.wikipedia.org/wiki/Compressed_Row_Storage 希望它有幫助