A two-dimensional array of integers in which most elements are zero is called a sparse array. Because most elements have a value of zero, memory can be saved by storing only the non- zero values along with their row and column indexes. Create a SparseArrayEntry structure to have fields for row, col and value.
The SparseArray vector represents a sparse array. It contains a list of SparseArrayEntryobjects, each of which represents one of the non-zero elements in the array. The entries representing the non-zero elements are stored in the list in no particular order. Each non-zero element is represented by exactly one entry in the list.
The following table shows an example of a two-dimensional sparse array. Empty cells in the table indicate zero values.
The sample array can be represented by the SparseArray vector, with the following instance values. The items in entries are in no particular orderl one possible ordering is shown below.
(a) Write the SparseArray function getValueAt. The method returns the value of the sparse array element at a given row and column in the sparse array. If the list entries contains an entry with the specified row and column, the value associated with the entry is returned. If there is no entry in entries corresponding to the specified row and column, 0 is returned.
In the example above, the call sparse. getValueAt(3, 1) would return - 9, andsparse. getValueAt(3, 3) would return 0.
CISC 1600 Sparse 2D Array Prof. Kadri
Write the sparseArray function removeColumn, After removing a specified column from a sparse array:
 All entries in the list entries with column indexes matching col are removed from the list.
 All entries in the list entries with column indexes greater than col are replaced by entries
with column indexes that are decremented by one (moved one column to the left).
 The number of columns in the sparse array is adjusted to reflect the column removed.
The sample object sparse from the beginning of the question is repeated for your convenience.
The shaded entries in entries, below, correspond to the shaded column above.
When sparse has the state shown above, the call sparse. removeColumn(1)could result in sparse having the following values in its instance variables (since entries is in no particular order, it would be equally valid to reverse the order of its two items). The shaded areas below show the changes.
CISC 1600 Sparse 2D Array Prof. Kadri
Test your code with this main() function: int main()
{
// Create a SparseArray vecor // Add 4 SparseArrayEntries: // SparseArrayEntry(1, 4, 4)
// SparseArrayEntry(2, 0, 1)
// SparseArrayEntry(3, 1, -9) // SparseArrayEntry(1, 1, 5)
showEntries();
cout<<"\ngetValueAt(3,1): "<
cout<< "\nremoveColumn(1)"; removeColumn(1); showEntries();
return 0; }
Output should look like this: row: 1 col: 4 value: 4
row: 2 col: 0 value: 1
row: 3 col: 1 value: -9 row: 1 col: 1 value: 5
getValueAt(3, 1): -9 getValueAt(3, 3): 0
removeColumn(1) row: 1 col: 3 value: 4 row: 2 col: 0 value: 1
Note: after removing column 1 the original entries
row: 1 col: 4 row: 2 col: 0
became row: 1 col: 3 row: 2 col: 0
value: 4 value: 1
value: 4 value: 1
Because The number of columns in the sparse array is adjusted to reflect the column removed and column 4 shifted one down to column 3.