Question 4: Sparse tables [10]

In lectures we discussed the idea of a sparse table whose implementation was a two-dimensional linked list. Study the partial definition below for a sparsetable class, then provide an implementation for the private search method. (If you need to make any assumptions about the behaviour of other methods in the class be sure you clearly state them.)

class sparsetable {
   private:
      // each cell or node in the table keeps track of the 
      //   nearest neighbours, its own data, and a copy of
      //   its own position in the table
      struct node {
         node *up, *down, *left, *right;
         int  row, col;
         string data;
      };
      // keep ptrs to the first element in each row and column
      node *RowPtrs[MaxRows]; 
      node *ColPtrs[MaxCols]; 
      int numrows, numcols;
      node *search(int r, int c);
   public:
      sparsetable();
      ~sparsetable();
      bool insert(int r, int c, float d);
      bool search(int r, int c, float &d);
      bool remove(int r, int c);
};