algorithm - 网格数据结构

Question

通常“可扩展”网格表示为列表列表(行列表，每行都有单元格列表)，这些列表是某种链表。

在此数据结构中操作(删除、插入)行既简单又便宜，只需重新链接以前的节点即可，但涉及到列时，例如删除列会变成一个非常长的操作，我需要“循环”所有行以删除索引单元格。显然，这不是好的行为，至少对我而言是这样。

我在这里不是在谈论数据库；我发现的一个很好的例子是将一些文本文件放入文本编辑器中，(据我所知)文本编辑器主要将行拆分为行并且很容易删除行。我希望删除列与删除某些行一样经济高效。

最后，我需要的是一些多维网格，但我认为任何二维简单网格都适用于 MD，对吗？

Answer 1

你可以有一个二维“链接矩阵”(我忘记了正确的术语):

... Col 3 ... Col 4 ...
      |         |
... --X-- ... --Y-- ...
      |         |
...  ...  ...  ...  ...

如图所示，每个单元格都有四个邻居。此外，您需要可能指示行/列位置的行标题和列标题，以及指向每行或每列中的第一个单元格。这些最容易表示为没有上邻域的特殊单元格(用于列标题)。

在 3 和 4 之间插入一个新列意味着向下迭代第 3 列中的单元格 X，并插入一个新的右邻单元格 Z。这个新单元格 Z 向左链接到 X，向右链接到 Y。您还需要添加一个新列标题，并垂直链接新单元格。那么4之后的所有列的位置都可以重新编号(第4列变成第5列)。

... Col 3 Col 4 Col 5 ...
      |     |     |
... --X-----Z-----Y-- ...
      |     |     |
...  ...   ...   ...  ...

插入一列的成本是 O(n) 用于插入和链接新单元格，而 O(m) 用于更新列标题。这是一个类似的删除过程。

因为每个单元格只有四个链接，所以相同的算法用于行插入/删除。