In this exercise you will practice basic C++ class construction, and memory allocation and deallocation. You are asked to implement a class that supports an extendable variant of a sparse matrix (look it up). A matrix is a two-dimensional array. A matrix is sparse when many positions in the array are not important. In usual sparse matrices entries are not important when they are 0. In our version of the saprse matrix we distinguish between existing positions and not existing positions. Existing positions in our sparse matrices could contain the entry 0. In both cases, allocating memory to the unimportant positions in the matrix is a waste of memory. You could think about a database containing students and their grades in modules. Every row in the database corresponds to a student and every column corresponds to a module. Then, grades are to be stored only in modules that the student did take. The entry that corresponds to a module that the student did not take should not exist. In particular, 0 is a possible grade in a module that a student takes.
To summarize, you are going to implement a sparse matrix that stores integers (including 0) in some of the positions of a (relatively large) two-dimensional array. Technically, I have created the header file for the sparse matrix. You have to complete it with additional members. You will have to only submit two files: Sparse.cpp and Sparse.hpp. You will probably want to create your own main.cpp file that includes a program that actually executes your Sparse.cpp. You will not be submitting this file(main.cpp). I also supply a Makefile that you should (must) use for compilation. The Makefile includes a compilation of a main.cpp. The header file includes detailed descriptions of the functions that are required that you implement. Specific requirements: The way to implement this is by having a two-dimensional linked-list (look up linked-list). This essentially means that your matrix is a collection of cells (see the provided Cell.hpp and Cell.cpp) that are connected by pointers to the cells above, below, to their left, and to their right.
This means that your memory requirements are proportional to the number of elements stored in the matrix. Also, every operation that you perform will take time that is proportional to the number of elements in the matrix. The disadvantage of this option is that it is quite complicated to implement. Notice that I set up Cell to be ready for implementing a doubly linked list. Solutions implementing singly-linked data structures will not incur a penalty. However, they will provide fast access in one direction only. In any case, you have to implement the member function whatDidIImplement(). This function returns a value that identifies your solution in this case its "two-dimensional linked-list".
If your function returns a value that does not match your implementation strategy it could cost you up to 5 points. Materials provided: Cell.hpp Cell.cpp Sparse.hpp main.cpp - a small example prepared by Paula showing how to use Cells to create a linked list. main1.cpp - an alternative main file that includes a small test of Sparse. Prepared by Paula. mmain.cpp - compilation tester. Makefile tests.cpp - test cases Avoid Compilation Problems: In order to make sure that your program compiles you should put in a fresh directory your submission (Sparse.cpp, Sparse.hpp), the Makefile from above, Cell.cpp and Cell.hpp from above, and the file mmain.cpp from above. Change the name of mmain.cpp to main.cpp and compile using make. This should produce an executable called main. It will most likely crash (and that's fine). But it should compile! Operating Sytem Used Linux g++ complier.
Attachment:- Assignment.zip