разреженная матрица с использованием связанного списка Переполнение стека

Я кодирую программу, которая использует связанный список для хранения разреженной матрицы. Сначала я создаю класс «Узел», содержащий индекс записи, значение записи и два указателя на следующую строку и следующий столбец. Во-вторых, я обнаружил в Google, что мне нужно создать класс Matrix, как показано ниже, но я не понимаю смысла Node **rowList а также 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
}

0

Решение

Похоже, это именно то, что говорит комментарий. Это массивы. предположительно rowList будет массив rows элементы и columnList будет массив cols элементы. Причина это Node** является то, что каждый элемент в массиве является 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), вы добавляете этот узел к каждому из rowList а также columnList, т.е.:

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]
}

Теперь вы заканчиваете функцию, и не забудьте выполнить индексацию столбцов …

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]