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