1

RobertSedwickによるAlgorithsm in C++のマルチリストデータ構造について読んでいます。

多次元行列が疎な場合は、多次元配列ではなくマルチリストを使用して表現することがあります。マトリックスの各値に 1 つのノードを使用し、各次元に 1 つのリンクを使用して、リンクがその次元の次の項目を指すようにすることができます。この配置により、次元の最大インデックスの積から必要なストレージが非ゼロ エントリの数に比例するように減少しますが、多くのアルゴリズムに必要な時間が増加します。

簡単な例で上記のステートメントを理解するために、ご協力をお願いします。

お時間とご協力いただきありがとうございます。

4

1 に答える 1

3

実装例を次に示します。

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

MultiList クラスには、同じ行の次のオブジェクトと同じ列の次のオブジェクトへのポインターがあります。2 次元の MultiList の場合、次のダミー ノードが必要になります。

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

をrow0.next_x指すnull、をcol0.next_y指すnullなど。

に値 '3' を挿入するには(0, 1)、 から開始し、列のダミー ノードに到達するまでroot続けます。次に、そのノードから開始して、いずれかになるまでその子を調べ続けます。next_x1col1

this->next_y == nullまたthis->next_y.y > ycor

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

次に、値を含む新しいノードをそのリストに挿入します。y の代わりに x の対応する行ノードで繰り返します。

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

分析: この実装は、追加する必要があるノードごとにメモリを割り当てるだけであることを考えると、本当にまばらな多次元配列に適しています。つまり、メモリの複雑さは O(n) です。挿入/削除は O(n) です。それらがすべて同じ行または列にある場合、すべての既存のノードを処理する必要がある可能性があるためです。同様の理由で Lookup も O(n) です。

于 2012-08-03T13:17:07.947 に答える