3

我们的团队正在致力于实现移动平台的表格小部件（其中一个应用程序是移动办公，如 MS Excel）。

我们需要优化存储表数据的数据结构（使用简单的二维数组）。

您能否建议存储表数据的最佳数据结构。以下是对数据结构的一些要求：

  • 表格的大小可以最大为 2^32 x 2^32；
  • 大多数表格单元格是空的（即表格是稀疏的），因此最好不要为空单元格存储数据；
  • 数据结构的接口应该支持插入/删除行和列；
  • 数据结构应该允许向前和向后遍历非空单元格；
  • 可以合并表格的单元格（即一个单元格可以跨越多于一行和/或一列）。
4

2 回答 2

2

在更多地考虑了行/列插入/删除的问题之后，我想出了一些看起来很有希望的东西。

首先，创建并维护 2 个已排序的数据结构（例如搜索树），其中包含所有水平和所有具有至少一个非空单元格的垂直索引。

对于此表：

 ABCDE
1
2*
3 %  #
4
5   $

你会有：

  1. A,B,D,E - 使用的水平索引
  2. 2,3,5 - 使用的垂直索引

将这些 A、B、D、E、2、3、5 索引值存储在上述 2 个结构中的某种节点内，这样您就可以知道节点在内存中的地址将某些东西链接到它（同样，树节点非常适合）。

在每个单元格（非空）中，都有一对指向索引节点的链接描述其位置（我使用 & 来表示对节点的链接/引用）：

  • *: &2,&A
  • %: &3,&B
  • #: &3,&E
  • $: &5,&D

这足以定义一个表。

现在，我们如何处理行/列插入？我们将新的行/列索引插入到相应的（水平或垂直）索引数据结构中，并在其之后更新索引值（=向右或向下）。然后我们为这个新的行/列（如果有的话）添加新的单元格，并将它们链接到适当的索引节点。

例如，让我们在第 3 行和第 4 行之间插入一行，并在 4C 处添加一个带有 @ 的单元格（在新行中）：

 ABCDE
1
2*
3 %  #
4  @   <- new row 4
5      <- used to be row 4
6   $  <- used to be row 5

您的索引结构现在是：

  1. A,B,C(new),D,E - 使用的水平索引
  2. 2,3,4（新），6（以前是 5） - 使用的垂直索引

单元格现在链接到索引节点，如下所示：

  • *: &2,&A - 和之前一样
  • %: &3,&B - 和之前一样
  • #: &3,&E - 和以前一样
  • @: &4,&C - 链接到新索引节点 4 和 C 的新单元格
  • $: &6,&D - 曾经是 &5,&D

但是看看 $ 单元格。它仍然指向与以前相同的两个物理节点，只是垂直/行节点现在包含索引 6 而不是索引 5。

如果 $ 单元格下方有 100 个单元格节点，例如只占用 5 个非空行，则您只需要更新行/垂直索引数据结构中的 5 个索引，而不是 100 个。

您可以以类似的方式删除行和列。

现在，为了使这一切变得有用，您还需要能够通过其坐标定位每个单元格。

为此，您可以创建另一个排序的数据结构（同样，可能是搜索树），其中每个键是索引节点地址的组合，值是单元格数据的位置（或单元格数据本身）。

这样，如果您想到达单元格 3B，您可以在索引数据结构中找到 3 和 B 的节点，获取它们的地址 &3 和 &B，将它们组合成 &3*2 32 +&B 并将其用作定位的键我刚刚定义的第三个数据结构中的 % 单元格。（注意：2 32实际上是 2位指针大小，可能因系统而异。）

无论其他单元格发生什么情况，% 单元格链接中的地址 &3 和 &B 将保持不变，即使 % 单元格的索引从 3B 更改为其他值。

您可以轻松地在此基础上开发迭代。

合并应该也是可行的，但我没有关注它。

于 2012-10-24T11:14:58.570 回答
0

我建议像在 excel 中一样存储键值对。例如，想想您的 excel 文档有列 A - AA 等...和第 1 - 256000 行...等所以只需将具有日期的值存储在某种类型的键值对中。

例如：

someKeyValueStore = new KeyValueStore();

someData = new Cell(A1,"SomeValue");

someOtherData = new Cell(C2,"SomeOtherValue");

someKeyValueStore.AddKeyValuePair(someData);
someKeyValueStore.AddKeyValuePair(someOtherData);

在这种情况下，您根本不必关心空单元格。您只能访问那些不为空的。当然，您可能希望跟踪集合中的键，以便您可以轻松查看是否具有特定键的值。但这本质上是处理它的最简单方法。

于 2012-10-24T08:25:58.130 回答