language-agnostic - 哪些数据结构可以有效存储二维 "grid"数据？

Question

我正在尝试编写一个对数字网格执行操作的应用程序，每次函数运行时，每个单元格的值都会发生变化，并且每个单元格的值取决于它的邻居。每个单元格的值将是一个简单的整数。

在这里存储我的数据的最佳方式是什么？我已经考虑过平面列表/数组结构，但这似乎无效，因为我必须反复进行计算才能确定哪个单元格在当前单元格的“上方”(当存在任意网格大小时)和嵌套列表，这不会' 似乎不是表示数据的好方法。

我不禁感到必须有一种更好的方式来表示这种数据在内存中用于这种目的。有任何想法吗？

(注意，我不认为这真的是一个主观问题 - 但堆栈溢出似乎认为它是......我有点希望有一种可接受的方式存储此类数据)

Answer 1

这里有一些方法。我将(尝试)用 3x3 网格的表示来说明这些示例。

平面阵列

+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+

a[row*width + column]

要访问左侧或右侧的元素，请减或加 1(注意行边界)。要访问上方或下方的元素，请减去或添加行大小(在本例中为 3)。

二维数组(对于 C 或 FORTRAN 等支持此功能的语言)

+-----+-----+-----+
| 0,0 | 0,1 | 0,2 |
+-----+-----+-----+
| 1,0 | 1,1 | 1,2 |
+-----+-----+-----+
| 2,0 | 2,1 | 2,2 |
+-----+-----+-----+

a[row,column]
a[row][column]

访问相邻元素只是增加或减少行号或列号。编译器仍然执行与平面数组完全相同的算法。

数组数组(例如 Java)

+---+   +---+---+---+
| 0 |-->| 0 | 1 | 2 |
+---+   +---+---+---+
| 1 |-->| 0 | 1 | 2 |
+---+   +---+---+---+
| 2 |-->| 0 | 1 | 2 |
+---+   +---+---+---+

a[row][column]

在此方法中，“行指针”列表(在左侧表示)每个都是一个新的独立数组。与二维数组一样，通过调整适当的索引来访问相邻元素。

全链接单元格(二维双向链表)

+---+   +---+   +---+
| 0 |-->| 1 |-->| 2 |
|   |<--|   |<--|   |
+---+   +---+   +---+
 ^ |     ^ |     ^ |
 | v     | v     | v
+---+   +---+   +---+
| 3 |-->| 4 |-->| 5 |
|   |<--|   |<--|   |
+---+   +---+   +---+
 ^ |     ^ |     ^ |
 | v     | v     | v
+---+   +---+   +---+
| 6 |-->| 7 |-->| 8 |
|   |<--|   |<--|   |
+---+   +---+   +---+

此方法使每个单元格最多包含四个指向其相邻元素的指针。访问相邻元素是通过适当的指针。您仍然需要保留指向元素的指针结构(可能使用上述方法之一)以避免必须按顺序遍历每个链表。这种方法有点笨拙，但它在 Knuth's Dancing Links 中确实有重要的应用。算法，其中在算法执行期间修改链接以跳过网格中的“空白”空间。