Matrix Data Assignment

• 03-01-2011, 02:59 AM
sehudson
Matrix Data Assignment
I need some help getting started with my homework assignment:

Implement a matrix abstract data type which does not allocate memory for 0valued entries. This is usefufor sparse matrices, which has a lot of 0 values. Use linked lists to implement the matrix class.

I'm guessing the first thing I need to do create a Matrix class, and in my constructor, I should create a singlyLinkedList arry ? i.e

Code:

```public class Matrix{ public Matrix{ LinkedListArray L = new LinkedListArray(); } }```
• 03-01-2011, 03:08 AM
You could use a linked list. The problem with that is that access time is linear. When I made one for a compiler (though, it was immutable which might make a difference to you) I created the sparse matrix using a sorted 2d array. Lookup was improved with a binary search, and elements were stored in the second dimension. You could also use a linked list structure that has a HashMap as a front end - this might be the best idea. That way lookups and insertions are constant time, the object mapped to the key could be a list of some sort.
• 03-01-2011, 03:14 AM
sehudson
• 03-01-2011, 04:44 AM
Is your sparse matrix an actual matrix (i.e. a 2d array?) or is it a sparse list?
• 03-01-2011, 05:49 AM
sehudson
well the idea is to read in a file in the format:

0 0 0 0
0 1 0 0
1 1 0 0
0 2 0 0

My approach was going to be to create a Matrix class, and in my constructor I was going to do something like "CreateLinkedListArray" and basically break up the file into a linked list array. I think I have it done, Ill post my code soon....ran into a snag though, I'm getting a null pointer on the CreateLinkedListArray;
Its saying "overridable method called in the constructor" what does that mean, maybe thats a clue.

Code:

```package matrixapplication; import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.util.LinkedList; public class Matrix{     public int Lines = 0;     public int Cols;     private LinkedList[] myLinkedListArray; public Matrix(){ CreateLinkedListArray(); myLinkedListArray = new LinkedList[getCols()];     } public int getCols(){     return Cols; } //Returns the value of the selected Node for a given ListArray Position and Node. public int getValAt(int ListPos, int Node){ String valPos = (String)myLinkedListArray[ListPos].get(Node); String[] tempStr = valPos.split(" "); int Value = Integer.parseInt(tempStr[1]); return Value;     } public void CreateLinkedListArray(){   {       String pos = "";       String val = "";       String PosPlusVal = "";   try {     BufferedReader in = new BufferedReader(new FileReader("C:/Users/Steve/Desktop/file.txt"));     String str;     while ((str = in.readLine()) != null) {         String[] temp = str.split(" ");         Cols = temp.length;         LinkedList list = new LinkedList();     for (int i=0; i< temp.length; i++){         if (!temp[i].equals("0")){         pos = Integer.toString(i);         val = temp[i];         PosPlusVal = pos+" "+val;         list.add(PosPlusVal);         }         myLinkedListArray[Lines]=list;     Lines++;     }   }     in.close(); } catch (IOException e) {     System.out.println(e.toString()); }   }     } }```
• 03-01-2011, 08:45 AM
JosAH
My approach would be to create a coordinate class like this:

Code:

```public class Coordinate {   private int x, y;   public Coordinate(int x, int y) {       this.x= x;       this.y= y;   }   public int hashCode() { return x^y; }   public boolean equals(Object obj) {         if (!(obj instanceof Coordinate)) return false;       Coordinate that= (Coordinate)obj;       return this.x= that.x && this.y == that.y;   } }```
... and have a HashMap<Coordinate, Double> that stores the sparse matrix. If a Coordinate is not present as a key in the map that particular matrix element is supposed to be 0.0

kind regards,

Jos