需要一个缓存友好的数据结构来存储二维数组中字母的邻居

Question

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

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

'f'的周围邻居是[abcegijk].我正在尝试创建一个缓存友好的数据结构来存储节点的邻居.现在我有类似的东西

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

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

请注意,节点可能具有的最大邻居是8.任何人都有任何建议吗？我需要将结构作为恒定时间邻居查找,因此我将预先计算每个节点的邻居.

Answer 1

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