c++ - 什么是“正交链表”？

Question

我了解链表是什么，但我的问题是什么是正交链表？我在网上搜索，但找不到任何有用的信息。我正在研究C++中的like list，如果有任何与链表相关的好书，请提及。

Answer 1

这不是一个很常见的术语，但根据计算词典，它是一个多维链表，其元素包含指向每个维度中邻居的指针。

取一个简单的矩阵：

1 2 3 
4 5 6
7 8 9

然后，元素 5 将有一个指向 4 和 6 的指针，但也有指向 2 和 8 的指针。

以下问题可能对 C++ 书籍有所帮助：

• The Definitive C++ Book Guide and List
• https://stackoverflow.com/questions/74405/what-is-the-best-c-book-for-an-intermediate-to-expert-developer

Answer 2

正交链表是行表和列表的组合。所以你可以用它来表示一个二维数组（因为它也有行和列）

在计算机科学中，我们一般用它来表示稀疏矩阵，从而降低大矩阵乘法的复杂度。

第一个链表由非零行组成，每个节点指向其右侧和底部的非零元素。

typedef struct Orthogonal_linked_list_node
{
    float some_data;
    int row;
    int column;
    struct _matrix_element *next_row;
    struct _matrix_element *next_column;
}matrixNode;