Проблема при вставке в разреженную матрицу

Question

Мне нужно реализовать матричную структуру данных CSR в C ++ с использованием 3 динамических c массивов (индексация начинается с 0), и я застрял. Поэтому я должен реализовать 2 функции:

1) modify(int i, int j, TElem e) - изменяет значение (i, j) на e или добавляет значение if (если оно не существует) или удаляет его, если e равно null.

2) element(int i, int j) const - возвращает значение, найденное для (i, j)

Я хотел проверить свой код следующим образом:

Matrix m(10, 10);
    for (int j = 0; j < m.nrColumns(); j++) {
        m.modify(4, j, 3);
    }                                                             
    for (int i = 0; i < m.nrLines(); i++)
        for (int j = 0; j < m.nrColumns(); j++)
            if (i == 4)
                assert(m.element(i, j) == 3);
            else
                assert(m.element(i, j) == NULL_TELEM);

И я получил удивительно видеть, что m.element (4, j) будет 0 для j в диапазоне (0,8) и только 3 для j = 9.

Это моя реализация элемента (int i, int j):

    int currCol;
    for (int pos = this->lines[i]; pos < this->lines[i+1]; pos++) {
        currCol = this->columns[pos];
        if (currCol == j)
            return this->values[pos];
        else if (currCol > j)
            break;
    }
    return NULL_TELEM;

Конструктор выглядит следующим образом:

Matrix::Matrix(int nrLines, int nrCols) {
    if (nrLines <= 0 || nrCols <= 0)
        throw exception();
    this->nr_lines = nrLines;
    this->nr_columns = nrCols;
    this->values = new TElem[1000];
    this->values_capacity = 1;
    this->values_size = 0; 
    this->lines = new int[nrLines + 1];
    this->columns = new TElem[1000];
    this->columns_capacity = 1;
    this->columns_size = 0; 
    for (int i = 0; i <= nrLines; i++)
        this->lines[i] = NULL_TELEM;
}

Это метод «изменения»:

TElem Matrix::modify(int i, int j, TElem e) {
    if (i < 0 || j < 0 || i >= this->nr_lines || j >= nr_columns)
        throw exception();
    int pos = this->lines[i];
    int currCol = 0;
    for (; pos < this->lines[i + 1]; i++) {
        currCol = this->columns[pos];
        if (currCol >= j)
            break;
    }
    if (currCol != j) {
        if (!(e == 0)) 
            add(pos, i, j, e);
    }
    else if (e == 0)
        remove(pos, i);
    else
        this->values[pos] = e;
    return NULL_TELEM;
}

И это вставка Метод:

void Matrix::add(int index, int line, int column, TElem value)
{
    this->columns_size++;
    this->values_size++;
    for (int i = this->columns_size; i >= index + 1; i--) {
        this->columns[i] = this->columns[i - 1];
        this->values[i] = this->values[i - 1];
    }
    this->columns[index] = column;
    this->values[index] = value;
    for (int i = line + 1; i <= this->nr_lines; i++)
        this->lines[i]++;
}

Может кто-нибудь помочь мне, пожалуйста? Я не могу понять, почему это происходит, и мне действительно нужно завершить эту реализацию в наши дни. Довольно странно, что эти позиции имеют значение 0.

Итак, после следующего теста, который начинается следующим образом, я получаю нарушение доступа к памяти:

Matrix m(200, 300);
    for (int i = m.nrLines() / 2; i < m.nrLines(); i++) {
        for (int j = 0; j <= m.nrColumns() / 2; j++)
        {
            int v1 = j;
            int v2 = m.nrColumns() - v1 - 1;
            if (i % 2 == 0 && v1 % 2 == 0)
                m.modify(i, v1, i * v1);
            else
                if (v1 % 3 == 0)
                    m.modify(i, v1, i + v1);
            if (i % 2 == 0 && v2 % 2 == 0)
                m.modify(i, v2, i * v2);
            else
                if (v2 % 3 == 0)
                    m.modify(i, v2, i + v2);
        }

Ошибка брошенный в методе "modify" в currCol = this-> column [pos];

И если я загляну в отладчик, он будет выглядеть так: i = 168, lines [i] = - 842150451, lines [i +1] = 10180, pos = -842150451.

У кого-нибудь есть идеи, почему так выглядит?

Answer 1

В вашем коде есть две небольшие ошибки.

Когда вы пытаетесь найти позицию вставки в modify, вы l oop над непустыми элементами в строке:

int currCol = 0;

for (; pos < this->lines[i + 1]; i++) {
    currCol = this->columns[pos];
    if (currCol >= j)
        break;
}

Здесь вы должны обновлять pos++ в каждой итерации вместо i++.

Вторая ошибка возникает при вставке элемента в столбец 0. currCol будет нулем, но ваше условие для добавления нового элемента

if (currCol != j) {
    if (!(e == 0)) 
        add(pos, i, j, e);
}

Но j также равен нулю, поэтому ничего не будет вставлено. Это можно исправить, начав с несуществующего столбца:

int currCol = -1;