c# - 用于 Excel 克隆的正确数据结构

Question

假设我正在使用 C# 开发 Excel 克隆。我的网格表示如下:

private struct CellValue
{
    private int column;
    private int row;
    private string text;
}
private List<CellValue> cellValues = new List<CellValue>();

每次用户添加文本时，我只是将其打包为 CellValue 并将其添加到 cellValues 中。给定一个 CellValue 类型，我可以在 O(1) 时间内确定它的行和列，这很棒。但是，给定一列和一行，我需要遍历整个 cellValues 以查找该列和行中的文本，这非常慢。另外，给定一个文本，我也需要遍历整个内容。是否有任何数据结构可以让我在 O(1) 时间内完成所有 3 个任务？

更新:翻阅了一些答案，我认为我没有找到我喜欢的答案。我可以:

1. 不要保留超过 2 个 CellValue 副本，以避免同步它们。在 C 世界中，我会很好地使用指针。
2. 可以动态添加行和列(与 Excel 不同)。

Answer 1

我会选择稀疏数组(链表的链表)以最小的存储空间提供最大的灵 active 。

在此示例中，您有一个行链接列表，每个元素指向该行中单元格的链接列表(您可以根据需要反转单元格和行)。

 |
 V
+-+    +---+             +---+
|1| -> |1.1| ----------> |1.3| -:
+-+    +---+             +---+
 |
 V
+-+             +---+
|7| ----------> |7.2| -:
+-+             +---+
 |
 =

每个行元素中都有行号，每个单元格元素都有一个指向其行元素的指针，因此从单元格中获取行号的复杂度为 O(1)。

同样，每个单元格元素都有其列号，这也是 O(1)。

没有简单的方法可以让 O(1) 立即找到给定行/列处的单元格，但稀疏数组的速度与它要获得的速度一样快，除非您为每个可能的单元格预先分配信息，以便您可以在数组上进行索引查找 - 这在存储方面会非常浪费。

您可以做的一件事是使一维成为非稀疏的，例如将列作为主数组(而不是链表)并将它们限制为 1,000 - 这将使列查找索引(快速)，然后进行搜索在稀疏行上。

我不认为您可以永远获得文本查找的 O(1) 仅仅因为文本可以在多个单元格中重复(与行/列不同)。我仍然相信稀疏数组将是搜索文本的最快方法，除非您在另一个数组中维护所有文本值的排序索引(同样，这可以使其更快但以大量内存为代价)。