1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

Sparse Array using Multi-Linked List.

Discussion in 'C++' started by united07, May 24, 2010.

  1. united07

    united07 New 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 a moderator: May 25, 2010
  2. united07

    united07 New Member

    95 views no replies ? :surprised
     
  3. xpi0t0s

    xpi0t0s Mentor

    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.
     

Share This Page