在 C 中使用链表创建稀疏矩阵

Question

我有一个任务是创建两个稀疏矩阵（A 和 B），然后将它们相加到第三个稀疏矩阵 (C) 中。我已经用向量完成了它（接收两个稀疏向量并将它们添加到第三个向量中）所以我决定使用一系列向量来表示矩阵会更容易。将来，我可能需要在没有向量的情况下使用实际矩阵（我什至有一个 psuedo-code 函数将数字插入稀疏矩阵），所以请理解 为什么 我问了所有这些，即使下面的代码有点有效。

因为是矩阵，所以有两个指针数组，分别是行数组和列数组。数组的每个单元格都指向各自的 line/column。如下图：

作为一个稀疏矩阵，其中有零，您会看到那些箭头，因为那些带有零的节点不存在。

为了简化问题，我更喜欢只处理行数组，如图所示，这些行指向每个新行的头部。假设每一行都是一个向量 C（就像我上面说的，我想用一系列向量来表示矩阵）。

这是我构建的所有链表函数的代码：

typedef struct List_node
{
    int key;
    int i,j;
    struct List_node *next;
}List_node;

typedef struct List
{
    List_node *head;
}List;

List *create_list()
{
    List *list = (List*)malloc(sizeof(List));
    list->head = NULL;
    return list;
}

void insert_first(List_node *x, List *list)
{
    x->next = list->head;
    list->head = x;
}

void insert(List_node *x, List_node *y)
{
    x->next = y->next;
    y->next = x;
}

List_node *mk_node(int data, int row, int col)
{
    List_node *node = (List_node *)malloc(sizeof(List_node));
    node->key = data;
    node->i = row + 1;
    node->j = col + 1;
    return node;
}

void delete_list(List *list) 
{
    List_node *node, *temp;
    node = list->head;
    while (node != NULL) 
    {
        temp = node->next;
        free(node);
        node = temp;
    }
    free(list);
}

void print_list(List *list, char name)
{
    List_node *p;
    p = list->head;
    printf("\nThe linked list %c consists of: ",name);
    while (p != NULL)
    {
        printf("%d(i = %d) (j = %d) ", p->key, p->i, p->j);
        p = p->next;
    }
    printf("\n");
}

这是创建向量的代码：

List *Create_vector (List *A, List *B, int i, int m)
{
    int l,flag = 0;
    List *C;
    List_node *node=NULL, *next, *Pointer_A, *Pointer_B;
    C = create_list();
    Pointer_A = A->head;
    Pointer_B = B->head;

    for (l = 0; l<m; l++)
    {
        if ((Pointer_A->key + Pointer_B->key) != 0)
        {
            if (flag == 0)
            {
                node = mk_node(Pointer_A->key + Pointer_B->key, i,l);
                insert_first(node, C);
                flag = 1;
            }
            else
            {
                next = mk_node(Pointer_A->key + Pointer_B->key, i,l);
                insert(next, node);
                node = next;
            }
        }
        Pointer_A = Pointer_A->next;
        Pointer_B = Pointer_B->next;
    }
    return C;
}

这是主程序：

void main()
{
    List_node *Row_A, *Row_B, *Row_C;

    List *A, *B, *C;
    List_node *node, *next;
    int data, m,n,l;
    printf("Enter list row\n");
    scanf("%d", &m);

    Row_A = (List_node*)malloc(sizeof(int)*(m));
    Row_B = (List_node*)malloc(sizeof(int)*(m));
    Row_C = (List_node*)malloc(sizeof(int)*(m));

    printf("Enter list columns\n");
    scanf("%d", &n);

    for (int i=0; i<m; i++)
    {

        A = create_list();
        B = create_list();

        printf("\nInsert first number into A\n");
        scanf("%d", &data);
        node = mk_node(data, i,0);
        insert_first(node, A);
        for (l = 1; l<n; l++)
        {
            printf("Now insert the rest of the numbers\n");
            scanf("%d", &data);
            next = mk_node(data, i,l);
            insert(next, node);
            node = next;
        }
        print_list(A,'A');

        printf("\nInsert first number into B\n");
        scanf("%d", &data);
        node = mk_node(data,i,0);
        insert_first(node, B);
        for (l = 1; l<n; l++)
        {
            printf("Now insert the rest of the numbers\n");
            scanf("%d", &data);
            next = mk_node(data, i,l);
            insert(next, node);
            node = next;
        }
        print_list(B,'B');

        C = Create_vector(A,B,i,n);
    }
    getchar(); getchar();
}

希望你能走到这一步。所以我的问题是：

我不确定如何创建我需要的指针数组，它们是 Row_A、Row_B、Row_C。意思是，如果每个单元格都指向向量的头部——我该如何定义数组？作为列表？列表节点？如何使数组的每个单元格指向每个向量的头部？
每次执行 for 循环时，列表 C 都会被覆盖。我看到可以保留每个向量 C 并将其放入矩阵的唯一方法是使每个数组单元格指向每个向量的头部，这使我们回到问题 #1。真的吗？我该怎么做？

非常感谢。

Answer 1

一些可以帮助您入门的观察结果：

您可以按照创建动态数组的方式创建头像列表 Row_A 等等。这些头部列表不应该是独立的数据结构。它们应该是 Matrix 结构的一部分，就像 head 是 List 结构的一部分一样。头数组的分配应该是它的创建者函数的一部分 create_matrix.
每个Matrix存储自己的头列表也是覆盖C的解决方案：而不是一遍又一遍地分配给C，分配给 C->head[i]。 A 和 B 也是如此。所有描述矩阵的日期都应该封装在一个结构中，这样所有的东西都可以整齐地存储在一起。
目前您将矩阵表示为行列表。这对于打印和矩阵加法来说很好，但是一旦你开始乘法，你还需要列标题。然后，您的节点结构必须准备好具有两个指针，如草图所示：一个用于行中的下一个元素（right，比如说），一个用于列中的下一个元素（below） .
您的矩阵不稀疏。例如，添加两个列表的代码（不应称为 create_vector；选择更具表现力的名称）应检查与节点关联的索引，以便可以跳过零条目。
您应该在结构中存储列表或矩阵的维度。这不是遍历列表所必需的，但它允许快速检查操作是否合法。例如，只能添加相同维度的矩阵。

例如：

typedef struct Matrix Matrix;
typedef struct Matrixnode Matrixnode;

struct Matrix {
    int n, m;
    Matrixnode *row;
    Matrixnode *col;
};

Matrix *create_matrix(int n, int m)
{
    Matrix *mx = malloc(sizeof(*mx));

    mx->n = n;
    mx->m = m;

    mx->row = malloc(m * sizeof(*m->row));
    mx->col = malloc(n * sizeof(*n->col));

    return mx;
}

Matrix *matrix_add(const Matrix *a, const Matrix *b)
{
    assert(a->m == b->m);
    assert(a->n == b->n);

    Matrix *c = create_matrix(a->n, a->m);

    for (int i = 0; i < c->m; i++) {
        c->row[i] = row_add(a->row[i], b->row[i]);
    }

    return c;
}

这是关于如何制作行向量数组的粗略草图。（我创建了一个 col 数组，但没有使用它。添加矩阵时，您还必须注意保持列指针一致。）

在 C 中使用链表创建稀疏矩阵

Creating a sparse matrix using linked lists in C

c

sparse-matrix