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

    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,323
    Rep Power
    7

    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
    364
    Rep Power
    5

    Default

    (*over a beginners head*) lol.

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

    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
    364
    Rep Power
    5

    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 online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,767
    Blog Entries
    7
    Rep Power
    21

    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
    cenosillicaphobia: the fear for an empty beer glass

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, 02:26 PM
  3. Matrix Message
    By shindry in forum New To Java
    Replies: 2
    Last Post: 05-04-2009, 05: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, 05: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
  •