0

リンクリストを使用して疎行列を格納するプログラムをコーディングしています。最初に、エントリのインデックス、エントリの値、および次の行と次の列への 2 つのポインターを含むクラス「ノード」を作成します。Node **rowList次に、以下のコードのようにクラス Matrix を作成する必要があることを Google で見つけましたが、 andの意味がわかりませんnode** columnList。なぜ彼らはそこでポインターへのポインターを使用し、そこからマトリックスをどのように実装できますか? どうもありがとう。

class Node
{
public:
    int iValue, jValue;
    float value;
    Node *rowPtr;
    Node *colPtr;
};

class Matrix
{
    Node **rowList;     // rowList is the pointer to the array of rows
    Node **columnList;  // columnList is the pointer to the array of columns
    int rows, cols;     // number of rows and columns
}
4

1 に答える 1

2

まさにコメントの通りのようです。それらは配列です。おそらく要素rowListの配列になり、要素の配列になります。である理由は、配列内の各項目が. 配列へのポインターには、常に余分なレベルの間接化 (余分な) があります。つまり、その配列から単一の要素にインデックスを付けると、型の値が再び取得されます。rowscolumnListcolsNode**Node**Node*

配列は次のように作成されます。

rowList = new Node* [rows];
columnList = new Node* [cols];

// Don't forget to initialise the values to NULL!  Here's the dull way:
for( int i = 0; i < rows; i++ ) rowList[i] = NULL;
for( int i = 0; i < cols; i++ ) columnList[i] = NULL;

それらを削除する必要がある場合 (のデストラクタでMatrix):

delete [] rowList;
delete [] colList;

そこからマトリックスを実装する方法に関する質問については、それは本当にあなた次第です。おそらく、位置 にノードを作成するときに、そのノードをおよび(i, j)のそれぞれに追加します。 すなわち：rowListcolumnList

Node * node = new Node(i, j, 123.0);
rowList[i] = node;
columnList[j] = node;

しかし、ノードは明らかに行リストと列リストの両方にリンクする必要があるため、それほど単純ではありません。非常に基本的なレベルで、提供された構造を使用すると、次のような方法があります。

// Inserts newNode at the head of the list and modifies the head pointer.
void insert_row( Node* & r, Node *newNode )
{
    newNode->rowPtr = r;
    if( r != NULL ) r->rowPtr = newNode;
    r = newNode;
}

// Similarly with insert_col()...

上記を元の例で使用すると、次のようになります。

Node * node = new Node(i, j, 123.0);
insert_row( rowList[i], node );
insert_col( columnList[j], node );

オーダーインサートの場合

あなたはすでにコードを持っているので、私はそれを提供します。しかし、それでも自分でいくつかの作業を行う必要があります。

私は概念を理解しようとしていますが、それは私にとってとても混乱しています。

まず、物事をきれいにしましょう。これはクラスであり、C++ を使用しているため、C++ の知識を使用してください。

class Node
{
public:
    Node( int i, int j, int val );

    void InsertRowAfter( Node* node );
    void InsertColAfter( Node* node );

    int iValue, jValue;  // Row and column index, 1-based
    float value;         // Element value
    Node *rowPtr;        // Next element in this row (sorted by jValue)
    Node *colPtr;        // Next element in this column (sorted by iValue)
};

Node::Node( int i, int j, int val )
    : iValue(i)
    , jValue(j)
    , value(val)
    , rowPtr(NULL)
    , colPtr(NULL)
{}

// Inserts the given node to follow this node in the row list
void Node::InsertRowAfter( Node* node )
{
    // [go on, you do it]
}

// Inserts the given node to follow this node in the column list
void Node::InsertColAfter( Node* node );
{
    // [go on, you do it]
}

したがって、Matrix::inputData関数を実装する必要があります...基本的に、友人がしようとしていたことを実行しますが、エラーやメモリリークは発生しません。つまり、次のように開始します。

// Use 'horz' and 'vert' to search through the row and column lists.  If a
// node needs to be created, it will be stored in 'node'.
Node *horz = rowList[iValue - 1];
Node *vert = columnList[jValue - 1];
Node *node;

// If there is no row list or smallest jValue, insert at the head.
// Otherwise, search for an insert point.
if( !horz || horz->jValue > jValue )
{
    // [go on, you do it]
}
else
{
    // Move 'horz' pointer to position at which we will append a node.
    Node *next = horz->rowPtr;
    while( next && next->jValue <= jValue ) {
        horz = next;
        next = next->rowPtr;
    }

    // If replacing an existing value, there's nothing else to do.
    if( horz->jValue == jValue ) {
        horz->value = value;
        return;
    }

    // Otherwise append a new node.
    // [go on, you do it]
}

これで、関数を終了し、列のインデックス付けを行うことを忘れないでください...

于 2012-09-25T02:31:13.793 に答える