假设我正在使用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个任务？
更新：
浏览一些答案，我认为我没有找到自己喜欢的答案。我可以吗：
为了避免同步它们，请勿保留超过2个CellValue副本。在C语言世界中，我会很好地使用指针。
可以动态添加行和列（与Excel不同）。
最佳答案
我会选择一个稀疏数组（链接列表的链接列表），以最小的存储量提供最大的灵活性。
在此示例中，您具有行的链接列表，每个元素都指向该行中单元格的链接列表（可以根据需要反转单元格和行）。
|
V
+-+ +---+ +---+
|1| -> |1.1| ----------> |1.3| -:
+-+ +---+ +---+
|
V
+-+ +---+
|7| ----------> |7.2| -:
+-+ +---+
|
=
每个行元素中都有行号，每个单元格元素都有一个指向其行元素的指针，因此从单元格获取行号为O（1）。
同样，每个单元格元素都有其列号，也使该O（1）。
要获得O（1）来立即查找给定行/列中的单元格，没有简单的方法，但是稀疏数组的获取速度将与它一样快，除非您为每个可能的单元格预先分配信息，以便可以进行索引查找在阵列上-在存储方面会非常浪费。
您可以做的一件事是使一维变为非稀疏状态，例如使列成为主数组（而不是链接列表）并将其限制为1,000个-这将使列查找索引（快速），然后对稀疏进行搜索行。
我认为您不可能因为文本可以在多个单元格中重复（不同于行/列）而获得O（1）来进行文本查找。我仍然相信稀疏数组将是搜索文本的最快方法，除非您在另一个数组中维护所有文本值的排序索引（同样，这样做可以使其速度更快，但会消耗大量内存）。