You are here:

Question
QUESTION: Dear Vijayan,
You're my favorite expert on this site, I'm glad you're back from vacation :)

I am trying to do some exercises from an ebook that does not provide the answers!

could you help me to get started with this exercise please?

I don't know how to code the functions add and extract in the classes below:

template <typename T> class FilePrio

{   public:

void add(const T& t);//should ad t to the list preserving the order

T extract();//should return the value of the head and delete the value

private:

};

template <typename T> class Element

{   public:

Element(T t): val(t),next(NULL){}

private:

T val;

Element<T> * next;

friend class FilePrio<T>;

};

I appreciate your time and help on this :)

ANSWER: i am guessing, the intent seems to be:

template <typename T> class FilePrio
is a singly linked list (elements are of type T).
there is a tacit assumption that a T can be compared with another T (for example using the < operator).
the list is intended to contain unique values and to be always sorted (let us say in ascending order of its elements).

to add an element to this list (preserving the order), you need to get to the correct position in the list.
a. if the list is empty, add it.
b. if the list is not empty,

template <typename T> void FilePrio::add( const T& t )
{
Element<T>* previous = 0 ;
while( ( current != 0 ) && ( t < current->val ) )
{
previous = current ;
current = current->next ;
}
if( current == 0 )
{
// add t as the last element
}
else if( current->val != t )
{
// add the new element between previous and current
}
else
{
// the element is already present
}
}

extract (//should return the value of the head and delete the value) is trivial:

{
return value ;
}
else
{
// error
// report it eg.
throw "attempted to access head of empty list" ;
}

---------- FOLLOW-UP ----------

I'm sorry I totally forgot to mention that it was a singly linked list and comparative operators assumed to be defined! you guessed it anyway, it shows that you're a pro.
allow me to ask my questions on the comment in the code please.

template <typename T> void FilePrio::add( const T& t ) {
// don't we need to add someting like if (head==0) before the next 2 statements?
Element<T>* previous = 0 ;
while( ( current != 0 ) && ( t < current->val ) )
{
previous = current ;
current = current->next ;
}
if( current == 0 )
{// when current = 0 that means the head=0 so this is the cause when the list is empty right?
current->val=t;
previous=0;

// add t as the last element
}
else if( current->val != t )
{
// add the new element between previous and current
// I'm kind of confused, should I create a new element?
// something like Element* newEl= new Element(t)
}
else
{
// the element is already present
}
}

emplate <typename T> void FilePrio::add( const T& t ) {
// don't we need to add someting like if (head==0) before the next 2 statements?

// not essential (if head==0, current==0 and
// the while loop will not execute).
// but we need to make that check somewhere, either here
// or after the loop

Element<T>* previous = 0 ;

// this loop starts comparing t with the elements
// one by one till we get to the right position
// keep moving down the list past all elements
// which are smaller than t

// *** note the correction in the second clause of the if
while( ( current != 0 ) && ( current->val < t ) ) // ***
{
previous = current ;
current = current->next ;
}

// at this point current is either 0 (end of list)
// or points to the first element >= t in the list
// and previous is the element just before it.

if( current == 0 )
{// when current = 0 that means the head=0 so this is the cause when the list is empty right?

// no, if current==0 and previous!=0, the list is not empty.
// in this case, previous is the last element
// add the new element as the last (previous->next)
if( previous != 0 )
previous->next = new Element<T>( t ) ;

// else ( current==0 && previous==0 ), the list is empty
else head = new Element<T>( t ) ;

// these statements are not required
// current->val=t;
// previous=0;
//

}
else if( current->val != t )
{
// add the new element between previous and current
// I'm kind of confused, should I create a new element?
// something like Element* newEl= new Element(t)

// the new element added would be previous->next
// the next of the new element would be current
previous->next = new Element<T>( t, current ) ;
}
else
{
// the element is already present
}
}
Questioner's Rating
 Rating(1-10) Knowledgeability = 10 Clarity of Response = 10 Politeness = 10 Comment No Comment

C++

Volunteer

#### vijayan

##### Expertise

my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.