c - c 中的稀疏矩阵插入

Question

我正在尝试进行有效的稀疏矩阵乘法。现在我正在将数据读入内存，这就是我的数据结构:

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,value，我得到:

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;
    }
    [ ... ]

当我添加一个较小的新元素时，我会以某种方式删除其中一个值。

问题是:如何使用正确提供的数据结构让此代码将稀疏矩阵值加载到内存中？

谢谢^^

Answer 1

这里:

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

您正在分配内存，然后立即覆盖指向它的指针。