Update! Homework help NOW available via e-mail ... (or in person if in Toronto Ontario Canada region.)
This space is reserved for a table of contents of links to various C/C++ topics ... and resources
Here is a link for beginners ... to linked lists (using C++):
http://developers-heaven.net/forum/index.php/topic,106.msg266.html#msg266For an example of recursive calls to a linked list of char's (to print the list reversed) ... see:
(most recent update is maintained here)
http://developers-heaven.net/forum/index.php/topic,106.msg569.html#msg569 (or)
http://www.dreamincode.net/code/snippet5082.htmTemplate class List ... with insert sort and merge sort (recursive) ... see a copy at:
http://www.dreamincode.net/code/snippet3448.htmOr look here (for most recent update) ...
// templateClassList2.cpp
// this version: 2010-04-16
// template class List with 'merge sort' and 'insert sort'
// has private class members: 'pFront', 'pRear' and 'size'
// and public copy constructor and overloaded assignment operator
#include <iostream>
#include <fstream>
#define haveFile true
using namespace std;
template< class T >
class List
{
public:
List();
~List();
List( const List <T> & obj ) // inline copy constructor ...
{
pFront = pRear = NULL;
size = 0;
for( Node* p = obj.pFront; p != NULL; p = p->next )
push_back( p->data );
is_sorted = obj.is_sorted;
}
List& operator = ( const List <T> & obj ) // inline overloaded assignment
{
// return if lists are already the same list ...
if( this == &obj ) return *this;
// ok ... not same ... so ...
if( size ) erase(); // sets ...pFront=pRear=NULL; size=0; is_sorted=true
else { pFront = pRear = NULL; size = 0; }
// now ...
for( Node* p = obj.pFront; p != NULL; p = p->next )
push_back( p->data );
is_sorted = obj.is_sorted;
return *this;
}
void push_front( T e );
void push_back( T e );
void add_at_index( int c, T e );
void remove( T e );
void show_all() const;
bool exist( T e ) const;
int length() const;
T List<T>::max() const;
T List<T>::min() const;
// insert new element e in sorted order into a sorted list ...
void isort_insert( T e );
void isort(); // insert-sort the whole list in place ...
void update_pRear()
{
pRear = pFront;
while( pRear->next != NULL ) pRear = pRear->next;
}
// merge sort the whole list in place (a 'divide and sort' recursive sort)
void msort()
{
Node* p = pFront;
merge_sort( p, size ); // p is updated in recursion using pass by ref.
set_pFront_pRear( p );
is_sorted = true;
}
void remove_duplicates()
{
if( size <= 1 ) return;
if( !is_sorted ) msort();
Node* p = pFront;
while( p->next != NULL )
{
if( p->data == p->next->data )
{
Node* tmp = p->next;
p->next = p->next->next;
delete tmp;
--size;
}
else p = p->next; // move up one ...
}
update_pRear();
}
private:
struct Node
{
T data;
Node* next;
}*pFront, *pRear;
int size; // number of list nodes
bool is_sorted;
void erase()
{
if( !size ) return;
for( Node* q = pFront; q != NULL; pFront = q )
{
q = pFront->next;
delete pFront;
}
pRear = NULL; // Note: pFront is set to NULL above on last for loop
size = 0;
is_sorted = true;
}
void insert_sorted( Node*& pHead, Node* pNewNode );
void merge_sort( Node*& pFront, int size ); // returns updated pFront by ref.
// merge two sorted lists with heads 'a' and 'b' ... in sorted order
Node* merge (Node* a, Node* b )
{
if( a == NULL ) return b;
if( b == NULL ) return a;
Node* sorted; // now get appropriate new head for merged list
if( a->data <= b->data )
{
sorted = a;
a = a->next;
}
else
{
sorted = b;
b = b->next;
}
Node* new_merged_head = sorted;
// now merge lists ...
while( a != NULL && b != NULL )
{
if( a->data <= b->data )
{
sorted->next = a;
sorted = sorted->next;
a = a->next;
}
else
{
sorted->next = b;
sorted = sorted->next;
b = b->next;
}
}
// now ... append the ONE part that might have been left-over above ...
if( a != NULL )
sorted->next = a;
else if( b != NULL )
sorted->next = b;
return new_merged_head;
}
void set_pFront_pRear(Node* p) { pFront = p; update_pRear(); }
};
// definitions ...
template< class T >
List<T>::List()
{
pFront = pRear = NULL;
size = 0;
is_sorted = true;
}
template< class T >
List<T>::~List()
{
erase();
}
template< class T >
void List<T>::push_front(T e) // inserts e with type T at front of List
{
Node* n = new Node;
n->data = e;
n->next = pFront;
pFront = n;
if( pRear == NULL ) pRear = pFront;
++size;
is_sorted = false;
}
template< class T >
void List<T>::push_back(T e) // inserts e with type T at end of List
{
Node* n = new Node;
n->data = e;
n->next = NULL;
if( pFront != NULL )
{
pRear->next = n;
pRear = n;
}
else
pRear = pFront = n;
++size;
is_sorted = false;
}
template< class T >
void List<T>::add_at_index( int c, T e) // inserts e with type T at index c
{
if( c>= 0 && c < size )
{
if( c > 0 )
{
// insert at index c ... BUT after index 0 ... i.e. at 1 to size
Node* prev = pFront;
for( int i = 1; i < c; ++i ) prev = prev->next;
Node* n = new Node;
n->data = e;
// now insert n at index c ... A -> B becomes A->C->B
n->next = prev->next; // C -> B
prev->next = n; // A -> C
++ size;
is_sorted = false;
} // here c is 0 ... so ...
else push_front( e ); // resets size, pFront and pRear ... as applicable
}
else if( c == size ) push_back( e );
else
{
cout << "\nHighest new index allowed is " << size
<< ". You requested index " << c << " ... push_back y/n ? ";
int reply = cin.get();
cin.sync();
if( reply == 'n' || reply =='N' )
return;
// if reach hear ...
cout <<"Ok ... will push_back ...\n";
push_back( e ); // resets size, pFront and pRear ... as applicable
}
}
template< class T >
void List<T>::remove( T e )
{
if( !size )
{
cout << "\nCan not remove '" << e << "' since list is empty.\n";
return;
}
Node* q = pFront;
if( q->data == e ) // if at front ...
{
pFront = q->next;
delete q;
--size;
cout<<"\n'" << e <<"' removed ...";
if( size <= 1 ) { pRear = pFront; is_sorted = true; }
return;
}
// if reach here ... 'e' is NOT the first
Node* prev = q;
q = q->next; // q now points to 2nd node in list ...
while( q != NULL ) // Note: also handles case of just one Node in list
{
if( q->data == e )
{
prev->next = q->next;
delete q;
cout<<"\n'" << e <<"' removed ...";
--size;
if( prev->next == NULL ) pRear = prev; // update 'rear' ...
if( size == 1 ) is_sorted = true;
return;
}
// if reach here ... advance both nodes up the list ...
prev = q;
q = q->next;
}
cout<<"\n'" << e <<"' NOT found ...";
}
template< class T >
void List<T>::show_all() const
{
for( Node* q = pFront; q != NULL; q = q->next )
cout << endl << q->data;
}
template <class T>
bool List<T>::exist( T e ) const
{
for( Node* q = pFront; q != NULL; q = q->next )
if( q->data == e )
return true;
return false;
}
template <class T>
int List<T>::length() const
{
return size;
}
template <class T>
T List<T>::max() const
{
if( !size )
{
cout << "List is empty ... returning 'zero' ... ";
return T(0);
}
T max = pFront->data;
for( Node* q = pFront; q->next != NULL; q = q->next )
if( q->next->data > max )
max = q->next->data;
return max;
}
template <class T>
T List<T>::min() const
{
if( !size )
{
cout << "List is empty ... returning 'zero' ... ";
return T(0);
}
T min = pFront->data;
for( Node* q = pFront; q->next != NULL; q = q->next )
if( q->next->data < min )
min = q->next->data;
return min;
}
//////////////////////////////// BEGIN MERGE SORT //////////////////////////////
// divide list into two halves and then recursively sort each half ...
// then merge the two sorted halves using the above merge function
// Note: calling 'pFront' is updated by using 'pass by ref'
template <class T>
void List<T>::merge_sort(Node*& pFront, int size)
{
if( size <= 1 ) return;
Node* pHead2;
Node* pEnd1;
int size2 = size/2;
int size1 = size - size2;
// split the list into two lists ... the first half begins with pHead
pEnd1 = pFront; // first set pEnd1 to the head address ...
for( int i=1; i<size1; ++i )
pEnd1 = pEnd1->next;
pHead2 = pEnd1->next; // second half begins with pHead2
pEnd1->next = NULL; // breaking the chain here... so we can have two lists
// merge the lists after recusively merge_sorting them
merge_sort( pFront, size1 );
merge_sort( pHead2, size2 );
pFront=merge( pFront, pHead2 );
}//////////////////////////////// END MERGE SORT ///////////////////////////////
/////////////////////////////////// BEGIN ISORT ////////////////////////////////
// does NOT update pRear ... so must call update_pRear() when all inserts done.
template <class T>
void List<T>::isort_insert( T e )
{
Node* n = new Node;
n->data = e;
n->next = NULL;
if( size > 0 && !is_sorted ) msort();
insert_sorted( pFront, n );
++size;
}
// insert a new node in a list with its node data in proper order ... does NOT
// update size or pRear ... so must call update_pRear() when all inserts done.
template <class T>
void List<T>::insert_sorted( Node*& pHead, Node* pNewNode )
{
// First ... handle case where new node should be first element
if( pHead == NULL || pNewNode->data < pHead->data )
{
// It now becomes the first element
pNewNode->next = pHead; // old pHead becomes 2nd in list
pHead = pNewNode; // and this new node becomes the head of the list
}
else // If here ... search the nexted list for the right location
{
Node* q = pHead; // Get a working copy of pHead in q
// Start comparing with element AFTER 'q' ... i.e. the 'next in'
while( q->next != NULL && q->next->data <= pNewNode->data )
{
q = q->next; // Traverse the list ...
}
// Ok, insert after 'q' by 're-nexting' the pointers
// ( Includes inserting at end position ... where q->next == NULL )
// for A->B to become A->N->B ...
pNewNode->next = q->next; // first insert/link ... N->B
q->next = pNewNode; // and now link ... A->N
}
}
// insert sort a whole list ...
template <class T>
void List<T>::isort()
{
// Note: pNewHead MUST be NULL to start ...
Node *pTmp, *pHead = pFront, *pNewHead = NULL;
while( pHead != NULL ) // take each node from old list and insert in new
{
pTmp = pHead; // get 'this' node ...
pHead = pHead->next; // move 'start' up one, to be ready for next node
insert_sorted( pNewHead, pTmp ); // insert 'this' pTmp node
}
set_pFront_pRear( pNewHead );
is_sorted = true;
} ///////////////////////////////// END ISORT //////////////////////////////////
// used in main ...
void pause()
{
cout << "\n\nPress 'Enter' to continue ... ";
cin.clear();
cin.sync();
cin.get();
}
int main() ////////////////////////// MAIN /////////////////////////////////////
{
List <int> ml; // construct an empty list to hold int's
ml.remove(1);
cout<<"Number of elements = "<<ml.length();
ml.show_all();
cout << "\nml.max() = ";
cout << ml.max();
cout << "\nml.min() = ";
cout << ml.max();
cout << "\n\nAfter push_back(...) 's ...";
ml.push_back(3);
ml.push_back(2);
ml.push_back(1);
ml.push_back(6);
ml.push_back(5);
ml.push_back(4);
cout<<"\n'6' is in the list = " <<(ml.exist(6) ? "True." : "False.");
cout<<"\n'22' is in the list = " <<(ml.exist(22) ? "True." : "False.");
cout << "\nml.max() = ";
cout << ml.max();
cout << "\nml.min() = ";
cout << ml.max();
ml.show_all();
cout<<"\nNumber of elements = "<<ml.length();
pause();
ml.add_at_index(0,0);
ml.push_back(7);
ml.show_all();
cout<<"\nNumber of elements = "<<ml.length();
pause();
ml.add_at_index(8,8);
ml.show_all();
cout<<"\nNumber of elements = "<<ml.length();
pause();
ml.add_at_index(9,9);
ml.add_at_index(10,10);
ml.show_all();
cout<<"\nNumber of elements = "<<ml.length();
pause();
// before isort ... get a copy ...
List <int> mlcopy( ml );
ml.isort();
ml.show_all();
cout<<"\nNumber of (isort sorted) elements = "<<ml.length();
pause();
cout << "\nEnlarged mlcopy (before msort) ... ";
mlcopy.push_front(10);
mlcopy.push_front(44);
mlcopy.push_front(10);
mlcopy.push_front(44);
mlcopy.show_all();
cout<<"\nNumber of elements = "<<mlcopy.length();
pause();
mlcopy.msort();
mlcopy.show_all();
cout<<"\nNumber of (msort sorted) elements = "<<mlcopy.length();
pause();
mlcopy.remove_duplicates();
cout << "\nAfter mlcopy.remove_duplicates() ...";
mlcopy.show_all();
cout<<"\nNumber of elements = "<<mlcopy.length();
pause();
cout << "\nNow returning to original list ... ml.show_all() ...";
ml.show_all();
cout<<"\nNumber of elements = "<<ml.length();
pause();
ml.remove(4); // now back to ml (original ...)
ml.remove(3);
ml.remove(5);
ml.remove(66);
ml.remove(0);
ml.remove(10);
ml.show_all();
cout<<"\nNumber of elements = "<<ml.length();
pause();
List < int > asn = ml;
cout << "\nAfter List < int > asn = ml ...";
asn.show_all();
cout<<"\nAnd ... asn.length() = " << asn.length();
pause();
# if haveFile
//=========================================================================//
List < int > list; // construct a new empty list 'list' to hold int's ...
ifstream fin("int.dat");
int x;
cout<< "\nA new list of unique elements from file, "
<< "using list.isort_insert(x) ...";
while( fin >> x )
{
if(!list.exist(x))
list.isort_insert(x);
}
list.update_pRear(); // RECALL: *MUST* update pRear when all insertions done
list.show_all();
cout << "\nNumber of elements = "<<list.length();
pause();
list.isort_insert(1492);
list.update_pRear(); // RECALL: *MUST* update pRear when all insertions done
cout << "\n\nAfter list.isort_insert(1492) ...";
list.show_all();
cout << "\nNumber of elements = "<<list.length();
pause();
list.remove(-47);
list.remove(-23);
while( list.exist(1492) ) list.remove(1492);
list.remove(-1);
if( list.exist(-2) ) list.remove(-2);
list.remove(1926);
list.remove(1935);
cout << "\nList Max = " << list.max();
cout << "\nList Min = " << list.min();
list.show_all();
cout << "\nNumber of elements = "<<list.length();
pause();
#endif
} //////////////////////////////////// END MAIN ////////////////////////////////
// FILE NAME: int.dat //
/*
1492
1776
1860
-23
1698
1935
1926
1953
1960
1492
1776
1860
-23
1698
2000
1935
1926
1953
1960
-47
*/
For a demo of template Class List (using a plain linked-list) ...
http://www.dreamincode.net/code/snippet2617.htmOr look here (for most recent update) ...
http://developers-heaven.net/forum/index.php/topic,106.msg570.html#msg570And some links to more 'list' examples ...
Search for a part of a string ... in a STL list of strings ...
http://www.dreamincode.net/forums/index.php?showtopic=152302&view=findpost&p=906829Compare these next 2 ... that sort a STL vector ... and sort a STL list ...
1. STL sort function to sort vector container of 'MyContacts' ... (from Chapter 15)
http://developers-heaven.net/forum/index.php/topic,127.msg280.html#msg280vs ...
2. STL list delete function is added here ... (from Chapter 15) Note we have switched from a STL vector container to a STL list container ... to allow easy deletes.
http://developers-heaven.net/forum/index.php/topic,127.msg281.html#msg281Carrying on with C++ lists ...these next 2 may be useful examples for C++ students ... 1. class Student using the STL list container to hold class Student objects ... vs ... 2. STL vector of class Student objects ...
1.
http://developers-heaven.net/forum/index.php/topic,106.msg272.html#msg272vs ...
2.
http://developers-heaven.net/forum/index.php/topic,106.msg198.html#msg198C++ Student class ... a very common student problem ... A very simple example of Student Records to get students started ... It uses a vector container to hold each 'Student'
1. takes in info from keyboard into a vector of 'Student' (uses push_back)
2. shows 'records' in memory on screen
3. writes to file the 'record's in memory
4. reads from file and puts records into memory
And ... an other class Student ... that uses the STL list ...
http://developers-heaven.net/forum/index.php/topic,127.msg614.html#msg614
Dilber MC Theme by HarzeM