多列表數據結構在C++中的應用

Question

我正在閱讀RobertSedwick在C++算法中的多列表數據結構。

如果一個多維矩陣是稀疏的，那麼我們可能會使用多重表 而不是一個多維數組來代表它。我們可以爲矩陣中的每個值使用一個 節點，每個維度使用一個鏈接 ，鏈接指向該維度中的下一項。這 安排減少從dimenstions的 最大指數的乘積成比例的 非零條目數所需的存儲空間，但增加所需的很多算法

懇請您的幫助，上面的語句理解的時間以簡單的例子。

在此先感謝您的時間和幫助。

Answer 1

下面是一個示例實現：

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

的多重表類有指向同一行中的下一個對象，並且在同一列中的下一個對象。對於2維多重表，你會需要以下虛擬節點：

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）。