c++ - multilist数据结构在C++中的应用

Question

我正在阅读 RobertSedwick 的 Algorithsm in C++ 中有关多列表数据结构的内容。

If a multidimensional matrix is sparse, then we might use a multilist rather than a multidimensional array to represent it. We could use one node for each value in the matrix and one link for each dimension, with the link pointing to next item in that dimension. This arrangement reduces the storage required from the product of the maximum indices in the dimenstions to be proportional to the number of nonzero entries but increases the time required for many algorithms

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

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

Answer 1

这是一个示例实现:

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，等等

要在 (0, 1) 处插入值“3”，您从 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)。