c++ - 多列表数据结构在C++中的应用

Question

我正在阅读 RobertSedwick 的 C++ 算法中的多列表数据结构。

如果多维矩阵是稀疏的，那么我们可以使用多列表而不是多维数组来表示它。我们可以为矩阵中的每个值使用一个节点，为每个维度使用一个链接，链接指向该维度中的下一项。这种安排减少了从维度中最大索引的乘积到与非零条目的数量成正比所需的存储空间，但增加了许多算法所需的时间

请通过简单的示例请求您帮助理解上述陈述。

提前感谢您的时间和帮助。

score 3 · Accepted Answer

这是一个示例实现：

class MultiList
{
    public:
        int value, x, y;
        MultiList *next_x, *next_y;
        void add( int xcor, int ycor, int val );
}

MultiList 类具有指向同一行中的下一个对象和同一列中的下一个对象的指针。对于二维 MultiList，您需要以下虚拟节点：

root -> col0 -> col1
  |
  V
row0
  |
  V
row1

用row0.next_x指向null、col0.next_y指向null等。

要在处插入值 '3' (0, 1)，请从处开始root，并继续前进，next_x直到到达1列虚拟节点col1。然后从该节点开始，继续查看其子节点，直到

this->next_y == null或者this->next_y.y > ycor

root -> col0 -> col1
  |               |
  V               V
row0              3
  |
  V
row1

然后，您将带有您的值的新节点插入到该列表中。您使用 x 中的相应行节点而不是 y 重复。

root -> col0 -> col1
  |               |
  V               V
row0      ->      3
  |
  V
row1

分析：这个实现非常适合真正稀疏的多维数组，考虑到您只为需要添加的每个节点分配内存，这意味着内存复杂度为 O(n)。插入/删除是 O(n)，因为如果它们都在同一行或同一列中，您可能必须遍历每个现有节点。出于类似的原因，查找也是 O(n)。

1 回答 1