Doubly Linked Lists and Library Routine Problem

[aranjan]

Okay so this is part of an assignment I have to do, but I am confused regarding the library routine as my professor has not covered it well. So my thing is what do it do to create the library...is it just a .h file with all the functions specified below. I know this is a big question, but I am just not sure how to tackle this problem. I don't expect codes by any means just pointers to the right direction. Any help is greatly appreciated. Thanks

Use Doubly linked list to model a sparse matrix. A row is represented as a vector of doubly linked list containing non-zero entries in the row. The element in the row vector also acts as a header for the corresponding doubly linked list, and contains the information about number of non-zero elements in the row. A column is represented as a vector of doubly linked list containing non-zero entries in the column. A column-vector also acts as the header for the doubly linked list for the non-zero elements in the corresponding column. A value node is modeled as a 7-tuple of the form (left pointer, Up pointer, row, column, value, down pointer, right pointer). Left pointer points to a node in the same row previous non-zero column; right pointer points to a node in the same row next non-zero column; up pointer points to the previous row with a non-zero entry in the same column, and down-pointer points to the next row with non-zero entry in the same column. Write a library routine to implement following methods: next_column_entry, next_row_entry, prev_row_entry, prev_column_entry, row_entries(row_number), column_entries(column_number), no_of_elements_in_row(row_number), no_of_elements_column(column_number), is_empty_row(row_number), is_empty_column(column_number), get_entry(row_number, column_number), set_entry(row_number, column_number, value), is_empty_matrix().

[aranjan]

Yeah I saw my professor and each time he confuses me more... He actually edited the first portion of my code and said I don't need to use vectors. This is what it looks like now:

#include <iostream>
#include <vector>
using namespace std;

template <typename T>
class sparse
	{

//int rowsize = 100;
//int columnsize = 100;
		
		struct valuenode
		{	//7-tupple
			valuenode *left_pointer;
			valuenode *up_pointer;
			T rownumber;
			T columnnumber;
			T value;
			valuenode *down_pointer;
			valuenode *right_pointer;
		};

		valuenode *rows;
		valuenode *columns;
		
	};

template<typename T>
void next_column_entry();
{
	
}

template<typename T>
void next_row_entry();
{
	
}

template<typename T>
void prev_row_entry();
{
	
}

template<typename T>
void prev_column_entry();
{
	
}

template<typename T>
void row_entries();
{
	
}

template<typename T>
void column_entires();
{
	
}

template<typename T>
void no_of_elements_in_row();
{
	
}

template<typename T>
void is_empty_row();
{
	
}

template<typename T>
void is_empty_column();
{
	
}

template<typename T>
void get_entry();
{
	
}

template<typename T>
void set_entry();
{
	
}

template<typename T>
void is_empty_matrix();
{
	
}


int main()
{
		
}

Definitely a ton of work left to do. Anyone have any suggestions as to what I should do next, because my professor is not of very much help.

[mike_2000_17]

Wow... your prof. seems to be a d'bag. Not to mention that this is probably the worst possible way to implement a sparse matrix class. And it doesn't seem like your prof has much of an idea about C++ programming.

Anyways, the explanation is very vague, but from what I understand of the problem, this is what I can say. First, the problem says "implement the following methods:..", this means all the functions that you have there should be methods, i.e., member functions of class "valuenode" for most and some for "sparse".

Second, the struct "valuenode" is also templated. I'm not sure if it needs "template<..>" before its declaration but it certainly needs it when declaring pointers "valuenode*", it should be "valuenode<T>*".

Third, you need to figure out what the prototype of theses methods are supposed to be. I'm guessing "prev_row_entry()" should return the valuenode pointer to the previous row. All these are pretty simple. Then the others, like "get_entry" and things might involve some hopping through the linked list (custom iterators if you want to be fancy). Really, implementing stuff as linked list is really not that hard, you just hop from one node to the next instead of incrementing an index.

Essentially, this problem is like implementing a "std::list" class, so look at that standard class, its methods and iterators to understand what your prof wants you to do but in 2D (rows and columns) instead of "list" which is only linear.

Frankly, this is really an ill-defined assignment problem and I would protest and demand to the prof that he posts a clearer "contract" for the assignment. A C++ professor should know what "programming by contract" means, so tell him "if you want me to program well, you need to give me a well-defined programming contract", i.e., real prototypes for the methods with clearly defined input/output and required behavior. Alternatively, if this is more of a software engineering task, then the purpose of this "sparse" class needs to be better defined (because in the description it says how it should be done but not exactly, and then says nothing about how you would use this "sparse" class).