1
// 1. Non efficient algorithm of replace.
void replace( LinkedList& list, int val1, int val2 ) {
for(inti =0; ilist.length(); i++ )
if(list.elementAt(i) == val1 )
list.setElementAt(i,val2);
}
// 2. Efficient algorithm of replace, using Node information.
void replace( LinkedList& list, int val1, int val2 ) {
Node* p = list.getHead();
while(p){
if( p->m_data == val1 )
p->m_data = val2;
p = p->m_next;
}
}
// 3. Adding a pointer to LinkedList.
classLinkedList {
public:
// :
voidinitPointer() {
m_pointer =m_head;
}
voidadvancePointer() {
if(m_pointer)
m_pointer =m_pointer->m_next;
}
intgetPointedValue() const {
if(m_pointer)
returnm_pointer->m_data;
else
exit(1);
}
boolatEnd() const {
returnm_pointer == nullptr;
}
// :
private:
Node* m_pointer;
Node* m_head;
unsignedintm_size;
};
// Replace using the pointer of LinkedList.
void replace(LinkedListlist,int val1,int val2){
list.initPointer();
while( !list.atEnd() ) {
if(list.getPointedValue() == val1 )
list.getPointedValue() = val2;
list.advancePointer();
}
}
// 4. LinkedList pointers are not enough for the sort algorithm.
void sort( LinkedList& list ) {
for( Node*p = list.getHead() ; p ; p = p->m_next )
for( Node*p1 = p; p1 ; p1 = p1->m_next )
if( p1->m_data < p->m_data )
swap( p1->m_data, p->m_data );
}
// 5. Iterator of LinkedList.
classLinkedList {
// :
friendclassListIterator;
// :
};
classListIterator {
public:
ListIterator(LinkedList& l );
void next();
boolisEnd() const;
intval() const;
voidoperator =( constListIterator& other );
private:
LinkedListm_list;
Node* m_pointer;
};
ListIterator::ListIterator(LinkedList& l ):
m_list( l ),m_pointer( l.m_head ) {}
voidListIterator::next() {
if(m_pointer )
m_pointer = m_pointer->m_next;
else
exit(1);
}
boolListIterator::isEnd() const {
returnm_pointer == nullptr;
}
intListIterator::val() const {
if(m_pointer)
returnm_pointer->m_data;
else
exit(1);
}
voidListIterator::operator=( constListIterator& other ) {
if ( &m_list!=&other.m_list )
exit(1);
m_pointer = other.m_pointer;
}
// Sort using iterators.
void sort( LinkedList& list ) {
for( ListIterator it1(list) ; !it1.isEnd() ; it1.next() )
for( ListIterator it2(it1) ; !it2.isEnd() ; it2.next() )
if( it2.val() < it1.val() )
swap( it2.val(), it1.val() );
}
// 6. Sort using pointer code style.
void sort( ListIterator begin, ListIterator end ) {
for(ListIterator it1 = begin ; it1 != end ; it1++ )
for(ListIterator it2 = it1 ; it2 != end ; it2++ )
if( *it2 < *it1 )
swap( *it2, *it1 );
}
// Calling this sort function.
sort(ListIterator(myList), ListIterator(myList,nullptr) );
sort(myList.begin(), myList.end() );
// 7. Replace using pointer code style.
void replace( ListIterator p, ListIterator stop, int val1, int val2 ) {
while( p != stop ) {
if ( *p == val1 )
*p = val2;
p++;
}
}
// Calling this replace function.
replace(ListIterator(myList), ListIterator(myList,nullptr), 4, 14 );
replace(myList.begin(), myList.end(), 4, 14 );
// 8. Function adding for ListIterator and LinkedList classes.
// LinkedList
classLinkedList {
// :
public:
ListIteratorbegin();
ListIteratorend();
// :
};
ListIteratorLinkedList::begin() {
returnListIterator( *this );
}
ListIteratorLinkedList::end() {
returnListIterator( *this, nullptr );
}
ostreamoperator <( ostreamos,constLinkedList& list ) {
for ( ListIterator p = list.begin() ; p != list.end() ; p++ )
os < *p < "->";
returnos;
}
// ListIterator
classListIterator {
// :
public:
ListIterator(LinkedList& list, Node * p );
intoperator *();
ListIteratoroperator ++(intdammy );
booloperator ==( constListIterator& other );
booloperator !=( constListIterator& other );
// :
};
ListIterator::ListIterator(LinkedList& l, Node * p ):
m_list(l), m_pointer(p) {}
intListIterator::operator *() {
if ( m_pointer )
returnm_pointer->m_data;
else exit(1);
}
ListIteratorListIterator::operator ++(intdammy ) {
ListIteratoranswer( *this );
if ( m_pointer ) {
m_pointer = m_pointer->m_next;
return answer;
}
else exit(1);
}
boolListIterator::operator ==( constListIterator& other ) {
returnm_pointer == other.m_pointer;
}
boolListIterator::operator !=( constListIterator& other ) {
return !( *this == other );
}
// 9. Sort with pointer arguments (very similar to the last sort function).
void sort( int* begin, int* end ) {
for(int* it1 = begin ; it1 != end ; it1++ )
for(int* it2 = it1 ; it2 != end ; it2++ )
if( *it2 < *it1 )
swap( *it2, *it1 );
}
// Calling this sort function.
int array[5] = {12,32,45,67,9};
sort(array,array+5);
// 10. Code reuse - template function instead of implementing two sort functions.
templateclass T>
void swap( T& t1, T& t2 ) {
T tmp(t1);
t1 = t2;
t2 = tmp;
}
templateclass IT>
void sort( IT begin, IT end ) {
for( IT it1 = begin; it1 != end; it1++ )
for( IT it2 = it1 ; it2 != end ; it2++ )
if( *it2 < *it1 )
swap( *it2, *it1 );
}