Разреженная матричная вставка в c - PullRequest
Новая
       9

Разреженная матричная вставка в c

0 голосов
/ 26 января 2012

Я пытаюсь сделать эффективное умножение разреженных матриц. Сейчас я читаю данные в память, и вот как выглядит моя структура данных: 

typedef struct node{
int x;
int y;
int value;
struct node* row;
struct node* col;
}node;

typedef struct matrix{
int height;
int width; 
node** rowList;
node** colList;
}matrix;

Мой текущий код для вставки: 

void insert(matrix** M, int row_index, int col_index, int value)
{
    node* currNode=(node*)malloc(sizeof(node));
    currNode->x=row_index;
    currNode->y=col_index;
    currNode->value=value;

    if ((*M)->rowList[row_index] == NULL) { /* index is empty */
        currNode->row = NULL;
        (*M)->rowList[row_index] = currNode;
    }
    else if ((*M)->rowList[row_index]->y > col_index) { /* insert node to front */
        //printf("%d, %d\n", (*M)->rowList[row_index]->y, col_index);
        currNode->col = (*M)->rowList[row_index];
        (*M)->rowList[row_index] = currNode;
    }
    else if ((*M)->rowList[row_index]->y < col_index) { /* insert node to front */  
        node* rowptr = (node*)malloc(sizeof(node));
        rowptr = (*M)->rowList[row_index];
        while(rowptr->col!=NULL&&rowptr->col->y < col_index)
            rowptr=rowptr->col;

        currNode->col=rowptr->col;
        rowptr->col=currNode;
        //printf("-----------------%d\n", rowptr->y);
    }

    if ((*M)->colList[col_index] == NULL) { 
        currNode->col = NULL;
        (*M)->colList[col_index] = currNode;
    }
    else
    if ((*M)->colList[col_index]->x > row_index) { 
        //printf("%d, %d\n", (*M)->colList[col_index]->x, row_index);
        currNode->row = (*M)->colList[col_index];
        (*M)->colList[col_index] = currNode;
    }
}

Если вы спросите, это моя функция печати: 

void print_matrix(matrix *M){
    for(int i=0;i<M->height;i++){
        while(M->rowList[i]!=NULL){
            printf("i=%d, j=%d, v=%d\n",M->rowList[i]->x, M->rowList[i]->y,
                   M->rowList[i]->value);
            M->rowList[i]=M->rowList[i]->col;
        }
    }
}

Для этого ввода: 

5,5
0,0,1
0,1,2
0,3,3
0,4,4

где (5,5) размеры матрицы и (0,0,1) = i, j, значение, я получаю это: 

i=0, j=0, v=1
i=0, j=1, v=2
i=0, j=3, v=3
i=0, j=4, v=4
i=0, j=4, v=4

Для этого ввода: 

5,5
0,0,1
0,1,2
0,3,3
0,4,4
0,2,5

Я понял: 

i=0, j=0, v=1
i=0, j=1, v=2
i=0, j=2, v=5
i=0, j=2, v=5

Я думаю, что проблема здесь: 

else if ((*M)->rowList[row_index]->y < col_index) {
    node* rowptr = (node*)malloc(sizeof(node));
    rowptr = (*M)->rowList[row_index];
    while(rowptr->col!=NULL&&rowptr->col->y < col_index)
        rowptr=rowptr->col;

        currNode->col=rowptr->col;
        rowptr->col=currNode;
    }
    [ ... ]

Каким-то образом я удаляю одно из значений, когда добавляю новый элемент меньшего размера.

Вопрос: как я могу получить этот код для загрузки значений моей разреженной матрицы в память, используя правильно предоставленную структуру данных?

Спасибо ^^

1 Ответ

1 голос
/ 28 января 2012

Здесь: 

if ((*M)->colList[col_index] == NULL) {
    currNode->col = NULL;
    (*M)->colList[col_index] = currNode;
}

там, где вы пишете currNode->col, вы должны были написать currNode->row.После внесения этого изменения вывод корректен для второго входного файла.

Просматривая код, я заметил другие странные вещи;например, функция print_matrix также уничтожает цепочки указателей matrix -> col.Кроме того, в этих двух строках 

    node* rowptr = (node*)malloc(sizeof(node));
    rowptr = (*M)->rowList[row_index];

вы выделяете память, а затем немедленно перезаписываете указатель на нее.

...