哪些数据结构可以有效地存储二维"网格"数据？

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]

在此方法中,"行指针"列表(在左侧表示)每个都是一个新的独立数组.与2-d数组一样,通过调整适当的索引来访问相邻元素.

完全连接的细胞(2-d双链表)

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

该方法使每个单元格包含最多四个指向其相邻元素的指针.通过适当的指针访问相邻元素.您将需要保持指向元素的指针结构(可能使用上述方法之一),以避免必须按顺序逐步浏览每个链接列表.这种方法有点笨拙,但它确实在Knuth的Dancing Links算法中有一个重要的应用,其中在执行算法期间修改链接以跳过网格中的"空白"空间.

Answer 2

如果查找时间对您很重要,那么二维数组可能是您的最佳选择,因为在给定单元格的(x,y)坐标的情况下查找单元格的邻居是一个恒定时间操作.