'Sparse Matrix' and Data Structures

Hi everyone, thanks in advance for taking the time to read and respond to this post. To be clear this is part of a University course I am doing so I'm not looking to cheat or 'blag' the answers from others! Quite simply we have no support or guidance and I'm a fairly novice programmer so I was hoping to post the question here where some of the more experienced programmers may offer some advice or guidance.

Quote:

---

An unstructured sparse matrix is simply a matrix where a significant number of elements are zero.
Using a suitable in-memory data structure that stores only non-zero elements, it is possible to
represent such a matrix in a much more compact way than a dense equivalent (where all elements
are stored whether zero or not).

1. Implement a data structure that can represent a sparse matrix. It is essential that the data
structure is space efficient since your solution will be tested with matrices whose
dimensions are many orders of magnitude larger than those provided.
2. Implement functions that enable an in-memory instance of the sparse matrix data structure
to be read from or written to an on-disk file as per the format above.

---

One example given is:

Quote:

---

5,5
0,0,-1
0,4,2
1,1,5
1,3,6
2,2,7
3,1,8
3,3,9
4,0,3
4,4,-4
represents a (5 x 5)-element matrix M =
-1 0 0 0 2
0 5 0 6 0
0 0 7 0 0
0 8 0 9 0
3 0 0 0 -4

---

Although It does not suggest this is the best or preferable way forward.

I'm not particularly well versed on data structures but I remember sorting data and writing it to a linked list by building it node by node last year and I'm wondering if a linked list could be a useful data structure to start with??

This is just Part of stage 1 and there are 5 stages. Later on I will have to compute the sum, product etc.. I thought this might be important to bring up in case this affects my choice of data structure.

Furthermore:

Quote:

---

Although there may be multiple valid approaches at each stage, your solution should aim to be as efficient as possible
wrt. execution time. Within reason, a trade-off favouring time over space is encouraged.

---

Thanks again - as you can probably tell I'm a little lost.

Quote:

---

I'm wondering if a linked list could be a useful data structure to start with??

---

That is a useful data structure to start with. Think of a matrix as a list of columns or rows, and columns or rows as lists of elements. If each element knows it's position and any missing element is assumed to be 0 - you can store any matrix with a minimum number of elements. You just need to think about how you would populate this matrix from their format and how to do things like products.

Using a direct conversion of the "list" approach, you might represent this conveniently using structs

Code:

---

typedef struct {
    int row;
    int col;
    int val;
} SMEntry;

typedef struct {
    int rows;
    int cols;
    SMEntry x[10000];
} SparseMatrix;

---

Then you can create a SparseMatrix with arbtirary number of rows and columns and up to 9999 nonzero entries (saving one array slot for an end-marker).

Example to initialize the example you gave from above:

Code:

---

SparseMatrix m = {
    5, 5,
    {
        (SMEntry){0, 0, -1},
        (SMEntry){0, 4, 2},
        (SMEntry){1, 1, 5},
        (SMEntry){1, 3, 6},
        (SMEntry){2, 2, 7},
        (SMEntry){3, 1, 8},
        (SMEntry){3, 3, 9},
        (SMEntry){4, 0, 3},
        (SMEntry){4, 4, -4},
        (SMEntry){-1,-1,-1}  // end marker   
    }
};

---

Then I would define the functions that you want to use to access your data structure. You need to at least create a sparse matrix, read it from a file, write it to a file, and most likely to print it out in normal matrix format (maybe its not required explicitly but its basically required for debugging)

Fantastic thanks for your help! I'll get cracking on trying to implement this tomorrow and let you know how I get on - I'm sure there will be some stumbling blocks along the way!
Cheers