用于Excel克隆的正确数据结构
假设我正在使用C＃中的Excel克隆。 我的网格表示如下：
private struct CellValue { private int column; private int row; private string text; } private List cellValues = new List(); 每次用户添加文本时，我只需将其打包为CellValue并将其添加到cellValues中。 给定一个CellValue类型，我可以在O（1）时间内确定它的行和列，这很好。 但是，给定一个列和一行，我需要循环遍历整个cellValues以查找该列和行中的文本，这非常慢。 另外，给定一个文本，我也需要遍历整个事情。 是否有任何数据结构我可以在O（1）时间内完成所有3个任务？
更新：通过一些答案，我不认为我找到了一个我喜欢的答案。 我可以吗：
- 不保留2个以上的CellValue副本，以避免同步它们。 在C世界中，我会很好地使用指针。
- 可以动态添加行和列（与Excel不同）。
我会选择稀疏数组（链表的链表），以最小的存储空间提供最大的灵活性。
在此示例中，您有一个链的行列表，每个元素都指向该行中单元格的链接列表（您可以根据需要反转单元格和行）。
| V +-+ +---+ +---+ |1| -> |1.1| ----------> |1.3| -: +-+ +---+ +---+ | V +-+ +---+ |7| ----------> |7.2| -: +-+ +---+ | =
每个行元素都包含行号，每个单元格元素都有一个指向其行元素的指针，因此从单元格中获取行号是O（1）。
类似地，每个单元元素都有其列号，也就是O（1）。
没有简单的方法可以让O（1）立即找到给定行/列的单元格，但是稀疏数组的速度和它要获得的速度一样快，除非你为每个可能的单元格预先分配信息，这样你就可以进行索引查找在arrays上 – 这在存储方面会非常浪费。
你可以做的一件事是使一个维度非稀疏，例如使列成为主数组（而不是链表）并将它们限制为1,000 – 这将使列查找索引（快速），然后搜索稀疏行。
我认为您不能仅仅因为文本可以在多个单元格中复制（与行/列不同）而获得O（1）文本查找。 我仍然相信稀疏数组将是搜索文本的最快方法，除非你维护另一个数组中所有文本值的排序索引（同样，这可以使它更快但是以大量内存为代价）。
我认为你应该使用其中一个索引集合使其工作得相当快，完美的是KeyedCollection
您需要通过扩展此类来创建自己的集合。 这样你的对象仍然会包含行和列（所以你不会丢失任何东西），但你可以搜索它们。 可能你必须创建一个封装（行，列）的类并使其成为键（因此使其成为不可变的并覆盖equals并获取哈希代码）
我创造了
Collection> rowCellValues = new Collection>();
和
Collection> columnCellValues = new Collection>();
外部集合对于每个行或列都有一个条目，由行或列编号索引，内部集合具有该行或列中的所有单元格。 应该将这些集合填充为创建新CellValue对象的过程的一部分。
rowCellValues[newCellValue.Row].Add(newCellValue); columnCellValues[newCellValue.Column].Add(newCellValue);
这种过早优化的气味。
也就是说，excel的一些特性对于选择一个好的结构很重要。
首先，excel以适度非线性的方式使用细胞。 解析公式的过程涉及以有效随机顺序遍历电子表格。 该结构将需要一种易于查找随机密钥值的机制，由于循环引用而将其标记为脏，已解决或无法解析。 还需要一些方法来了解何时没有剩余未解决的单元格，以便它可以停止工作。 涉及链表的任何解决方案可能都不是最佳的，因为它们需要线性扫描才能获得这些单元。
另一个问题是excel一次显示一系列单元格。 这似乎是微不足道的，并且在很大程度上它是，但如果应用程序可以提取一次性绘制一系列单元格所需的所有数据，那肯定是理想的。 其中一部分可能是跟踪行和列的显示高度和宽度，以便显示系统可以在该范围内迭代，直到收集到所需的单元格宽度和高度。 以这种方式迭代的需要可能排除使用散列策略来稀疏存储单元。
最重要的是，电子表格的代表性模型存在一些弱点，可以通过略微不同的方法更有效地解决这些问题。
例如，列聚合有点笨重。 列总数很容易在excel中实现，但它有一种神奇的行为，可以在大多数时间工作，但不是所有时间。 例如，如果您在聚合区域中添加一行，则对该聚合的进一步计算可能会继续有效，具体取决于您添加它的方式。 如果你复制并插入一行（并替换值）一切正常，但如果你将单元格剪切并粘贴一行，那么事情就不会那么顺利。
鉴于数据是二维的，我会有一个2D数组来保存它。
好吧，你可以将它们存储在三个词典中：两个用于行和列的Dictionary对象，以及一个用于文本的Dictionary 。 你必须谨慎地保持所有三个同步。
我不确定我是不是只会选择一个大的二维arrays…
如果它是一个精确的克隆，那么一个由数组支持的CellValue [256]数组列表。 Excel有256列，但行数可增长。
如果可以“动态”添加行和列，则不应将行/列存储为单元格的数字属性，而应存储为行或列对象的引用。
例：
private struct CellValue { private List _column; private List _row; private string text; public List column { get { return _column; } set { if(_column!=null) { _column.Remove(this); } _column = value; _column.Add(this); } } public List row { get { return _row; } set { if(_row!=null) { _row.Remove(this); } _row = value; _row.Add(this); } } } private List> MyRows = new List>; private List> MyColumns = new List>;
每个Row和Column对象都实现为CellValue对象的List。 这些是无序的 – 特定行中单元格的顺序与列索引不对应，反之亦然。
每张工作表都有一个行列表和一列列，按工作表的顺序排列（如上图所示为MyRows和MyColumns）。
这将允许您重新排列和插入新的行和列，而无需循环和更新任何单元格。
删除行应循环遍历行上的单元格，并在删除行本身之前将其从各自的列中删除。 对于列，反之亦然。
要查找特定的Row和Column，找到相应的Row和Column对象，然后找到它们共同包含的CellValue。
例：
public CellValue GetCell(int rowIndex, int colIndex) { List row = MyRows[rowIndex]; List col = MyColumns[colIndex]; return row.Intersect(col)[0]; }
（我对.NET 3.5中的这些扩展方法有点模糊，但这应该在球场上。）
如果我没记错的话，有一篇文章讲述了Visicalc是如何做到的，也许是在80年代早期的Byte杂志上。 我相信这是一种稀疏的arrays。 但是我认为上下左右都有链接，所以任何给定的单元都有一个指向它上面的单元格的指针（不管有多少个单元格），在它下面，在它的左边，并在它的右边。