Results 1 to 6 of 6
  1. #1
    sehudson's Avatar
    sehudson is offline Senior Member
    Join Date
    Mar 2010
    Posts
    379
    Rep Power
    6

    Default 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

    Java Code:
    public class Matrix{
    
    public Matrix{
    LinkedListArray L = new LinkedListArray();
    
    }
    
    
    
    }
    Last edited by sehudson; 03-01-2011 at 03:02 AM.

  2. #2
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,327
    Rep Power
    8

    Default

    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.

  3. #3
    sehudson's Avatar
    sehudson is offline Senior Member
    Join Date
    Mar 2010
    Posts
    379
    Rep Power
    6

    Default

    (*over a beginners head*) lol.

  4. #4
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,327
    Rep Power
    8

    Default

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

  5. #5
    sehudson's Avatar
    sehudson is offline Senior Member
    Join Date
    Mar 2010
    Posts
    379
    Rep Power
    6

    Default

    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.

    Java 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());
    }
    
      }
    
        }
    }
    Last edited by sehudson; 03-01-2011 at 05:52 AM.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,044
    Blog Entries
    7
    Rep Power
    23

    Default

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

    Java 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
    The only person who got everything done by Friday was Robinson Crusoe.

Similar Threads

  1. Matrix Data Type
    By fraB3422 in forum New To Java
    Replies: 7
    Last Post: 02-27-2011, 03:08 AM
  2. help in matrix
    By Engineer in forum New To Java
    Replies: 7
    Last Post: 10-06-2010, 01:26 PM
  3. Matrix Message
    By shindry in forum New To Java
    Replies: 2
    Last Post: 05-04-2009, 04:32 AM
  4. displaying 2D-Matrix
    By srinivasmallabathula in forum New To Java
    Replies: 2
    Last Post: 02-18-2009, 08:19 PM
  5. Help with matrix
    By susan in forum New To Java
    Replies: 1
    Last Post: 08-07-2007, 04:37 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •