Thread: Adding Two 2D-Sparse Matrix using Data Structures in C

  1. #1
    Registered User
    Join Date
    Aug 2016
    Posts
    3

    Lightbulb Adding Two 2D-Sparse Matrix using Data Structures in C

    Hey guys, I am new to data structures using C. I have been told to add two 2D arrays. I have taken the Row, Column and Value input of the non zero values from the user for the two sparse matrix and stored them dynamically in the memory pointed by the integer pointer 'a'(for the first one) and 'b'(for the second one). The problem I am facing is how do I add both these matrix and store them in another memory location pointed by 'c'. I want to do this operation without creating any kind of 2D array if possible(using linear memory location). Here is the code I created so far for taking input of the Row, Col and Non-Zero values of the two sparse matrix from the user and print the 2D sparse matrix from it:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    int main() {
        int *a, *b, *c, row, col, val1, val2, ind1 = 0, ind2 = 0, ind3 = 0, ri1, ci1, ri2, ci2, count = 0;
        printf("Please Enter The Rows In Sparse Matrix: ");
        scanf("%d", &row);
        printf("Please Enter The Cols In Sparse Matrix: ");
        scanf("%d", &col);
        printf("Please Enter The No. Of Non Zero Elements In First Matrix: ");
        scanf("%d", &val1);
        printf("Please Enter The No. Of Non Zero Elements In Second Matrix: ");
        scanf("%d", &val2);
        
        a = (int *)malloc(sizeof(int)*(val1+1)*3);
        a[ind1++] = row;                    //store the total number of rows in actual matrix at a[o]
        a[ind1++] = col;                    //store the total number of cols in actual matrix at a[1]
        a[ind1++] = val1;                    //store the total number of non-zero values in actual matrix at a[2]
        
        printf("Please Enter The Data For First Sparse Matrix: \n");
        for(int i = 1; i <= val1; i++) {
            printf("Enter Row %d: ", i);
            scanf("%d", &a[ind1++]);
            printf("Enter Col %d: ", i);
            scanf("%d", &a[ind1++]);
            printf("Enter Value %d: ", i);
            scanf("%d", &a[ind1++]);
        }
        
        ind1 = 0;
        b = (int *)malloc(sizeof(int)*(val2+1)*3);
        b[ind1++] = row;                    //store the total number of rows in actual matrix at b[o]
        b[ind1++] = col;                    //store the total number of cols in actual matrix at b[1]
        b[ind1++] = val2;                    //store the total number of non-zero values in actual matrix at b[2]
        
        printf("Please Enter The Data For Second Sparse Matrix: \n");
        for(int i = 1; i <= val2; i++) {
            printf("Enter Row %d: ", i);
            scanf("%d", &b[ind1++]);
            printf("Enter Col %d: ", i);
            scanf("%d", &b[ind1++]);
            printf("Enter Value %d: ", i);
            scanf("%d", &b[ind1++]);
        }
        
        printf("The Entered Elements Of Matrix 1 Are: \n");
        for(int i = 0; i < (val1+1)*3; i++)
            printf("%d \t", a[i]);
        
        printf("The Entered Elements Of Matrix 2 Are: \n");
        for(int i = 0; i < (val2+1)*3; i++)
            printf("%d \t", b[i]);
    }
    Any help will be appreciated..

  2. #2
    Registered User
    Join Date
    May 2012
    Posts
    505
    The important thing is your data structures.
    There are several ways of representing a sparse matrix. An obvious one is
    to create a little structure row, column, and value, then store the sparse
    matrix as an array of those structures. It's important to keep sorted, because
    duplicates row/columns aren't allowed. You also need width and height.

    So set up those data structures. To make things easy, let's say everything
    must be in dynamic memory. So both the SPARSEMATRIX and the list
    of entries are allocated with malloc, and are always passed about as pointers.

    Now let's write some functions

    /* create a sparse matrix, all entries zero */
    SPARSEMATRIX *create_sparsematrix(int width, int height)

    /* destroy a sparse matrix, free all memory */
    void destroy_spraematrix(SPARSEMATRIX *sm);

    /* insert a non-zero (presumably) entry */
    int sparsematrix_insertentry(SPAREMATRIX *sm, int row, int column, double value);

    /* access the sparse matrix like a regular matrix - most entries will be 0 */
    double sparematrix_getvalue(SPARSEMATRIX *sm, int row, int column);

    /* add src to dest */
    int sparsematrix_add(SPARESMATRIX *dest, SPARSEMATRIX *src)

    The last is the function you want. Get the rest working first - you'll need
    it to set up your tests.
    How do we add? Go through the second matrix. For each entry, do a binary
    search on the first matrix. If you find a corresponding entry, add the values,
    if you don't, append. Then finally sort the destination matrix to maintain
    the "sorted" criterion.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 01-06-2016, 01:15 AM
  2. 'Sparse Matrix' and Data Structures
    By uniprog in forum C Programming
    Replies: 3
    Last Post: 12-12-2012, 11:56 AM
  3. adjacency matrix and sparse matrix
    By dpp in forum C Programming
    Replies: 3
    Last Post: 07-11-2010, 10:26 AM
  4. adding sparse matrices
    By budala in forum C Programming
    Replies: 2
    Last Post: 08-21-2009, 09:52 AM
  5. Sparse Matrix
    By brb9412 in forum C Programming
    Replies: 3
    Last Post: 01-02-2009, 01:12 PM

Tags for this Thread