Project 2 Preview

This project is to design sparse matrices and to fulfill some operations ( addition, subtraction and transpose ) on them. Five classes are to be implemented.

SMatrix 

        SMatrix is implemented by using the List ADT. Only the non-zero values in the matrix are store in the list. Each node in the list has two components: one is a pointer to the next node and the other one is an object. In this project, the object is a type SMatrixData.

SMatrixData

        SMatrixData records the information ( position and value ) of each non-zero elements in the matrix. It has three private data members:            

        int  _row:    the row number of the element;

        int  _col :    the column number of the element;

        int  _val:     the value of the elements.

         The function bool operator < (const SMatrixData &) const compares two SMAtrixData type objects by their positions. The comparison is executed first by row and then by column. The implementation is as following:

                            bool operator < (const SMatrixData & sm) const{

                                            if ( _row < sm._row) return true;

                                            if ( _row == sm._row && _col < sm._col ) return true;

                                            return false;

                            }

SortedLinkedList

        The list to represent the sparse matrix must be sorted. It is sorted by position of the element stored in each node, first by row then by column.. Since elements are represented by objects of SMatrixData, we can use the comparison function in SMatrixData to sort the list. There are two ways to implements the SortedLinkedList based on List class. One is to modify the List class directly and the other one is to derive SortedLinkedList from the List class. In both cases, we must modify or overloading the insert function in the List class. You can add accessors in List class when use inheritance.

SMRowIter and SMColumnIter

        In SMatrix class there are two functions RowIter( ) and ColumnIter( ) return SMRowIter and SMColumnIter respectively. SMRowIter is used to access each element in a specified row while SMColumnIter is used to access each element in a specified column. For example, RowIter(0) will return an object of SMRowIter which points to the first element of row 0. If the element at (0,0) has non-zero value, there must be a node in the sorted list to represent this element. We can simply produce a list iterator of the sorted link list and let it points to that node. 

        However, if the element at (0,0) is 0, no node in the sorted list represents this element. In this case, we create a dummy node to represent it. A dummy node has the same structure as the regular node except that its pointer always points to null and the _val variable in the SMatrixData object is always 0. The _row and _col variables can be changed so that we simply use only one dummy node to represent all those zero-value elements in a sparse matrix. 

        To demonstrate how SMRowIter works, assume function RowIter(1) is called. We first produce a list iterator of the sorted link list in class SMatrix which points to the first node of the list. Then compare the _row of the node with the specified row number 1. If  the node has a smaller row number  then call advance( ) in ListItr class until the list iterator points to the first node in the list with _row equal to 1 or larger than 1( if there is no node with _row equal to 1). Then we check the _col to see if it is 0. If _col is 0 then list iterator points to the first element in row 1 and we let the SMRowIter points to that node. If _col is not 0 then we create a dummy node, set  _row to 1 and _col to 0 and let the SMRowIter points to this dummy node. When advance( ) function in SMRowIter is called, we first check the node SMRowIter currently points to to find out the position of the next element and then check the sorted list to see if there is a node representing this element. If not, change the _col in the dummy node and let the SMRowIter points to it.

Matrix operation

addition and subtraction: to add two matrices M1 and M2, M1 and M2 must have the same size ( same number of  rows and same number of columns ).

multiplication: to multiply two matrices M1 and M2 ( M1*M2 ), the number of columns in M1 must equal to the number of rows in M2.

transpose: if M has size a*b, then MT, the transpose matrix of M, has size b*a and MT_ij=M_ji

Reminder

    Each class must have:

• default constructor;
• destructor;
• copy constructor;
• assignment operator.