Sparse Array using Multi-Linked List.

united07's Avatar, Join Date: May 2010
Newbie Member
How to implement sparse array using multi-linked list ?
Code:
struct Node {
int row;
int col;
int value;
Node* next_in_row;
Node* next_in_col;
};

class MultiLinkedListSparseArray {
private:
//add anything you need
public:
MultiLinkedListSparseArray(int rows, int cols, char* logFile);
~MultiLinkedListSparseArray();
void setCell(int row, int col, int value);
int getCell(int row, int col);
void display();
void log(char *s);
void dump();
};
In the constructor, you initialize anything you need in your sparse array.
In the destructor, you free any memory you allocated in your sparse array.
In the method setCell, you set a new value for the cell located at the provided row and column.
In the method getCell, you get the value of the cell located at the provided row and column.
The method display should be able to reconstruct the array and display it as a normal 2d array.
The method dump reconstructs the array and writes it into the log file.
The method log writes the given string into the log file.

Initially, assume that all the cells are set to zero.
Assuming that rows and columns indices start by 1, test code with the following code:
Code:
int main()
{
MultiLinkedListSparseArray a(5, 5, "SparseArrayLog.txt");
a.setCell(1, 5, 4);
a.log("Array after setting [1,5] to 4\n");
a.dump();
a.setCell(2, 1, 2);
a.log("Array after setting [2,1] to 2\n");
a.dump();
a.setCell(2, 2, 3);
a.log("Array after setting [2,2] to 3\n");
a.dump();
a.setCell(3,4, 5);
a.log("Array after setting [3,4] to 5\n");
a.dump();
a.setCell(4, 1, 7);
a.log("Array after setting [4,1] to 7\n");
a.dump();
a.setCell(4, 5, 8);
a.log("Array after setting [4,5] to 8\n");
a.dump();
a.setCell(5, 2, 6);
a.log("Array after setting [5,2] to 6\n");
a.dump();
cout << "X[2, 2] = " << a.getCell(2, 2) << endl;
cout << "X[3, 2] = " << a.getCell(3, 2) << endl;
cout << "X[4, 5] = " << a.getCell(4, 5) << endl;
a.setCell(3, 4, 0);
a.log("Array after setting [3,4] to 0\n");
a.dump();
a.setCell(1, 5, 0);
a.log("Array after setting [1,5] to 0\n");
a.dump();
a.setCell(2, 2, 0);
a.log("Array after setting [2,2] to 0\n");
a.dump();
a.setCell(5, 2, 0);
a.log("Array after setting [5,2] to 0\n");
a.dump();
a.setCell(4, 5, 0);
a.log("Array after setting [4,5] to 0\n");
a.dump();
a.setCell(2, 5, 7);
a.log("Array after setting [2,5] to 7\n");
a.dump();
a.setCell(5, 3, 8);
a.log("Array after setting [5,3] to 8\n");
a.dump();
a.setCell(2, 3, 5);
a.log("Array after setting [2,3] to 5\n");
a.dump();
a.setCell(2, 5, 3);
a.log("Array after setting [2,5] to 3\n");
a.dump();
a.setCell(2, 1, 0);
a.log("Array after setting [2,1] to 0\n");
a.dump();
a.setCell(4, 2, 4);
a.log("Array after setting [4,2] to 4\n");
a.dump();
a.setCell(4, 2, 2);
a.log("Array after setting [4,2] to 2\n");
a.dump();
a.setCell(4, 2, 0);
a.log("Array after setting [4,2] to 0\n");
a.dump();
a.setCell(4, 1, 0);
a.log("Array after setting [4,1] to 0\n");
a.dump();
a.setCell(2, 3, 0);
a.log("Array after setting [2,3] to 0\n");
a.dump();
a.setCell(2, 5, 0);
a.log("Array after setting [2,5] to 0\n");
a.dump();
a.setCell(5, 3, 0);
a.log("Array after setting [5,3] to 0\n");
a.dump();
return 0;
}

Last edited by shabbir; 25May2010 at 09:41.. Reason: Code blocks
united07's Avatar, Join Date: May 2010
Newbie Member
95 views no replies ?
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
Quote:
Originally Posted by united07 View Post
95 views no replies ?
Well, you've posted your assignment, but you haven't said where you're stuck. Do you understand what you need to do? Have you worked out how you're going to represent the data? A lot of the program has been written for you and the text tells you in quite a lot of detail what you need to do, so this is a fairly simple task to complete.