data-structures - 如何实现一个高效的类 excel 应用程序

Question

我需要实现一个高效的类似 excel 的应用程序。我正在寻找一种数据结构，它将：

• 以有效的方式存储数据（例如 - 我不想为未使用的单元预分配内存）。
• 当用户更改其中一个单元格中的公式时允许有效更新

有任何想法吗？

谢谢，李

Answer 1

在这种情况下，您正在寻找一个在线词典结构。这是一类结构，可让您将一小部分数据（在本例中为表示单元格的坐标）与另一部分（在本例中为单元格内容或公式）相关联。“在线”形容词意味着可以实时添加、删除或更改字典条目。

有很多这样的结构。举一些更常见的例子：哈希表、二叉树、跳过列表、链表，甚至数组中的列表。

当然，其中一些比其他更有效（取决于实现和条目的数量）。通常我使用哈希表来解决这类问题。

但是，如果您需要进行范围查询“修改此范围内的所有单元格”，则使用二叉树或更复杂的空间结构可能会更好——但考虑到问题的简单要求，这不太可能。