Using C++

In this lab we are going to finish the Mvector class, and begin to develop and implement the template class Mlist.

First add iterators to the class Mvector. The interface is here:

template class Lnode { public : T data; Lnode *lptr; Lnode *rptr; };

template class Mlist { public : typedef Lnode* iterator; Mlist(); void add(T x); // add to back void del(); // delete front void del(T x); //deletes nodes with value x; T getfront(); iterator firstptr(){return first;} iterator lastptr(){return last;} T operator[] (unsigned int i); void insert(int i, T x); void erase(int i); int size(){return lsize;}

private : Lnode *first; Lnode *last; int lsize; };

Write the functions and test them with a main program.

Next create the interface for the class along with function stubs. The interface is here:

template class Mvector { public: typedef T* iterator; Mvector(); Mvector(unsigned int n); void pushback(T x); void popback(); void clear(); void insert(int i, T x); void erase(int i); T operator[] (unsigned int i); void operator-- (int); int size(); iterator begin() {return v;} iterator end() {return v+vsize;} void insert(iterator ix, T x); void erase(iterator ix); private: int vsize; int vcap; T *v; void reserve(unsigned int n); };

Add stubs for each member function and test the compilation (c++ -c).

Write the functions and test the compilation.

Write a main program that tests the class functions. (Use the pseudo-random number generator to create a list and add and remove elements from the list).

del(T x) function: template void Mlist::del(T x) { if (lsize==0) { return; } Lnode *ptr=first; while ( ptr != 0 ) { if (ptr->data == x) { Lnode *next = ptr->rptr; Lnode *previous = ptr->lptr; if (previous==0 and next==0) // one element { delete first; first=0; last=0; lsize--; return; } if ( next==0) // last element { last=previous; last->rptr=0; delete ptr; lsize--; return; } if (previous==0) //delete first element { first=ptr->rptr; first->lptr=0; delete ptr; lsize--; ptr=first; } else // not the first and not the last { previous->rptr=ptr->rptr; next->lptr=ptr->lptr; delete ptr; ptr=next; lsize--; } } else // move ptr to right { ptr=ptr->rptr; } } }

Insert Function:

template void Mlist::insert(int i,T x) { Lnode *nptr = new Lnode; nptr->data=x; assert(i>=0 and i<=lsize); if (i==0 and lsize==0) //empty list { first=nptr; last=nptr; nptr->lptr=0; nptr->rptr=0; lsize++; return; } if (i==0) //add front { nptr->lptr=0; nptr->rptr=first->rptr; first=nptr; lsize++; return; } if (i==lsize) //add end { nptr->lptr=last; last->rptr=nptr; nptr->rptr=0; last=nptr; lsize++; return; } Lnode *ptr=first; for (int j=0; j< i; j++) { ptr=ptr->rptr; } Lnode *previous = ptr->lptr; nptr->rptr=ptr; nptr->lptr=previous; previous->rptr=nptr; ptr->lptr=nptr; lsize++; return; }

Erase Function:

template void Mlist::erase(int i) { Lnode *ptr=first; for (int j=0; j< i; j++) { ptr=ptr->rptr; } // now ptr points to [i] Lnode *next = ptr->rptr; Lnode *previous = ptr->lptr; if (previous==0 and next==0) // one element { delete first; first=0; last=0; lsize--; return; } if ( next==0) // last element { last=previous; last->rptr=0; delete ptr; lsize--; return; } if (previous==0) //delete first element { first=ptr->rptr; first->lptr=0; delete ptr; lsize--; ptr=first; } else // not the first and not the last { previous->rptr=ptr->rptr; next->lptr=ptr->lptr; delete ptr; lsize--; } }