Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   Sparse Array using Multi-Linked List. (http://www.go4expert.com/forums/sparse-array-using-multi-linked-list-t22198/)

united07 25May2010 01:14

Sparse Array using Multi-Linked List.
 
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;
}


united07 27May2010 06:13

Re: Sparse Array using Multi-Linked List.
 
95 views no replies ? :surprised

xpi0t0s 27May2010 12:27

Re: Sparse Array using Multi-Linked List.
 
Quote:

Originally Posted by united07 (Post 68466)
95 views no replies ? :surprised

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.


All times are GMT +5.5. The time now is 01:50.