基于矩阵的问题的数据结构

Question

我经常发现自己不确定什么数据结构对于基于矩阵的算法更好。

“基于矩阵的算法”我的意思是算法，如Needleman-Wunsh alignment。有很多算法可以用矩阵直观地表示。

我不知道我应该选择：阵列

• 阵列
• 链表的链表
• 哈希表，其中的关键是像（行，列）
• 等一个元组

面对这个僵局时我需要考虑什么？

Obs：我的问题是“语言开放”。您可以在答案中使用任何编程语言。

Answer 1

要使用的数据结构取决于您的算法以及您将如何访问该矩阵。例如，如果大小是固定的并且需要快速访问，则最好使用2维数组，因为无论您使用什么，都必须分配该空间。如果矩阵的大小是动态确定的，那么可能是矢量的矢量（或者取决于语言的类似数据结构）。 另一个问题是，如果您的矩阵非常稀疏且非常大（如在数字几何算法中）并且您必须经常对该矩阵进行算术运算，那么三重格式的数据结构可能非常有用，例如可以创建的压缩行存储使用3个向量。您可以在此链接阅读更多https://de.wikipedia.org/wiki/Compressed_Row_Storage 希望它有帮助