Matrix Data Assignment

[sehudson]

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

public class Matrix{

public Matrix{
LinkedListArray L = new LinkedListArray();

}



}

[quad64bit]

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.

[sehudson]

(*over a beginners head*) lol.

[quad64bit]

Is your sparse matrix an actual matrix (i.e. a 2d array?) or is it a sparse list?

[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.

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

  }

    }
}

[JosAH]

My approach would be to create a coordinate class like this:

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