c++ - 需要缓存友好的数据结构来将字母的邻居存储在二维数组中

Question

假设以下是我们正在操作的二维数组

a b c d
e f g h
i j k l
m n o p

“f”的周围邻居是 [a b c e g i j k]。我正在尝试创建一个缓存友好的数据结构来存储节点的邻居。现在我有这样的东西

struct Neighbor{
   size_t neighborPosition[8][2];
   size_t size;
};

typedef size_t Position[2];
typedef Neighbor** NeighborTable;

请注意，一个节点最多可以有 8 个邻居。有人有什么建议吗？我需要该结构是一个恒定时间的邻居查找，所以我将预先计算每个节点的邻居。

Answer 1

除了边缘单元格外，每个单元格在相对位置方面都有相同的邻居。但是如果你添加一个边框(在开始和结束处额外的行和列)，并用一个让你知道它是边框的值填充它，你根本不需要任何数据结构来识别邻居。