Creating a sparse matrix using linked lists in C

Question

I have an assignment which is to create two sparse matrices (A and B) and then adding them up into a third sparse matrix (C). I have already done it with vectors (receiving two sparse vectors and adding them into a third) so I decided it would be easier to use a series of vectors to represent a matrix. In the future, I may need to do it without vectors but with an actual matrix (I even have a psuedo-code of a function that inserts a number into a sparse matrix), so do understand why I'm asking all of this, even though the following code somewhat works.

Because it is a matrix, it has two arrays of pointers that are the row array and column array. each cell of the array is pointing to the respective line/column. It is as in the picture below:

Being a sparse matrix, where there are zeroes, you see those arrows as those nodes that have zeroes with them do not exist.

To simplfy the problem, I prefer to only address the array of rows, which, as seen in the image, are pointing to the heads of each new row. Assume each line is a vector C (like I said above, I want to represent the matrix with a series of vectors).

This is the code of all of the linked list functions I built:

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");
}

This is the code that creates the vectors:

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

And this is the main program:

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();
}

Hopefully you got this far. So my problems are:

1. I'm not sure how to create the array of pointers that I need, which are Row_A, Row_B, Row_C. Meaning, if each cell is pointing into the head of a vector - how do I define the arrays? As list? List node? How do I make every cell of the array to point to each vector's head?

2. List C is overriden every time the for loop is executed. The only way I see that can keep each vector C and put it in a matrix is to make each array cell point to each vector's head, which brings us back to problem #1. Is that true? How can I do this?

Thank you very much.

Answer 1

Some observations that may get you started:

• You create list of heads just the way you create your dynamic arrays Row_A and so on. These lists of heads should not be standalone data structures. They should be part of a Matrix struct, just as head is part of your List struct. The allocation of the head array should be part of its creator function create_matrix.

• The fact that each Matrix stores its own list of heads is also the solution to overwriting C: Instead to assign to C over and over, assign to C->head[i]. Likewise for A and B. All date that describes the matrix should be encapsulated in one struct, so that everything is stored neatly together.

• At the moment you represent your matrix as a list of rows. That's fine for printing and for matrix addition, but once you get to multiplication, you will also need column heads. Your node structure must then be prepared to have two pointers as illustrated in the sketch: One for the next element in the row (right, say) and one for the next element in the columns (below).

• Your matrices are not sparse. For example, your code to add two lists (which shouldn't be called create_vector; chose something more expressive) should check the index associated with the nodes so that zero entries can be skipped.

• You should store the dimension of a list or matrix in the struct. This is not needed in order to traverse the list, but it allows to check quickly whether an operation is legal. For example, you can only add matrices of the same dimension.

For example:

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

This is a rough sketch of how you can make the row vectors arrays. (I've created a col array, but don't use it. When adding matrices, you'd have to take care of keeping the column pointers consistent, too.)